Euler Problem 120 asks:
Let r be the remainder when (a-1)n + (a+1)n is divided by a2.
For example, if a = 7 and n = 3, then r = 42:
- 63 + 83 = 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), 2an is evenly divisible by a2. The remainders are thus 2 for even n and 2an for odd n respectively. How big can n grow? Such that 2an stays less than a2, or 2n is less than a. Otherwise, a2 divides one more time.
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 pattern is true for all…”
…mrt