Sum of $x^x$ final 10 digits

Question

Warning/spoiler alert

This problem occurs in Project Euler.

I want to find the last ten digits of the following sum:

$$ S = 1^1 + 2^2 + 3^3 + 4^4 + \cdots + 1000^{1000} $$

Finding this number programmatically is cumbersome because you might need to store a very large integer. To overcome this I figured the following observation;

18^18=    39,346,408,975,296,500,000,000
19^19= 1,978,419,655,660,310,000,000,000

Which led me to the conclusion that:

$$\sum_{x=20}^{1000}x^x >10,000,000,000 $$

And as of such I need not consider numbers with a higher index than 19. If $D_{10}(x)$ is the functions that shows the first ten decimals of a number then;

$$D_{10}(S) = D_{10}() = 1^1 + ... + 1000^{1000} = 1^1 + ... + 20^{20} $$

When I try this out with a bit of python code, I do not seem to come to the same conclusion though;

Full brute force

s = 0
mod = pow(10, 10)
for x in xrange(1, 20):
    s = s + pow(x, x)

print s % mod #9110846700

Limited brute force

s = 0
mod = pow(10, 10)
for x in xrange(1, 1001):
    s = s + pow(x, x)

print s % mod #4303215024

What is my flaw? I the code doesn't seem to have a mistake, but if not that what is the flaw in my logic mathematically?

Answer 1

Heres your main flaw: $$18^{18}\neq 39,346,408,975,296,500,000,000$$ $$19^{19}\neq 1,978,419,655,660,310,000,000,000$$ because if we are to analyze the last digit of the exponent(denoted$L(x)$), then note that $$L(18^2)=4$$ $$L(18^3)=2$$ $$L(18^4)=6$$ $$L(18^5)=8$$ $$L(18^3)=4$$ and $$L(19^2)=1$$ $$L(19^3)=9$$ $$L(19^4)=1$$ note the cycle with period four and two respectively

Now a way of approaching this would be to only calculate the last ten digits of each summand and then sum, but that would still be pretty computationaly heavy.

Answer 2

My guess is rounding errors. You claimed that $19^{19}=1,978,419,655,660,310,000,000,000$ but when I calculated it on Wolfram Alpha, its gives $19^{19}=1,978,419,655,660,313,589,123,979$ Whatever you are using just gives a rounded version, which is useless in determining the last 10 digits.

Answer 3

You are interested in the number $\bmod 10^{10}$, judicious use of Euler's theorem should cut the computation down nicely. Still very ugly, there probably is some shortcut that doesn't involve compute all this.

Answer 4

You need to make use of modular exponentiation , provided in python as pow(a,b,m)

sum([pow(i,i,10**10) for i in xrange(1,1001)])

Sorry for providing you the solution!