Given a fixed $n \in \mathbb{N}$ larger than $1$, let $G(n)$ denote the largest number that is not expressible as a sum of prime powers larger than $n$ (the 'base' prime of the prime power need not be larger than $n$). I'm interested in upper bounds on $G(n)$.
From my understanding, Ramanujan's variation on Bertrand's postulate demonstrates the existence of two distinct primes between $n$ and $2n$ for all $n$ larger than $6$, and there exist two prime powers between $n$ and $2n$ for all $n>1$. If these two prime powers are denoted $p,q$, then their Frobenius number is $pq-p-q$. Thus, I obtain a bound of $G(n)\leq 4n^2 - 2n$, possibly marginally better with some detailing. But I suspect that a better bound should exist, since expressing numbers as sums of prime powers doesn't seem too restrictive of a condition.
Edit: I would also be interested in replacing the term 'prime powers' with 'numbers $x$ such that $\phi (x)\geq n$', where $\phi$ is the Euler-toitent function.
