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.

  • 6
    $\begingroup$ 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). $\endgroup$ – Thomas Bloom May 9 '14 at 7:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Bloom May 9 '14 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.