Euler Problem 120

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:

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

Posted in Uncategorized

2 thoughts on “Euler Problem 120

  1. 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. 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

Leave a Reply

Your email address will not be published. Required fields are marked *