HMMT 十一月 2023 · 团队赛 · 第 9 题

HMMT November 2023 — Team Round — Problem 9

[60] Let r denote the remainder when is divided by 8 . Compute r + 2 r + 3 r + · · · + 63 r . k 1 2 3 63 k

解析

[60] Let r denote the remainder when is divided by 8. Compute r + 2 r + 3 r + · · · + 63 r . k 1 2 3 63 k Proposed by: Rishabh Das Answer: 8096 128 − k Solution: Let p = , so k k 127 = p p · · · p . 1 2 k k 96 Now, for k ≤ 63, unless 32 | gcd( k, 128 − k ) = gcd( k, 128), p ≡ − 1 (mod 8). We have p = = 3. k 32 32 Thus, we have the following characterization:  1 if k is even and k ≤ 31     7 if k is odd and k ≤ 31 r = k  5 if k is even and k ≥ 32    3 if k is odd and k ≥ 32 . We can evaluate this sum as 4 · (0 + 1 + 2 + 3 + · · · + 63)

3 · ( − 0 + 1 − 2 + 3 − · · · − 30 + 31)
(32 − 33 + 34 − 35 + · · · + 62 − 63) = 4 · 2016 + 3 · 16 + ( − 16) = 8064 + 32 = 8096 .