The Goldbach Conjecture states that every even number greater than 2 can be expressed as a sum of two primes.
For example, 4=2+2 and 16 = 5 + 11.
What is the smallest number for which there are 5 different ways to express this number as a sum of two primes?
48 is the answer as seen below:
The first few numbers that can be done in at least 5 ways are given:
The sets below refer to:
Number, how many ways
The pairs of primes making up those ways
48 5
5 43 7 41 11 37 17 31 19 29
54 5
7 47 11 43 13 41 17 37 23 31
60 6
7 53 13 47 17 43 19 41 23 37 29 31
64 5
3 61 5 59 11 53 17 47 23 41
66 6
5 61 7 59 13 53 19 47 23 43 29 37
70 5
3 67 11 59 17 53 23 47 29 41
72 6
5 67 11 61 13 59 19 53 29 43 31 41
76 5
3 73 5 71 17 59 23 53 29 47
78 7
5 73 7 71 11 67 17 61 19 59 31 47 37 41
84 8
5 79 11 73 13 71 17 67 23 61 31 53 37 47 41 43
90 9
7 83 11 79 17 73 19 71 23 67 29 61 31 59 37 53 43 47
96 7
7 89 13 83 17 79 23 73 29 67 37 59 43 53
100 6
3 97 11 89 17 83 29 71 41 59 47 53
102 8
5 97 13 89 19 83 23 79 29 73 31 71 41 61 43 59
104 5
3 101 7 97 31 73 37 67 43 61
106 5
3 103 5 101 17 89 23 83 47 59
108 8
5 103 7 101 11 97 19 89 29 79 37 71 41 67 47 61
110 6
3 107 7 103 13 97 31 79 37 73 43 67
112 7
3 109 5 107 11 101 23 89 29 83 41 71 53 59
114 10
5 109 7 107 11 103 13 101 17 97 31 83 41 73 43 71 47 67 53 61
116 6
3 113 7 109 13 103 19 97 37 79 43 73
118 5
5 113 11 107 17 101 29 89 47 71
found by
10 for N=4 to 10000 step 2
20 P=3:Ct=0
30 while P<N/2
40 P2=N-P
50 if prmdiv(P2)=P2 then inc Ct
60 P=nxtprm(P)
70 wend
80 if Ct>4 then print N,Ct:inc SCt
81 :P=3:Ct=0
85 :while P<N/2
90 :P2=N-P
95 :if prmdiv(P2)=P2 then print P;P2;" ";:endif
100 :P=nxtprm(P)
105 :wend:print
185 if SCt>21 then end
190 next
To find the lowest number that can be accomplished in a given number of prime pairs:
10 for N=4 to 10000 step 2
20 P=3:Ct=0
30 while P<=N/2
40 P2=N-P
50 if prmdiv(P2)=P2 then inc Ct
60 P=nxtprm(P)
70 wend
80 if Ct>4 and Ct>Max then print N,Ct:inc SCt:Max=Ct
81 :P=3:Ct=0
85 :while P<=N/2
90 :P2=N-P
95 :if prmdiv(P2)=P2 then print P;P2;" ";:endif
100 :P=nxtprm(P)
105 :wend:print
185 if SCt>11 then end
190 next
Note that for example the lowest number that can be done in 11 ways is also the lowest that can be done in 12 ways, so there's no entry for 11:
The sets refer to:
Number, how many ways
The pairs of primes making up those ways
48 5
5 43 7 41 11 37 17 31 19 29
60 6
7 53 13 47 17 43 19 41 23 37 29 31
78 7
5 73 7 71 11 67 17 61 19 59 31 47 37 41
84 8
5 79 11 73 13 71 17 67 23 61 31 53 37 47 41 43
90 9
7 83 11 79 17 73 19 71 23 67 29 61 31 59 37 53 43 47
114 10
5 109 7 107 11 103 13 101 17 97 31 83 41 73 43 71 47 67 53 61
120 12
7 113 11 109 13 107 17 103 19 101 23 97 31 89 37 83 41 79 47 73 53 67 59 61
168 13
5 163 11 157 17 151 19 149 29 139 31 137 37 131 41 127 59 109 61 107 67 101 71 97 79 89
180 14
7 173 13 167 17 163 23 157 29 151 31 149 41 139 43 137 53 127 67 113 71 109 73 107 79 101 83 97
210 19
11 199 13 197 17 193 19 191 29 181 31 179 37 173 43 167 47 163 53 157 59 151 61 149 71 139 73 137 79 131 83 127 97 113 101 109 103 107
300 21
7 293 17 283 19 281 23 277 29 271 31 269 37 263 43 257 59 241 61 239 67 233 71 229 73 227 89 211 101 199 103 197 107 193 109 191 127 173 137 163 149 151
330 24
13 317 17 313 19 311 23 307 37 293 47 283 53 277 59 271 61 269 67 263 73 257 79 251 89 241 97 233 101 229 103 227 107 223 131 199 137 193 139 191 149 181 151 179 157 173 163 167
|
|
Posted by Charlie
on 2010-06-12 15:44:56 |
computer solution (spoiler)
