Project Euler - Problem 48

After posting about Problem 49 and realizing it wasn't really all that interesting, I decided to backtrack a bit and post my solution to Problem 48 as well, which is a more interesting problem.

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Unfortunately C# can't handle large numbers like those required to perform a calculation such as 1000^1000. For earlier project euler problems I had built a few quick hack methods (BigMultiply and BigAdd) to calculate the results of operations on large numbers. But those are slow and we actually don't need them here. The key to doing this problem efficiently is to realize that since we only want the last 10 digits, those are the only digits we ever care about, throughout all operations.

Thusly....

public static ValueType Go()

{

Int64 seriesSum = 0;

for (Int64 i = 1; i < 1001; i++)

{

Int64 currentPower = i;

for (Int64 power = i; power > 1; power--)

{

currentPower = currentPower * i;

// only need last 10 digits

string pow = currentPower.ToString();

if (pow.Length > 10)

currentPower = Int64.Parse(pow.Substring(pow.Length - 10));

}

seriesSum += currentPower;

// only need last 10 digits

string sum = seriesSum.ToString();

if (sum.Length > 10)

seriesSum = Int64.Parse(sum.Substring(sum.Length - 10));

}

return seriesSum;

}

...and voila! Takes a mere 340ms to get the answer: 9110846700.

In general the problems lately have been quite trivial, so I haven't been posting solutions. Here's hoping something more intriguing shows up!