1
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ $19^{19}$ certainly does not end in $0$ (the last digit is a $9$). So what do you mean when you write $19^{19} = 1,978,419,655,660,310,000,000,000$? $\endgroup$ – Nicholas Stull May 22 '14 at 18:39
  • $\begingroup$ $19^{19} = 1,978,419,655,660,313,589,123,979$, so why are you cutting off the last 10 digits, when those are the ones you are concerned with? (Sorry for the double post, but I forgot to edit this into my previous comment) $\endgroup$ – Nicholas Stull May 22 '14 at 18:42
  • $\begingroup$ ah. it seems that the calculator i used (the alfred app) applies rounding to deal with long integers. i should really refrain from doing project euler in the middle of the night. my bad. thanks! $\endgroup$ – Vincent Warmerdam May 22 '14 at 18:44
  • $\begingroup$ You can calculate the result directly without needing an intermediate number bigger than 10^13. Remember that $abc \bmod n = a(bc \bmod n)\bmod n $. $\endgroup$ – NovaDenizen May 22 '14 at 19:19
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.