The last digits of large numbers
Published on Friday, July 29, 2011Problem 48, the next challenge in Project Euler when they're sorted by ascending difficulty, seemed a bit familiar. It asks you to come up with a very large number and then report back the last few digits thereof. It reads:
The series, 11 + 22 + 33 + … + 1010 = 10405071317.
Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.
.NET makes this kind of problem extremely easy, as all one has to do is use BigIntegers to add all members of the series together. Taking that approach, I came up with the following:
static void Main(string[] args)
{
BigInteger ridiculouslyHugeSum = new BigInteger(1);
for (int i = 2; i <= 1000; i++)
ridiculouslyHugeSum += BigIntPower(i, i);
string sumString = ridiculouslyHugeSum.ToString();
Console.WriteLine(sumString.Substring(sumString.Length - 10));
}
private static BigInteger BigIntPower(int exponentBase, int power)
{
BigInteger exponentValue = new BigInteger(exponentBase);
for (int j = 1; j < power; j++)
exponentValue *= exponentBase;
return exponentValue;
}
It worked fine; it just took a bit longer than I would have liked (read: a few seconds rather than a few milliseconds). Because the problem only asked for the ten least significant digits, I inserted two lines of code into the above that instructed the computer to lop off the most significant digit whenever it encountered an eleven digit number.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Problem048
{
class Program
{
static void Main(string[] args)
{
long runningTotal = 1;
for (int i = 2; i <= 1000; i++)
{
runningTotal += lastTenOfPower(i, i);
if (runningTotal > 10000000000)
runningTotal %= 10000000000;
}
Console.WriteLine(runningTotal);
}
private static long lastTenOfPower(int exponentBase, int power)
{
long exponentValue = exponentBase;
for (int j = 1; j < power; j++)
{
exponentValue *= exponentBase;
if (exponentValue > 10000000000)
exponentValue %= 10000000000;
}
return exponentValue;
}
}
}