What is the smallest integer that can be expressed as a sum of consecutive primes in 3 different ways?
The program (at the bottom) was designed to use only up to the 50th prime. That means that in order to insure completeness for all reported numbers, those numbers should not exceed 456, as the sum of the 49th and 50th primes. Also, as a further consequence, only a running count for up to 18 primes would be necessary, as 19 or more consecutive primes would add up to more than 456.
The intended answer is probably 240, as:
240 = 17+19+23+29+31+37+41+43
= 53+59+61+67
= 113+127
This is reported as the entry below:
240
7 14: 17 19 23 29 31 37 41 43
16 19: 53 59 61 67
30 31: 113 127
where the numbers before the colon refer to the ordinality of the primes that follow; for example 17 is the 7th prime and 43 is the 14th.
287 would be the next such number.
In the entries below, those in which the target number is also prime are marked with **. That's to indicate that the number itself could be considered a degenerate "sum" of consecutive primes. If that were done, 41 would be the lowest, as there are two other sums of consecuteve primes that add up to 41.
Interestingly 311 has four sums of actual consecutive primes that add up to it, plus it is itself prime, giving a 5th, degenerate, sum.
41 **
1 6: 2 3 5 7 11 13
5 7: 11 13 17
83 **
5 9: 11 13 17 19 23
9 11: 23 29 31
197 **
1 12: 2 3 5 7 11 13 17 19 23 29 31 37
7 13: 17 19 23 29 31 37 41
199 **
11 15: 31 37 41 43 47
18 20: 61 67 71
223 **
8 14: 19 23 29 31 37 41 43
20 22: 71 73 79
240
7 14: 17 19 23 29 31 37 41 43
16 19: 53 59 61 67
30 31: 113 127
251 **
9 15: 23 29 31 37 41 43 47
22 24: 79 83 89
281 **
1 14: 2 3 5 7 11 13 17 19 23 29 31 37 41 43
10 16: 29 31 37 41 43 47 53
287
7 15: 17 19 23 29 31 37 41 43 47
15 19: 47 53 59 61 67
24 26: 89 97 101
311 **
5 15: 11 13 17 19 23 29 31 37 41 43 47
11 17: 31 37 41 43 47 53 59
16 20: 53 59 61 67 71
26 28: 101 103 107
340
7 16: 17 19 23 29 31 37 41 43 47 53
10 17: 29 31 37 41 43 47 53 59
39 40: 167 173
371
4 16: 7 11 13 17 19 23 29 31 37 41 43 47 53
13 19: 41 43 47 53 59 61 67
30 32: 113 127 131
401 **
10 18: 29 31 37 41 43 47 53 59 61
14 20: 43 47 53 59 61 67 71
439 **
11 19: 31 37 41 43 47 53 59 61 67
34 36: 139 149 151
DefDbl A-Z
Dim crlf$
Private Sub Form_Load()
Text1.Text = ""
crlf$ = Chr(13) + Chr(10)
Form1.Visible = True
hiPrime = 50
maxGoal = prm(hiPrime - 1) + prm(hiPrime)
maxCt = 0
While tot <= maxGoal
maxCt = maxCt + 1
tot = tot + prm(maxCt)
Wend
Text1.Text = Text1.Text & maxCt & Str(maxGoal) & crlf
ReDim totPrm(maxCt), ways(maxGoal, 10, 2)
For p = 1 To hiPrime
For i = 2 To maxCt
totPrm(i) = totPrm(i) + prm(p)
prevP = p - i
If prevP > 0 Then
totPrm(i) = totPrm(i) - prm(prevP)
End If
If p >= i Then
goal = totPrm(i)
If goal <= maxGoal Then
ways(goal, 0, 0) = ways(goal, 0, 0) + 1
s = ways(goal, 0, 0)
ways(goal, s, 1) = prevP + 1
ways(goal, s, 2) = p
End If
End If
Next
Next p
For i = 1 To maxGoal
If ways(i, 0, 0) > 2 Or prmdiv(i) = i And ways(i, 0, 0) > 1 Then
Text1.Text = Text1.Text & i
If prmdiv(i) = i Then Text1.Text = Text1.Text & " **"
Text1.Text = Text1.Text & crlf
For j = 1 To ways(i, 0, 0)
Text1.Text = Text1.Text & ways(i, j, 1) & Str(ways(i, j, 2)) & ": "
For k = ways(i, j, 1) To ways(i, j, 2)
Text1.Text = Text1.Text & Str(prm(k))
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf
End If
Next
End Sub
Function prm(i)
Dim p As Long
Open "17-bit primes.bin" For Random As #111 Len = 4
Get #111, i, p
prm = p
Close 111
End Function
Function prmdiv(num)
Dim n, dv, q
If num = 1 Then prmdiv = 1: Exit Function
n = Abs(num): If n > 0 Then limit = Sqr(n) Else limit = 0
If limit <> Int(limit) Then limit = Int(limit + 1)
dv = 2: GoSub DivideIt
dv = 3: GoSub DivideIt
dv = 5: GoSub DivideIt
dv = 7
Do Until dv > limit
GoSub DivideIt: dv = dv + 4 '11
GoSub DivideIt: dv = dv + 2 '13
GoSub DivideIt: dv = dv + 4 '17
GoSub DivideIt: dv = dv + 2 '19
GoSub DivideIt: dv = dv + 4 '23
GoSub DivideIt: dv = dv + 6 '29
GoSub DivideIt: dv = dv + 2 '31
GoSub DivideIt: dv = dv + 6 '37
Loop
If n > 1 Then prmdiv = n
Exit Function
DivideIt:
Do
q = Int(n / dv)
If q * dv = n And n > 0 Then
prmdiv = dv: Exit Function
Else
Exit Do
End If
Loop
Return
End Function
|
Posted by Charlie
on 2015-03-08 12:53:52 |