Project Euler 120: Find the max remainder when (a − 1)ⁿ + (a + 1)ⁿ is divided by a²

Project Euler 120 Problem Description

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

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

For 3 ≤ a ≤ 1000, find ∑ r_max.

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:

The last term becomes the remainder since the other terms are divisible by a². 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 r_max = (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):

Project Euler 120 Solution

Afterthoughts

• See also, Project Euler 123 Solution:
  
• To solve this problem we do not require to consider values of n.
  
• But, if we ever need to find which value of n yeilds a maximum remainder, we could expand the following series:
  n₃=1, n₄=1, n₅=7, n₆=5, n₇=n₃+2, n₈=n₄+2, n₉=n₅+6, n₁₀=n₆+4, n₁₁=n₆+2, n₁₂=n₇+2, n₁₃=n₈+6, n₁₄=n₉+4, …
  
• Gratuitous table of r_max note the odd r_max = a²−a, even r_max = a²−2a