Project Euler 63: How many n-digit positive integers exist which are also an nth power

Project Euler 63: How many n-digit positive integers exist which are also an nth power

Written by on 1 October 2011

Topics: Project Euler

In project Euler‘s problem 63 we are again crawling up above 10.000 solutions, which suggests that this problem is a bit easier than the previous ones. So let’s take a look at it

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?

If nothing else at least the description is short. I can ensure you that the coding we will do for this is short as well, but let us first do a bit of analysis on the problem.

Problem analysis

The problem states that we need to find out how many n-digit integers that exists which are also an nth power. We can express this in a slightly more mathematical way as. We need to find an integer x such that

For n= 3 that would give us<

which includes all the 3 digit positive numbers. We already have a clear upper bound which is since x has to be an integer. The lower bound is less obvious.  However, we the lower bound is given by one equation with one unknown, so let’s isolate x in the equation.

By taking the base 10 logarithm on both sides (just denoted log)

So this gives us a lower bound for x.

One more thing we are interested in, how many values of n do we have to find an upper and lower bound for. As we can see this lower bound grows when n grows as the fraction approaches 1 as n grows. Or expressed more mathematical

It means that the whole expression will approach 10 as n increases. So we can be sure that at some point we reach a value for n where the lower bound  is larger than 9 and thus lower bound is larger than the upper bound and there are no more solutions for larger values of n. So we know that if we iterate over values of n we have an upper bound at which we can stop.

The implementation

We know have an expression for the upper and a lower bound for x for each value n, so all we have to do in the algorithm is to iterate over n, calculate the upper and lower bound and sum up the number of values between them. This can be done in C# as

int result = 0;
int lower = 0;
int n = 1;

while (lower < 10) {
    lower = (int)Math.Ceiling(Math.Pow(10,(n-1.0)/n));
    result += 10 - lower;
    n++;
}

I have deducted 1.0 instead of 1 to convert it to a double, otherwise the division would end up being an integer division which would always result in 0, and thus give us a wrong bound.

Running this code gives us

There are 49 n-digit integers which are also an nth power
Solution took 0 ms

So I doubt it can be done much faster.

Wrapping up

This problem was pretty easy to program a solution for once we got the mathematics right. I hope I have conveyed the mathematics of the post in an understandable way. It shouldn’t be too hard to follow the ideas. I think the most important insight was the restatement of the problem to an upper and lower bound using powers of 10. From there on it was pretty straight forward.

The source code is available for you if you want to have it as a .cs file instead of copy pasting.

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

  1. BABU says:

    It would have been better if you provide all 49 numbers list.

  2. Jean-Marie Hachey says:

    Thanks to Kristian for this interesting and challenging problem.

    Some results and comments.
    Calculations done with Microsoft Excel and Javasripter (1) for big numbers (i.e. over 15 digits).

    (1) Big Integer Calculator:
    http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm

    ______

    Table 1 :
    n-digit positive integers and nth power.
    Numbers (0 @ 10); Exponents (0 @ 12)

    http://img819.imageshack.us/img819/4044/pe63tabone.jpg

    Enlightened in yellow : values where power exponents and numbers of digits are equal.

    ___

    Table 2 :
    Powers : 1^1 @ 9^22
    (EN 1 @ 50)

    http://img827.imageshack.us/img827/269/pe63tabtwo.jpg

    As predicted, EN 49 is the last one where the exponent is equal to the number of digits.

    ___

    Table 3 :
    Powers : 9^23 @ 9^10000
    (EN 51 @ 77)

    http://img94.imageshack.us/img94/7411/pe63tabthree.jpg

    As exponents of the power increase so do the diffrence between the exponents and the number of digits.

  3. Jean-Marie Hachey says:

    Occurrence of consecutive pairs of numbers with equal length digits generated by 9^22n and 9^x.
    (Illustrated: 1=<n<=6; 152=<x<=306)

    Table 1

    The first pair of equal length digit numbers occurs at 9^21 and 9^22.

    http://img715.imageshack.us/img715/9655/exptablone.jpg

    However, the production of such pairs of numbers is not restricted to 9^22n.
    Table 2 shows that after the 9^22n series, the same type of pairs is obtained with 9^x.
    (152=<x<=306 in the examples shown).

    ___

    Table 2

    http://img850.imageshack.us/img850/7262/exptabltwo.jpg

    Lines of transition : EN 13 and 14.

    The exponents of 9 generating pairs of consecutive numbers of equal length digit are no longer multiples of 22.

  4. Kristian says:

    Thanks Jean-Marie, it is some interesting insights you come up with.

  5. Vlad says:

    Besides the elegant solutions you guys provided, below is mine.

    It involves brute forcing all the numbers and powers until the limit I provide, which can be found with a bit of guesswork + trial and error. It works, and I get the solution in 0.004 secs.

    Wasteful, dirty, but got the job done 😛


    counter = 0
    for power in range(1, 25):
    for i in range(1, 100):
    n = i ** power
    if len(str(n)) == power:
    print str(i) + " ** " + str(power) + " = " + str(n) # just for show
    counter += 1

    print counter

  6. Kristian says:

    I believe the two approaches are almost similar except for the stopping criteria. After all we end up going through all the combinations as well. The main difference being that you don’t really have a way to tell if your bounds are correct. But make them high enough and they will be 🙂

  7. Shobhit says:

    This was too simple to write a program. I did it on paper with the help of a log table and a calculator (I used google for both of them).
    I used the same logic:
    x^n > 10^n-1
    it means the number would give the result until
    10^(n-1) > x^n
    n-1 > n*log(x)
    solving it for n
    n > 1 / (1 – log x)
    Solve it by putting 1 – 9 and take the floor of the result.

    It is not a new approach but a more synthesized formula. Loop will run from 1 – 9 only once.
    Can it be simplified even more ?

  8. Kristian says:

    No I don’t think you can simplify it more than it is now.

  9. Larry C says:

    Much too easy a problem.

    First realize that i^n requires that i be less than 10 since all powers of 10 will have n+1 digits. So values of i larger than 10 will all fail.

    Second i^1 for i 0. Remember i < 10. But it will pass for all values of n up to some value.

    Brute force would say for any i just compute i^n until failure. That can't take long.

    A direct approach is to realize that failure occurs when i^n < 10^n. Taking log base 10 and solving for n give n < i/log(i).

    So the easy answer is the sum over i from 2 to 9 of (int)(i/log(i)) plus 1. The extra 1 is for 1^1 since log of 1 is zero we can't divide by zero.

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.