# Decomposition $2^k$ into a sum of primes

We know Goldbach's_conjecture. It concerns even numbers. However even numbers have many subsets.

My questions concern decomposition of specifically a number $2^k$ into a sum of two primes:

• Is $2^k$ always decomposable into a sum of two primes $p_1$ and $p_2$ when $k>2$?
• How to prove that?
(so far there is no proof for set of all even numbers, maybe there is for a some specific subset?)

(the third question at the end of the text)

I've prepared a small program for SymPy in order to check that and collected results in the table below.

Observe listed the sequence of the least prime numbers with property that when added to other prime number gives $2^k$

i.e. $2^k=p_1+p_2$.

($p_1$ - it is listed in the second column - in the first column $k$ is listed, in the third one a number of loops till prime is reached (see program below) is listed

so we have $2^3=3+5, \ 2^4=3+13, \ \dots \ 2^7=19+109 \$, ... etc..)

$\begin{bmatrix} 3 & 3 & 1 \\ 4 & 3 & 1 \\ 5 & 3 & 1 \\ 6 & 3 & 1 \\ 7 & 19 & 2 \\ 8 & 5 & 1 \\ 9 & 3 & 1 \\ 10 & 3 & 1 \\ 11 & 19 & 2 \\ 12 & 3 & 1 \\ 13 & 13 & 1 \\ 14 & 3 & 1 \\ 15 & 19 & 1 \\ 16 & 17 & 2 \\ 17 & 13 & 2 \\ 18 & 5 & 1 \\ 19 & 19 & 1 \\ 20 & 3 & 1 \\ 21 & 19 & 2 \\ 22 & 3 & 1 \\ 23 & 37 & 4 \\ 24 & 3 & 1 \\ 25 & 61 & 3 \\ 26 & 5 & 1 \\ 27 & 79 & 2 \\ 28 & 89 & 2 \\ 29 & 3 & 1 \\ 30 & 41 & 2 \\ 31 & 19 & 1 \\ 32 & 5 & 1 \\ 33 & 79 & 4 \\ 34 & 41 & 1 \\ 35 & 31 & 1 \\ 36 & 5 & 1 \\ 37 & 31 & 2 \\ 38 & 107 & 3 \\ 39 & 7 & 1 \\ 40 & 167 & 2 \\ 41 & 31 & 2 \\ 42 & 11 & 1 \\ 43 & 67 & 2 \\ 44 & 17 & 1 \\ 45 & 139 & 7 \\ 46 & 167 & 5 \\ 47 & 127 & 2 \\ 48 & 59 & 1 \\ 49 & 139 & 4 \\ 50 & 71 & 4 \\ 51 & 139 & 2 \\ 52 & 47 & 1 \\ 53 & 379 & 9 \\ 54 & 53 & 2 \\ 55 & 67 & 2 \\ 56 & 5 & 1 \\ 57 & 13 & 1 \\ 58 & 137 & 4 \\ 59 & 607 & 6 \\ 60 & 107 & 2 \\ 61 & 31 & 1 \\ 62 & 167 & 6 \\ \end{bmatrix}$

The sequence was obtained with the program (I believe it acts properly)

for k in range(3, 63):

diff=0
delta=2
level =0

while isprime(diff)==False:

level=level+1
p= prevprime(2**k-delta)
diff= (2**k)-p

if isprime(diff)==False:

delta=diff
else:
break

print  "%d  &  %d  &  %d \\\\ " % (k, diff, level)


Additionally although the reference numbers $2^k$ are quite big the mentioned least prime numbers $p_1$ are rather small, probably the pattern is continuing for bigger $k$ ..

• Can we say something about upper bound for such numbers ? Does some $2^m$, where $m=f(k)$, limit them?
• How is 19+107=126 a power of 2? – Oscar Lanzi May 25 '18 at 9:30
• Typo, should be 19+109 – Widawensen May 25 '18 at 9:32
• To find a heuristical bound should be feasible, but I think Goldbach's conjecture is also open for the powers of $2$ – Peter May 25 '18 at 11:23
• @Widawensen Are you interested in a larger list ? – Peter May 25 '18 at 11:24
• For $k\le 1\ 000$, if $p$ denotes the smallest prime doing the job, we have $p<k^{1.58}$. But this is only an empirical bound. – Peter May 25 '18 at 11:33

The following PARI/GP program shows the first $300$ numbers (The first two lines show the self-defined function) Remark : For the sake of speed, I only applied the BPSW-test, which is very reliable.

? check
%17 = (m)->n=2^m;p=2;while(ispseudoprime(n-p)==0,p=nextprime(p+1));p
? for(j=2,300,print(j,"   ",check(j)))
2   2
3   3
4   3
5   3
6   3
7   19
8   5
9   3
10   3
11   19
12   3
13   13
14   3
15   19
16   17
17   13
18   5
19   19
20   3
21   19
22   3
23   37
24   3
25   61
26   5
27   79
28   89
29   3
30   41
31   19
32   5
33   79
34   41
35   31
36   5
37   31
38   107
39   7
40   167
41   31
42   11
43   67
44   17
45   139
46   167
47   127
48   59
49   139
50   71
51   139
52   47
53   379
54   53
55   67
56   5
57   13
58   137
59   607
60   107
61   31
62   167
63   409
64   59
65   79
66   5
67   19
68   23
69   19
70   71
71   577
72   107
73   181
74   257
75   97
76   347
77   43
78   11
79   67
80   317
81   163
82   113
83   97
84   563
85   19
86   41
87   67
88   563
89   31
90   41
91   619
92   83
93   79
94   3
95   37
96   17
97   349
98   107
99   1231
100   479
101   619
102   1277
103   97
104   17
105   13
106   431
107   919
108   59
109   31
110   443
111   37
112   269
113   211
114   11
115   67
116   3
117   373
118   5
119   1069
120   1049
121   73
122   3
123   67
124   59
125   853
126   137
127   577
128   173
129   613
130   5
131   181
132   347
133   103
134   197
135   409
136   113
137   13
138   983
139   397
140   773
141   103
142   887
143   127
144   83
145   151
146   1013
147   1777
148   167
149   31
150   3
151   829
152   17
153   2011
154   773
155   31
156   167
157   19
158   1571
159   241
160   47
161   709
162   101
163   577
164   1307
165   61
166   5
167   577
168   257
169   643
170   761
171   19
172   227
173   103
174   3
175   229
176   233
177   619
178   41
179   1669
180   47
181   199
182   233
183   2239
184   59
185   1879
186   677
187   1951
188   167
189   1129
190   11
191   19
192   1409
193   31
194   317
195   1201
196   47
197   439
198   17
199   1021
200   383
201   313
202   977
203   271
204   167
205   229
206   5
207   157
208   563
209   439
210   47
211   601
212   23
213   3
214   743
215   157
216   479
217   61
218   233
219   277
220   167
221   3
222   263
223   1621
224   719
225   103
226   5
227   2017
228   149
229   733
230   2063
231   439
232   1163
233   3
234   83
235   151
236   569
237   181
238   383
239   199
240   467
241   2113
242   281
243   31
244   1289
245   163
246   107
247   571
248   887
249   1021
250   2111
251   619
252   839
253   421
254   521
255   19
256   587
257   1861
258   2411
259   1069
260   149
261   223
262   71
263   1297
264   4349
265   139
266   3
267   1381
268   719
269   241
270   53
271   967
272   2543
273   1321
274   2531
275   199
276   89
277   103
278   653
279   751
280   47
281   139
282   83
283   3967
284   173
285   1879
286   521
287   937
288   167
289   1489
290   47
291   19
292   167
293   601
294   1301
295   421
296   1709
297   619
298   953
299   2521
300   383
?


If we define $$r:=\frac{\ln(p)}{\ln(m)}$$ where $p$ is the smallest prime doing the job and $m$ the exponent in the power of $2$, then the hard cases ($r> 1.5$) upto $m=1\ 000$ are :

? check
%14 = (m)->n=2^m;p=2;while(ispseudoprime(n-p)==0,p=nextprime(p+1));log(p)/log(m)

? maxi=0;for(s=2,1000,r=check(s);if(r>1.5,print(s,"      ",r)))
7      1.513142310602514647614827827
59      1.571666448002255509959688695
99      1.548508495589302173521881338
102      1.546445599742583725469041828
153      1.512072608515003505693123572
264      1.502470890179106899253261957
?

• It's always encouraging to see that results obtained with different calculations confirmed also my (smaller) range :) Thank you Peter.. – Widawensen May 25 '18 at 12:14
• It seems that the limit in infinity is $3/2$ ... – Widawensen May 25 '18 at 12:19
• Another interesting category would be the smallest prime doing the job. For the exponent $1\ 105$ it is $32\ 323$ , currently the champion in my search. – Peter May 25 '18 at 12:37
• Also, I found no "hard case" yet beyond exponent $1\ 000$. But exponent $1\ 527$, the new champion with prime $50\ 377$ , comes close. – Peter May 25 '18 at 12:40
• New champion : Exponent $1\ 824$ , prime $58\ 937$ – Peter May 25 '18 at 12:58