(9 votes, average: 5.00 out of 5)

## Project Euler 120: Find the max remainder when (a − 1)n + (a + 1)n is divided by a2

#### Project Euler 120 Problem Description

Let r be the remainder when (a−1)n + (a+1)n is divided by a2.

For example, if a = 7 and n = 3, then r = 42: 63 + 83 = 728 ≡ 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

For 3 ≤ a ≤ 1000, find ∑ rmax.

#### Analysis

A little investigation proves that for any value of a and any even value of n the remainder will always be 2. For odd values of n the remainder will be 2an. This remove’s any requirement to consider even n for a maximum remainder.

You can expand the polynomial for the first 8 values of n to get an idea of how this works:

 Odd n: 1, 3, 5, 7 Even n: 2, 4, 6, 8 2a 2a2 + 2 2a3 + 6a 2a4 + 12a2 + 2 2a5 + 20a3 + 10a 2a6 + 30a4 + 30a2 + 2 2a7 + 42a5 + 70a3 + 14a 2a8 + 56a6 + 14a4 + 56a2 + 2

The last term becomes the remainder since the other terms are divisible by a2. Now we need to calculate which odd values of n will yield the largest remainder. This will save having to iterate different values of n.

We want to make 2n as close to a as possible; note that for even a the max remainder would be (a-2)*a and for odd a would be (a-1)*a. This is the same as rmax = (a−1) // 2 * 2 * a. So iterating through the range of a values we can accumulate the sum easily.

print sum((a-1)//2 * 2 * a for a in range(3, 1001))

An even easier way would be to use the formula that calculates the sum (source: Project Euler 120, Ben “beignet” Yey):

$\sum_{a=4, a\hspace{1mm}\mathrm{ even}}^{1000}(a^{2}-2a) \hspace{1mm} + \sum_{a=3,a\hspace{1mm}\mathrm{odd}}^{999}(a^{2}-a)$

$\sum_{a=3}^{1000}a^{2}\hspace{1mm}- \sum_{a=3}^{1000}a\hspace{1mm}-\sum_{a=4, a\hspace{1mm}\mathrm{even}}^{1000}a$
$\left[\sum_{i=1}^{1000}a^{2}\hspace{1mm}-(1+4)\right]- \sum_{i=3}^{1000}a\hspace{1mm}-2\sum_{i=2}^{500}a$
$\left[\frac{1000(1001)(2001)}{6}-5\right]-\frac{998(1003)}{2}-2\frac{499(502)}{2}$

#### Project Euler 120 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 120 Solution Python 2.7 source.