Problem 48 of Project Euler has the nice and simple description

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} + … + 1000^{1000}.

When I first saw the problem, I thought I knew it would be trivial to solve with BigInteger. However, it turns out that the solution lacks performance, so I have derived another solution as well based on the properties of the modulo operator.

## BigInteger Solution

I don’t even know what kind of clever remarks to make to the source code because it really is trivial. I ended up using the Pow function, since this turned out faster than a for loop for the BigInteger case. The C# source code looks like

BigInteger result = 0; for (int i = 1; i <= 1000; i++) { result += BigInteger.Pow(i, i); }

The code runs in 70 ms with the result

[sourecode]

The last 10 digits are 9110846700

Solution took 70 ms

[/sourecode]

## Modulo Solution

It seems that the BigInteger class is nowhere near using simple integral values of .net, so I wanted to look at other options.

The modulo operator or rather modular arithmetic has some pretty interesting properties for this problem both on addition and multiplication.

The properties we want to exploit are

(a*b) % c = ((a % c) * (b % c) )% c

and

(a+b) % c = ((a % c) + (b % c) )% c.

Since we only need the last ten digits of the results these properties mean that we can cut away all of the leading digits during our calculations. Which in terms means we can use longs to represent our numbers instead of BigInteger.

I have implemented the exponential as a for loop to be able to use the modulo operator inside it such that the source code looks like

long result = 0; long modulo = 10000000000; for (int i = 1; i <= 1000; i++) { long temp = i; for (int j = 1; j < i; j++) { temp *= i; temp %= modulo; } result += temp; result %= modulo; }

So every time we have made a calculation we trim it down, so it fits within the range of a long. This code runs in 17 ms.

The last thing we can do to limit the number of modulo operators and allow us to use a bit more than just ten digits.

long result = 0; long modulo = 10000000000; for (int i = 1; i <= 1000; i++) { long temp = i; for (int j = 1; j < i; j++) { temp *= i; if (temp >= long.MaxValue / 1000) { temp %= modulo; } } result += temp; result %= modulo; }

This small addition to the code optimizes the code and lets it run in 7ms.

## Wrapping up

Many people have solved this problem, which is pretty simple to understand and even easier to implement if your language has support for large integers. I must admit that I quite like the exploitation of the modulo operator. The other code is easier to read, but this one just have a nice feeling to it.

The source code is available as always. Any comments, other solutions or questions are welcome as always.

The top image is from FreeFoto.com and illustrates that this problem was easy as driving down a straight road.

You could also have used BigInteger.ModPow()

This also takes 7 ms.

But of course it’s a lot more fun to implement the ModPow yourself..

Using BigInteger.ModPow seems to take 3 ms, not 7 ms.

That’s pretty awesome, I wasn’t aware of that function. It does exactly what this problem needs.

Thanks for letting me know.

Thank you, Nicely explained.

Another Good post on the similar concept.

http://terminal.co.in/2012/02/find-last-n-digits-of-a-number-obtained-by-some-big-mathematical-calculations/

Hi Palash

Thanks for the compliment and the link.

/Kristian

Using exponentiation by squaring, you can go much faster (not that it’s painfully slow now – 7ms is already fine)! With my implementation (C++) I can get the sum for the 100,000 first self-powers in about 50ms (for the original problem runtime is below my timing precision).

The only thing to be careful about is not overflowing the data type when squaring or multiplying (but that can be taken care of with Russian multiplication for example).

Ah yes, of course you can. And you can use it even if you make the modulo operations I have described if I am not completely mistaken. That is indeed a good insight.

Hey,

This is wrong,

(a+b) % c = ((a + c) * (b + c) )% c

I think you mean:

(a+b) % c = ((a % c) + (b % c) )% c.

Yup you are right. It is corrected now. Thanks for spotting the error.

why have you chose the condition (long.MaxValue>1000)

That was to ensure that I always have room within the memory to multiply by thousand which is the largest number I need to multiply with.

//maysank.blogspot.com

//A simple and fast way in C language can be this also

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]);

}

}

Directly above the ‘Modulo Solution’ header, there is a block of code that is wrapped in broken tags. My guess is that you meant o put and not [sou

recode]. Hope it helps you improve slightly. Great site though!