Loading...
Project Euler 123: Maximize the remainder when (p−1)n + (p+1)n is divided by p2 for prime p
Project Euler 123 Problem Description
Project Euler 123: Let pn be the nth prime: 2, 3, 5, 7, 11, …, and let r be the remainder when (pn−1)n + (pn+1)n is divided by pn2.
For example, when n = 3, p3 = 5, and 43 + 63 = 280 ≡ 5 mod 25.
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.
Analysis
Using much of our understanding from solving Problem 120, we are able to easily adapt those methods to solve this problem. The differences are as follows:
- No even numbers to deal with so the rmax is simply 2npn.
- We’re looking for a limit as opposed to summing a range.
- No algebraic solution.
We can make an educated guess of how many primes we’ll need by applying the remainder formula to a sufficiently large prime number and check that the results exceeds our target I (1010 in this case). So, I guessed by using a list of primes at the 22044th prime number 249,989 with a remainder of 2*22044*249989 = 11021515032. That’s greater than 1010 and will suffice.
Project Euler 123 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 123 Solution Python 2.7 source.
Afterthoughts
- See also, Project Euler 120 Solution:
- We can start checking with the 7039th prime number as clued by the problem’s example.
- Added a cell to the beginning of the primes array to force the starting base to 1.
- The starting value for ni must be an odd number.
- There a lot you could do to improve this solution, like:
binary search
calculate starting and ending search indexes
The 21034th prime is 237733.
This results in r = 2*21034*237733 = 10000951844.
Why isn’t the solution 21034?
Posted by Selenae | January 25, 2015, 8:10 PMYou will find that for any even n the remainder of (pn−1)n + (pn+1)n when divided by p2 is always 2. When n is odd, the remainder for the nth prime Pn is 2*n*Pn. This formula is only relevant for odd n and so we only consider such.
Hope this helps.
Posted by Mike Molony | January 27, 2015, 11:54 AM