Monday 20 April 2009

PROJECT EULER #63

Link to Project Euler problem 63

The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.
How many n-digit positive integers exist which are also an nth power?


Using BigInt was one way, but there is a more elegant solution using logs:
number of digits in 100 = 3, 1000 = 4,

log 100 = 2, log 1000 = 3.
number of digits in 567 = (int)((log 567)+1) = (int)2.75 + 1 = 3
number of digits in x = (int)(log x) + 1
number of digits in x^y = (int)((y * log x) + 1)
number of digits in 10^y = y + 1, so only x = 1 to 9 hold solutions
then if x^y = y digits, =>
y = (int) y * log x + 1, => (divide by y)
1 = (int) log x + 1 / y, => (subtract log x)
1 / y = (int)(1 - log x), => (invert)
y = (int)(1/(1 - log x)).

The BigInt solution:

using System;

namespace ProjectEuler
{
class Program
{
static void Main()
{
//Problem 63
DateTime start = DateTime.Now;
int count = 0;
for (int i = 1; i < 10; i++)
{
BigInt n = new BigInt(1);
for (int j = 1; j < 25; j++)
{
n *= i;
if (n.ToString().Length==j)
count++;
}
}
Console.WriteLine(count);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}

The log solution:

using System;

namespace ProjectEuler
{
class Program
{
static void Main()
{
//Problem 63
DateTime start = DateTime.Now;
int count = 0;
for (int i = 1; i < 10; i++)
count += (int) (1/(1 - Math.Log10(i)));
Console.WriteLine(count);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}
Triple-click for answer: 49

No comments: