Euler Problem 120 asks:

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- 728 mod 49 = 42
And as n varies, so too will r, but for a = 7 it turns out that r_max = 42.

For 3 <= a <= 1000, find Sum(r_max).

All my brute force attempts to solve this problem overflowed whatever variable type I used, from longs through currency through decimal variants through doubles. Another approach was needed, and Isacc Newton had it figured out in his binomial theorem, which gives the expansion of *(x+y) ^{n}*.

Four examples:

1 2 3 4 5 6 |
<ol> <li>(a+1)<sup>2</sup> = a<sup>2</sup>+2a+1</li> <li>(a-1)<sup>2</sup> = a<sup>2</sup>-2a+1</li> <li>(a+1)<sup>3</sup> = a<sup>3</sup>+3a<sup>2</sup>+3a+1</li> <li>(a-1)<sup>3</sup> = a<sup>3</sup>-3a<sup>2</sup>+3a-1</li> </ol> |

Adding equations (1) and (2) together, which have *n = 2*, gives

1 2 3 |
<ol start="5"> <li>(a+1)<sup>n</sup> + (a-1)<sup>n</sup>= 2a<sup>n</sup>+2</li> </ol> |

This is true for all even n.

Adding equations (3) and (4) together, which have *n = 3*, gives

1 2 3 4 |
<ol start="6"> <li>(a+1)<sup>3</sup> + (a-1)<sup>3</sup> = 2a<sup>3</sup> + 6a</li> <li>2a<sup>3</sup> + 6a = 2a<sup>n</sup> + 2an</li> </ol> |

This is true for all odd n.

Within equations (5) and (7), *2a ^{n}* is evenly divisible by

*a*. The remainders are thus

^{2}*2 for even n*and

*2an for odd n*respectively. How big can

*n*grow? Such that

*2an*stays less than

*a*, or

^{2}*2n*is less than

*a*. Otherwise,

*a*divides one more time.

^{2}Looping through *a = 3* to *a = 1000* and summing *2an* provides the answer. This simple code does that. It runs in a blink.

Dim Answer As Long, T As Single

Dim a As Long, n As Long

T = Timer

For a = 3 To 1000

n = 2

While 2 * n LT a

n = n + 1

Wend

n = n – 1 ‘ went 1 too far

Answer = Answer + 2 * a * n

Next a

Debug.Print Answer; ” Time:”; Timer – T

End Sub

The usual angle bracket adjustment is in the code. Next week, I’ll put up Problem 123, which uses this same approach, but with *a* as prime numbers.

…mrt

This is one Euler problen that could be solved with a single worksheet formula. Your inner While…Wend loop is unnecessary. You’re finding the largest even number strictly less than a. That doesn’t require a loop. For odd a, it’s a-1, and for even a it’s a-2. Both can be combined into a – 2 + (a Mod 2). Or as a worksheet formula,

=SUMPRODUCT(ROW(3:1000)*(ROW(3:1000)-2+MOD(ROW(3:1000),2)))

Hi fzz –

Thanks. Yep, the 5 lines from n = 2 to n = n – 1 can be replaced with the single line

n = (a – 1)2

which makes the simple code even simpler ;-)

I didn’t adequately express my thoughts above: 2x it should be “This

patternis true for all…”…mrt