Euler Problem 123 asks:
Let p(n) be the nth prime: 2, 3, 5, 7, 11, …, and let r be the remainder when (p(n)-1)n + (p(n)+1)n is divided by p(n)2.
For example, when n = 3, p(3) = 5, and 43 + 63 = 280. 280 mod 25 = 5.
The least value of n for which the remainder first exceeds 109 is 7037.
Find the least value of n for which the remainder first exceeds 1010.
This is really the same problem as Euler 120 (posted last week) with p(n) taking the part of a. We are looking for 2*p(n)*n greater than 1010. I built a collection of the first 7037 primes, and then added primes one-by-one to the collection until the remainder was large enough, with the caveat that even n gives a remainder of 2, so we need an odd n.
All prime numbers beyond 3 lie left or right of an even multiple of six so a prime-checking routine need only check whether or not n mod 6 = 1 or 5 has even divisors, and even then, only up to the square root of n.
Here is the code that does that. The routine runs in about 2.5 seconds.
Dim Answer As Long, T As Single
Dim n As Long, i As Long, R As Double
Dim p As New Collection
T = Timer
p.Add Item:=2, Key:=“2” ‘1st Prime
n = 1
i = 3
Do
If IsPrime3(i) Then
p.Add Item:=i, Key:=CStr(i)
n = n + 1
End If
i = i + 2
Loop Until n = 7037 ‘Primes in p
Do
If n Mod 2 = 0 Then
R = 2
Else
R = 2 * p.Item(n) * n
End If
If R GT 10 ^ 10 Then
Answer = n
Exit Do
End If
i = p.Item(n) + 2
Do Until IsPrime3(i)
i = i + 2
Loop
n = n + 1
p.Add Item:=i, Key:=CStr(i)
Loop
Debug.Print Answer; ” Time:”; Timer – T, p.Item(Answer), R
End Sub
Function IsPrime3(Num As Variant) As Boolean
Dim i As Long
If Num != Int(Num) Then
Exit Function ‘IsPrime = False
Else
Num = CDec(Num)
End If
If Num LT 2 Then Exit Function ‘IsPrime = False
If Num = 2 Then
IsPrime3 = True
Exit Function
End If
If Num = 3 Then
IsPrime3 = True
Exit Function
End If
Select Case Num Mod 6
Case 1, 5
For i = 3 To Sqr(Num) Step 2
If Num Mod i = 0 Then Exit Function ‘IsPrime = False
Next i
Case Else
Exit Function ‘IsPrime = False
End Select
IsPrime3 = True
End Function
Dick has more on prime numbers here. The usual angle bracket corrections are in the above.
…mrt
If you can accept using a fair amount of RAM, it’d be a lot faster to use the Sieve of Eratosthenes to generate the necessary primes rather than determine sequential primes.
Start with the insight from Euler problem 120, that for odd a, rmax = a * (a – 1). Then note that the prime number in question would fall between 10^5 and 10^5 + 100. So generate an array containing the odd integers from 3 to 100,099, use the Sieve of Eratosthenes to reduce it down to the odd primes 1E10.
The following runs in less than less than a second.
Const IMAX As Long = 50049
Const TRGT As Double = 10000000000#
Dim dt As Double
Dim p() As Long
Dim i As Long, j As Long, k As Long, n As Long
dt = Timer
ReDim p(1 To IMAX)
‘populate array of sequential odd integers 3..100099
k = 1
For i = 1 To IMAX
k = k + 2
p(i) = k
Next i
‘Sieve of Eratasthones
n = 2 * IMAX + 1
For i = 1 To Sqr(n)
j = p(i)
If j .GT. 0 Then
For k = 3 * j To n Step 2 * j
p(k 2) = 0
Next k
End If
Next i
‘find the smallest prime with rmax > TRGT
n = 2
For i = 2 To IMAX
k = p(i)
If k .GT. 0 Then
n = n + 1
If CDbl(k) * CDbl(k – 1) .GT. TRGT Then Exit For
End If
Next i
Debug.Print n, k, CDbl(k) * CDbl(k – 1), Timer – dt
Erase p
End Sub
Your code gives incorrect results.
Hi fzz –
Incorrect results? Which one? The Answer checks in as correct, the prime number it returns is the correct nth prime for that answer per
http://primes.utm.edu/lists/small/100000.txt
and 2*thePrime*theAnswer is the same as my spreadsheet solution gave.
…mrt
Sorry. Your results are correct. I misread the specs, misbelieving that the goal was the maximum remainder for p(n) rather than the remainder specifically when p(n) -/+ 1 are raised to the nth power.
Still, an approach based on the Sieve of Eratasthones (if you have the RAM) is a lot faster than your approach.
Hi fzz –
No trouble. Reading the problem wrong is an occupational hazard for Eulerites (Eulerians?). More than once I’ve come back to a problem when stuck only to see I was trying to check in the wrong part of the process as the answer. That differs from the times when I read the question right and just flat have a wrong answer ;-)
And stuck right now is my usual position. Anybody done #83 please speak up! Being able to go backwards puts me in a infinite loop of minimum cells. I’ve got a conceptual gap. Euler said it’s harder, and I attest that it is.
…mrt
Hi Michael,
I too have become addicted to Project Euler, having first learned about it on this site. I’ve learned an awful lot about VBA just by doing those problems. That said, I agree with fzz that the Sieve of Eratasthones is generally the best way to find prime numbers, especially when the upper bound is under a few million.
As for Problem 83, I’d be happy to offer as much or as little help as you like. A couple of questions: What approach have you taken so far? Did you solve 81 and 82? How? I solved all three problems with basically the same algorithm.
Josh
Hi Josh –
I have done #81. I’ll post it this weekend, and give you a chance to chime in there. My approach was basically the same as I used for #67 to do #81, swapping min for max, but moving it on to #83 eludes me at the moment.
So thanks, and stay tuned!
…mrt (who was just waiting for fzz to write a sieve for him ;-) )
I did problem 83 with VBA (which I’m not going to post because the code is a mess), then it occurred to me that it could be done neatly using a simple circular reference.
The procedure is:
1. Open the data as a worksheet (re-name matrix.txt to matrix.csv is a quick way)
2. Insert a blank column to the left, and blank row above the data, so the data range is B2:CC81
3. Set up the worksheet to allow iterative calculation, with 1 iteration, and set calculation to manual.
4. In cell A83 enter 0.
5. Set up an 80×80 table (say in B85:CC164) below the matrix containing the minimum sum to reach any cell:
in cell B85 enter +B2
In cell C86: =+C3+IF($A$83,MIN(B86,C85,D86,C87),B86)
Copy C86 to C86:CB163
In cell C85: =+C2+IF($A$83,MIN(B85,D85,C86),B85) Copy to C85:CB85
In cell CC85: =+CC2+IF($A$83,MIN(CB85,CD85),CB85)
In cell B86: =+B3+IF($A$83,MIN(B85,C86,B87),B85) Copy to B86:B163
In cell B164: =+B81+IF($A$83,MIN(B163,C164),B163)
In cell C164: =+C81+IF($A$83,MIN(B164,C163,D164),B164) Copy to C164:CB164
In cell CC86: =+CC3+IF($A$83,MIN(CB86,CC85,CC87),CB86) Copy to CC86:CC163
In cell CC164: =+CC81+IF($A$83,MIN(CB164,CC163),CB164)
6: Press F9, then enter 1 in cell A83
7: Press F9 (calc) three times.
8: The answer is in cell CC164
An alternative would be to enter a large number (say 1,000,000) in the columns and rows around the range B85:CC164, then use the same formula (as in C86) everywhere except B85.
My VBA essentially used the same technique, and solved near instantaneously.
Hi Doug –
Yep. It’s those circular references that I can’t get my mind around. Thanks for showing an approach. It certainly ought to be doable in a spreadsheet!
…mrt
Michael – I just looked at the Project Euler forum and see that the first correct solution used Excel, using essentially the same method as I described.
One simplification is that the Min function ignores blank cells, so you can in fact use the same formula all over, and don’t need to adjust it for the edges and corners, or enter big numbers all around the boundaries.
My method has one improvement in that I initially use a specified cell, with non-circular references, to seed the values used in the circular references, rather than using the circular reference from the first iteration. This converges much more rapidly (i.e. 3 iterations, rather than hundreds).
Hi Doug –
Thank you. It truly never occurred to me that I wanted to be in loop like that. My strategy was to weight the cell I was in so heavily that it would never again be a minimum, and never again visited.
I didn’t succeed. Many times ;-)
…mrt
I am truly amazed at many of the spreadsheet-only solutions that people post. My first instinct is generally to go straight to VBA, and setting up circular references in the spreadsheet never would have occurred to me. I used the (Named) Algorithm also used by many other people in the PE forum and while I learned a new algorithm, I think I would have learned more about Excel from the above method. Now to attempt to wrap my mind around the above method…
-Josh
Hi Josh –
I set up Doug’s example (actually both of them) and I don’t which is the greater insight: to create a second matrix or to iterate. Neat stuff.
I did something wrong…it takes me 4(!) loops to do the first, and interestingly, 5 to do the second. That turns out to be when the lower right is stable. Maybe Doug knows why the difference. It takes 11 or 12 tries before everything is stable.
I coded up the second method. The seeding Doug mentioned is important. When I did it badly, it took over a minute to calculate and 1218 loops. With the seeds, 3/10’s of a second, and those 5 loops. I’ll post it when I get the time. Needs some cleanup.
…mrt