Home » Problem sets » Project Euler » Project Euler 120

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)

= \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}

Such an expression you can just plug into a calculator to get the same result.

Advertisements

One thought on “Project Euler 120

  1. Pingback: Project Euler 120 Solution: Square remainders

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s