## Project Euler 123: Maximize the remainder when (p−1)^{n} + (p+1)^{n} is divided by p^{2} for prime p

#### Project Euler 123 Problem Description

Project Euler 123: Let `p`_{n} be the `n`th 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 ≡ 5 mod 25.

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

#### 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 r
_{max}is simply 2np_{n}. - 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 (10^{10} in this case). So, I guessed by using a list of primes at the 22044^{th} prime number 249,989 with a remainder of 2*22044*249989 = 11021515032. That’s greater than 10^{10} 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 7039
^{th}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*

The 21034th prime is 237733.

This results in r = 2*21034*237733 = 10000951844.

Why isn’t the solution 21034?

You will find that for any even n the remainder of (p

_{n}−1)^{n}+ (p_{n}+1)^{n}when divided by p^{2}is always 2. When n is odd, the remainder for the nth prime P_{n}is 2*n*P_{n}. This formula is only relevant for odd n and so we only consider such.Hope this helps.