     (6 votes, average: 5.00 out of 5) Loading...

## Project Euler 123 Solution ## 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

• 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
Project Euler 123 Solution last updated

## Discussion

### 2 Responses to “Project Euler 123 Solution”

1. 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 PM
• You 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