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 4

^{3}+ 6^{3}= 280. 280 mod 25 = 5.The least value of n for which the remainder first exceeds 10

^{9}is 7037.Find the least value of n for which the remainder first exceeds 10

^{10}.

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 10^{10}. 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