# Numbers expressible as sums of prime powers larger than n

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.

• Using the fact that for large odd $m$ there are $\gg m^{2}(\log m)^{-3}$ ways to write $m$ as the sum of $3$ primes, and $\ll (n/\log n)(m/\log m)$ ways to write it as the sum of $3$ primes where one is at most $n$, it follows that $G(n)\ll n\log n$ (even restricting $G$ to just consider primes, not prime powers). – Thomas Bloom May 9 '14 at 7:48
• And trivially $G(n)\geq n$, so the hard part is in improving the log term if possible. The Goldbach problem for large $k$ (i.e. writing $n$ as the sum of $k(n)$ primes) would probably be a good place to look. – Thomas Bloom May 9 '14 at 7:51