As it was Pi-day yesterday, I celebrated by staying up all night catching up on reading for a class because of the weekly quiz. I also spaced out the monotony with some coding. Moreover, this will be part of a twofer! This is a neat problem that I wouldn’t have been able to do until a few weeks ago, when I learned some of the math in being able to do this problem in my Number Theory class. It’s very simple: what is the last 10 digits of the sum 1^1 + 2^2 + 3^3 + 4^4 + … + 1000^1000. Until I learned more about modular arithmetic in my number theory class, I had no idea how to proceed. I doubt there was a formula for sum(k^k), so there is some brute force approach, but 1000^1000 has over 3000 digits! I had written a big-number library for another problem, but I don’t know how well it would carry over.
But luckily, number theory came to the rescue. Presumably you, the reader, know what modulo n means. First, we only care about the last 10 digits of the result. We can get the last digit of any number by dividing out all multiples of 10, that is, the last digit of n is simply n mod 10. Similarly, we can get the last two digits of any number n by dividing out all multiples of 100, n mod 100 in this case. Our problem then indicates that we just need to take n mod 10^10 of the result. Does that mean we need to keep track of the sum in the meantime? No! And thank God, since we still haven’t dealt with that 3000 digit business, but turns out we don’t need to. To proceed, we’ll need two identities:
1. if a = b mod n, then a^k = b^k mod n for k integer. What this means for us is a handy way to keep track of the term k^k mod 10^10, so that any time, the largest number we really have to keep track of won’t exceed 10^10, which can be stored in a long long in my c++ solution. For example, to calculate 100^100, we start with 100 mod n = 100. We can increase the power by 1 by multiplying by 100 and then taking the modulus of the result according to that identity. We repeat until the power equals 100. *
* We can actually do it faster if we square each result, stopping at the highest power of 2 lower than our desired power. To see why, realize a^k = b^k mod n implies (a^k)^2 = (b^k)^2 mod n, and that ((a^k)^2)^2 = ((b^k)^2)^2 mod n, and so on. But it’s an optimization we won’t miss.
2. if a = b mod n, then a + c = b + c mod n. What this one means for us is that we can keep a running modular sum, carry out k^k mod n by means of the first identity, and add it to our result.
Since the highest base is 1000, the first identity is employed less then 1000*1000 times if we increase power linearly. I’m happy with a O(n^2) algorithm if it’s easier to code :p
The result, by the way is 9110846700, and the code is here: http://pastebin.com/q3wPDmyv
Look out for part 2 later in the day! Back to studying I go.
ben "beignet" yeh 
need answer to
The series, 1^1 + 2^2 + 3^3 + … + 10^10 = 10405071317.
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + … + 500^500
1688579601
code: (python)
totalsum = 0
for e in range(500):
a = e**e
totalsum = totalsum + a
g = str(totalsum)
print g[-10:]
A really easy way to do it on python is:
totalsum = 0
for e in range(1000):
a = e**e
totalsum = totalsum + a
g = str(sume)
print g[-10:]
and i convert it to string to do offset -10, 3 lines code! xD
very cool! I didn’t know any python, nor don’t know how python handles such a large number in totalsum. The problem with c/c++ is that it will easily overflow even the largest datatype so I have to take the modulus after every step.
main()
{
int num;
int j;//to save the value of i
int i;
int reserve;//for reserving the value of number.
static int sum[10];//for storing the value of result and static for making all array value initially zero.
static int a[10];//for storing value of individual power
int n=10;
int check;//for checking wether an element of array is getting carry or not.
for(num=1;num<=1000;num++)//Loop for taking all the numbers whose power is taken.
{
a[n-1]=num;
for(reserve=1;reserve<num;reserve++)//Loop for value of individual Power.
{
for(i=0;i<n;i++)//Loop for multiplying each array element with the number to get power;
{
a[i]*=num;
}
for(i=0;i9)
{
check=a[i];
a[i]=(check%10);
check/=10;
j=i-1;
while(check!=0)
{
if(j<0){break;}
a[j]+=(check%10);
check/=10;
j–;
}
}
}
}
for(i=0;i9)
{
check=sum[i];
sum[i]=check%10;
check/=10;
j=i-1;
while(check!=0)
{if(j<0){break;}
sum[j]+=(check%10);
check/=10;
j–;
}
}
}
}
for(i=0;i<=9;i++)//for printing last 10 digits
{
printf("%d",sum[i]);
}
}