2

For example:

$2^2=4=2+2$

$2^3=8=3+3+2$

$2^4=16=5+5+3+3$

$2^5=32=17+7+3+3+2$

$2^6=64=17+17+17+7+3+3$

How much further can this go?

  • 4
    The answer is "yes" if Goldbach's conjecture is true. But since Goldbach is not necessary, there might be a proof for this weaker statement. – Peter Mar 14 '20 at 16:38
  • 1
    Just giving this question a quick glance, this would seem to fall into the category of "probably true but incredibly difficult to prove" (like Goldbach's conjecture). There might be a nice way of proving or disproving it, but I would be surprised. – QC_QAOA Mar 14 '20 at 16:38
  • @QC_QAOA A disproof would disprove Goldbach, this would be more than a surprise. – Peter Mar 14 '20 at 16:40
  • 1
    Once you get this far, there are lots of primes less than $2^n$, so lots of options for the sum to come out right. It would be shocking if there were a counterexample, but I have no idea how to prove it. There might be an approach using the density of primes to say the sum is possible for all naturals, not just $2^n$ – Ross Millikan Mar 14 '20 at 16:45
  • 4
    Well, since the ternary Goldbach conjecture is true, $2^n-3$ is an odd number which can be written as a sum of three primes, and so $2^n$ is certainly a sum of four primes for all $n$. – Luke Collins Mar 14 '20 at 16:45
  • @LukeCollins Formulate this as an answer. How could I overlook that ? – Peter Mar 14 '20 at 17:02

2 Answers2

5

This is a very difficult problem but luckily previous results allow us to solve it (thanks to @Luke_Collins). The Weak Goldbach Conjecture states that every odd number $n$ (greater than or equal to $7$) is equal to the sum of three prime numbers. This implies that every even number greater than or equal to $10$ is equal to the sum of $4$ primes. Then consider $n\geq 4$

$$2^n=[2^n-2(n-4)]+2(n-4)$$

We can write $2(n-4)=2+2+\dots+2$ as the sum of $n-4$ $2$'s. Since $2^n-2(n-4)\geq 10$ (and even) for all $n\geq 4$, we are assured that it can be written as the sum of $4$ primes. Since the cases $n\in\{1,2,3\}$ are easy to check, every power $2^n$ can be written as the sum of $n$ primes.

QC_QAOA
  • 11,796
1

Actually, it is not a very difficult problem. We just need a stronger form of Bertrand's postulate, that for every positive integer $n ≥ 8$ there is a prime between $n$ and $n·3/2$. This fact has been known for a long time, for example based on a theorem of Jitsuro Nagura that if $n ≥ 25$ then there is a prime between $n$ and $n·6/5$. For $n < 25$ check against the sequence of primes $11, 13, 17, 23, 31$.

Simply use induction to prove:

Every integer $n$ in the range $[2^k,2^{k+1})$ is a sum of exactly $k$ primes, for each positive integer $k$.

It is easy to check that this is true for $k ≤ 4$:

2 = 2      8 = 3+3+2   14 = 7+5+2     20 = 7+5+5+3    26 = 11+7+5+3
3 = 3      9 = 3+3+3   15 = 7+5+3     21 = 7+7+5+2    27 = 11+7+7+2
4 = 2+2   10 = 5+3+2   16 = 7+5+2+2   22 = 7+7+5+3    28 = 11+7+7+3
5 = 3+2   11 = 5+3+3   17 = 7+5+3+2   23 = 7+7+7+2    29 = 11+11+5+2
6 = 3+3   12 = 5+5+2   18 = 7+5+3+3   24 = 7+7+7+3    30 = 11+11+5+3
7 = 5+2   13 = 5+5+3   19 = 7+5+5+2   25 = 11+7+5+2   31 = 11+11+7+2

Now consider any $k ≥ 5$ and $n$ in the range $[2^k,2^{k+1})$. If $n ≤ 2^k+2^{k-2}$, let $p$ be a prime between $2^{k-2}$ and $2^{k-1}$ by Bertrand's postulate, and so $n-p$ is between $2^{k-1}$ and $2^k$. If $n > 2^k+2^{k-2}$, let $m = n-2^k ≥ 8$ and let $p$ be a prime between $m$ and $m·3/2$ by the above fact, and we also have $m·3/2 ≤ m+2^{k-1}$, so $n-p$ is between $2^{k-1}$ and $2^k$. In either case, $n-p$ is a sum of exactly $k-1$ primes by the induction, so $n$ is a sum of exactly $k$ primes.

So we not only prove the desired theorem, but something much stronger, for not much effort.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • Nice proof. Much more intuitive and elementary than appealing to the Weak Goldbach Conjecture – QC_QAOA Apr 16 '20 at 03:59
  • @QC_QAOA: Thank you for checking! I was left in the dark wondering whether I had made a mistake but could not see it. It's good to have your confirmation! =) – user21820 Apr 16 '20 at 04:15