Euler Problem 123

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.

Sub Problem_123()
   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

Posted in Uncategorized

12 thoughts on “Euler Problem 123

  1. 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.

    Sub euler123()
      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.

  2. 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.

  3. 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

  4. 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

  5. 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 ;-) )

  6. 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.

  7. 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

  8. 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).

  9. 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

  10. 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

  11. 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

Leave a Reply

Your email address will not be published. Required fields are marked *