Project Euler 120

Consider the quantity $(a-1)^n+(a+1)^n$ when divided by a^2. The remainder is a function of n, and attains a max for certain values of n. Call the maximal remainder r_max. Compute the sum of r_max over the range of 3<=a<=1000.

I had a lot of fun with this one, especially because unlike the other problems, it could be done without programming. There’s a lot of math, and it culminates in a simple formula for the answer. Well, ok, not so simple, but you could plug it into a calculator or WolframAlpha. Using the binomial theorem, we get

$(a-1)^n+(a+1)^n = \sum_{i=0}^{n}\binom{n}{i}(a)^{i}(-1)^{n-i}+\sum_{i=0}^{n}\binom{n}{i}(a)^{i}(1)^{n-i}$

$= \sum_{i=0}^{n}\binom{n}{i}a^{i}\left ( (-1)^{n-i}+1 \right )$

From this we immediately see that the half the terms are 0, which could have also been obvious since (a-1)^n will expand with alternating signs. But there is a larger insight: For all terms in which i >= 2, all have a nonzero integer quotient when divided by a^2, as evident from the presence of the a^i factor. Of the two surviving terms, as from the beginning of this paragraph, one is 0, thus

$(a-1)^n+(a+1)^n \hspace{2mm}(\mathrm{mod} \hspace{2 mm} a^{2})\equiv 2$ , if n is even and

$(a-1)^n+(a+1)^n \hspace{2mm}(\mathrm{mod} \hspace{2 mm} a^{2})\equiv 2na$ , if n is odd

In the range of “a” considered for the problem, any odd n produces a remainder larger than 2 when divided by a^2. Thus, it will not behoove us to consider even n. Our solution will consist of finding n so that 2na is as close possible to a^2, but not exceeding it. So consider the inequality 2na < a^2, or 2n < a. It will again be beneficial to consider the case of odds and evens.

If a is even, the value of n that satisfies the inequality is n = a/2 – 1, and the corresponding remainder is a^2 – 2a. (*)

If a is odd, the value of n that satisfies the inequality is n = (a-1)/2, and the corresponding remainder is a^2 – a. (**)

And that’s it! If we sum the expression (*) over the evens, and the expression (**) over the odds, in the range 3<=a<=1000, it will provide the answer, which is 333082500.

As an added bonus, let’s produce a more direct formula:

$\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)$