# Euler Problem 120

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:

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

This is true for all even n.

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

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.

Sub Problem_120()
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
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

Posted in Uncategorized

## 2 thoughts on “Euler Problem 120”

1. fzz says:

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

2. Michael says:

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

Posting code? Use <pre> tags for VBA and <code> tags for inline.