Consider the sum 1^99 + 2^99 + 3^99 + ... + 99^99.
Finding the last digit of this sum was the task of an old problem
Last Digit. With a clever setup finding the last two digits was just as easy.
So I present a higher challenge: find the last four digits. No computer programs!
Consider pairing the first with the last, the second with the penultimate, etc (but sadly 50^99 will not have a buddy):
a^99 + (100a)^99
The latter has 100 terms, but they all have a factor of 100^k. So the first 98 terms all have 0000 as the last 4 digits. The only contribution to the last 4 digits is from:
a^99 + 99*100*a^98  a^99
We need consider only the Sum (from a=1 to 49) of 9900*a^98 + 50^99.
But 50^99 ends with many zeros so we can ignore that term.
The problem is now 9900 times the sum of the first 49 98th powers instead of the sum of the first 99 99th powers.
Do it again.
a^98 + (50a)^98
a^98  (98*97/2)*50^2*a^96 + 98*50*a^97  a^98
Note that the term (98*97*96/6)*50**3 * a^95 has more than 4 terminal zeros.
Simplify to
98*50 * (a^97  97*25*a^96)
So we have the sum from a=1 to a=24 of the above expression plus the lonely unpaired term 25^98
Note that 98*50 ends in 2 zeros and we are multiplying this entire bit by 9900, so all the terms fall out with at least 4 terminal zeros except for 25^98
The first several powers of 25 end in:
1 0025
2 0625
3 5625
4 0625
5 5625
6 0625
7 5625
8 0625
So 25^98 ends with 0625
9900 * 0625 ends in 7500
 verified by program below
ans = 0
for n in range(1,100):
ans += n**99
ans = ans % 10000 # also works with this line commented out
print(str(ans)[4:])
Output: 7500

Posted by Larry
on 20240417 08:25:46 