Consider the quantity 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
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
, if n is even and
, 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:
Such an expression you can just plug into a calculator to get the same result.
Pingback: Project Euler 120 Solution: Square remainders