Project Euler 120: Find the max remainder when (a − 1)^{n} + (a + 1)^{n} is divided by a^{2}
Project Euler 120 Problem Description
Let r be the remainder when (a−1)^{n} + (a+1)^{n} is divided by a^{2}.
For example, if a = 7 and n = 3, then r = 42: 6^{3} + 8^{3} = 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:
Odd n: 1, 3, 5, 7  Even n: 2, 4, 6, 8 
2a  2a^{2} + 2 
2a^{3} + 6a  2a^{4} + 12a^{2} + 2 
2a^{5} + 20a^{3} + 10a  2a^{6} + 30a^{4} + 30a^{2} + 2 
2a^{7} + 42a^{5} + 70a^{3} + 14a  2a^{8} + 56a^{6} + 14a^{4} + 56a^{2} + 2 
The last term becomes the remainder since the other terms are divisible by a^{2}. 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 (a2)*a and for odd a would be (a1)*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((a1)//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
Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 120 Solution Python 2.7 source.
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_{3}=1, n_{4}=1, n_{5}=7, n_{6}=5, n_{7}=n_{3}+2, n_{8}=n_{4}+2, n_{9}=n_{5}+6, n_{10}=n_{6}+4, n_{11}=n_{6}+2, n_{12}=n_{7}+2, n_{13}=n_{8}+6, n_{14}=n_{9}+4, …  Gratuitous table of r_{max} note the odd r_{max} = a^{2}−a, even r_{max} = a^{2}−2a


Discussion
No comments yet.