Project Euler 48: Find the last ten digits of 1^1 + 2^2 + … + 1000^1000

Project Euler 48: Find the last ten digits of 1^1 + 2^2 + … + 1000^1000

Written by on 18 June 2011

Topics: Project Euler

Problem 48 of Project Euler has the nice and simple description

The series, 11 + 22 + 33 + … + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

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.

13 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    You could also have used BigInteger.ModPow()

    BigInteger sum = 0,
               mod = BigInteger.Pow(10, 10);
    
    for (int i = 1; i <= 1000; i++)
    {
    	sum = (sum + BigInteger.ModPow(i, i, mod)) % mod;
    }
    

    This also takes 7 ms.
    But of course it’s a lot more fun to implement the ModPow yourself..

  2. SuprDewd says:

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

  3. Kristian says:

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

    Thanks for letting me know.

  4. Kristian says:

    Hi Palash

    Thanks for the compliment and the link.

    /Kristian

  5. Khaur says:

    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).

  6. Kristian says:

    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.

  7. gui xunlong says:

    Hey,
    This is wrong,
    (a+b) % c = ((a + c) * (b + c) )% c

    I think you mean:
    (a+b) % c = ((a % c) + (b % c) )% c.

  8. Kristian says:

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

  9. raj says:

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

  10. Kristian says:

    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.

  11. maysank.blogspot.com says:

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

  12. michael says:

    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 [sourecode]. Hope it helps you improve slightly. Great site though!

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.