[C/C++] Project Euler #63 - Powerful digit counts

This is a problem involving powers, but unexpectedly, it’s quite easy. The difficulty level is only 5%. The problem is: How many n-digit numbers are also nth powers of some number?
For example, \(16807 = 7^5\), and 16807 is a 5-digit number, which is exactly the 5th power of 7.

 

block stacking

---

Even a brute-force solution works just fine for this problem. First, only numbers less than 10 are worth considering as bases. That’s because \(10^n\) has n+1 digits, and obviously, any number larger than 10 will exceed n digits even faster.
At first glance, the problem seems difficult, but once you realize the constraints hidden in the digits and values, it becomes much easier.

So, you can just square (or raise to power) numbers from 1 through 9 and count the number of cases where the result has the same number of digits as the exponent. As long as you’re careful about overflow, there shouldn’t be any issues.
For example, \(3^3 = 27\), and 27 is a 2-digit number, so the number of digits is less than the exponent. Multiplying by 3 again won’t help. So you can stop checking once the number of digits exceeds the exponent. This kind of straightforward calculation is totally fine for this problem.

Let’s take the number 2 and see how many powers of 2 produce a result with the same number of digits as the exponent.
Start with \(2^1 = 2\), which is a 1-digit number — so it counts.
Then \(2^2 = 4\), which is still a 1-digit number, so it no longer satisfies the condition. Therefore, the maximum count for base 2 is just 1.

I expressed this with the following formula:

\[ \text{count}_n = \left\lfloor \frac{1}{1 - \log{10} n} \right\rfloor \]

If n = 1, the result is 1.
If n = 2, the result is about 1.43, and taking the floor gives 1.
If n = 3, the result is approximately 1.912, still floor 1.
\(3^2 = 9\), which is nearly 10 — so it’s close to moving to the next digit count.
If n = 4, the result is about 2.51, which gives 2.
Since \(4^2 = 16\), that’s the first time a power gives a 2-digit number.

So you can manually compute how many such cases exist using this logic.

//------------------------------------------------
//    Project Euler #63 - Powerful digit counts
//        - by Aubrey Choi
//        - created at 2015-10-01
//------------------------------------------------
#include <stdio.h>
#include <time.h>
#include <math.h>

void solve1()
{
    int count = 1;
    for( int i = 2 ; i < 10 ; i++ )
    {
        count += 1.0/(1.0-log10((double)i));
    }
    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}