What is the Powerful Digit Counts Problem?

The Powerful Digit Counts is one of the problems from Project Euler.

The problem statements are as follows:

The 5-digit number, 16807 = $7^{{5}}$ , is also a fifth power. In the same way, the 9-digit number, 134217728 = $8^{{9}}$, is the ninth power.

How many n-digit positive integers exist, which are also an nth power?

Solution

Determining the limits for base

We will first try to determine the lowest and highest possible base. This will act as the first step towards our solution.

Consider the base to be 10. We can calculate the powers of 10 like this:

• $10^{{1}}$ = 10
• $10^{{2}}$ = 100
• $10^{{3}}$ = 1000

Here, we can see a trend that the length of the answer exceeds the power, i.e., if the power is 1, the length of the answer is 2 (with 10 being the answer).

Hence, we can safely conclude that no number greater than or equal to 10 will satisfy our initial condition.

Now, we will try to calculate the first few powers with base 9:

• $9^{{1}}$ = 9
• $9^{{2}}$ = 81
• $9^{{3}}$ = 729

Here, we can see that the length of the answer remains the same as the power, i.e., if the power of 9 is 2, then the length of the answer is also 2 (with 81 being the answer).

Hence, we can safely conclude that any number less than or equal to 9 can be the base for a correct answer.

Determining the limits for power for each number

Let us consider the first few powers with bases 2 and 5:

• $2^{{1}}$ = 2
• $2^{{2}}$ = 4
• $2^{{3}}$ = 8
• $2^{{2}}$ = 16 …

Similarly, for 5:

• $5^{{1}}$ = 5
• $5^{{2}}$ = 25
• $5^{{3}}$ = 125
• $5^{{4}}$ = 625
• $5^{{5}}$ = 3125 …

As we can see, we gradually reach a limiting number in the power for each base, after which the power becomes greater than the length of the answer. For base 2, the limiting factor is 1. For base 5, the limiting factor is 3.

This limiting number will be unique for each base number.

With the above conclusions in our mind, we will focus on the algorithm and the code implementation.

Algorithm

We will start with base 1 and iterate till base 9.

For each number in the base, we will calculate the power starting from 1 till we find a power where the length of the answer is not equal to the power. This power will be the limiting factor. The condition will never satisfy after the limiting factor, so we continue to the next number.

Code

The following piece of code is the implementation of the algorithm explained above in Python:

The above snippet of code prints the output 49. This means that there are 49 such numbers which are nth powers and contain n number of digits.