Problem 63 - Powerful digit counts

Implementation

This is a relatively straightforward problem and simple to understand, but one that benefits from a little planning beforehand. It's very temping to write a brute-force function that continues to generate integer powers until the number of digits exceeds the exponent. But after a bit of testing it quickly becomes apparent that that might not work.

210 = 1024 (4 digits)
250 = 1,125,899,906,842,624 (16 digits)
2100 = 1,267,650,600,228,229,401,496,703,205,376 (31 digits)

It doesn't appear that any power of 2 will ever have as many digits as the exponent. But what about powers of 3 or 4? Where should we start checking?

The key to this problem is to remember that there is a function that tells us how many digits a number has. The logarithm of x is related to x's number of digits by:

# digits of x = floor(log10(x)) + 1

Because the problem is asking us to find the number of digits of integer powers, we can also utilize a property of logarithms to simplify our solution.

# digits of ab = floor(log10(ab)) + 1
# digits of ab = floor(b*log10(a)) + 1

With this formula we can make the following observation:

For a ≥ 10
# digits of 10b ≥ floor(b*log10(10)) + 1
# digits of 10b ≥ b+1

This tells us that any integer base ≥ 10 raised to an integer power b will always have more digits than the value of b. Therefore we only need to check bases 1-9. In addition, with this formula it's no longer necessary to calculate the number itself. With a given base and exponent we can calculate the number of digits directly.

unsigned numNDigitNPowers() {
	unsigned count = 0;
	unsigned minBase = 1, maxBase = 10;
	for (unsigned exp = 1; minBase < maxBase; exp++) {
		while ((unsigned)(exp*log10(minBase))+1 < exp) minBase++;
		for (unsigned base = minBase; base < maxBase; base++)
			count += ((unsigned)(exp*log10(base))+1 == exp);
	}
	return count;
}

In the outer loop we iterate through integer exponents. For each exponent we first find the minimum base that gives a power with exp number of digits. Then in the inner loop we check the remaining bases (up to 9) for any more solutions. This continues until the minimum base needed is > 9.

The full solutions are given below:

1^1 = 1
2^1 = 2
3^1 = 3
4^1 = 4
5^1 = 5
6^1 = 6
7^1 = 7
8^1 = 8
9^1 = 9

4^2 = 16
5^2 = 25
6^2 = 36
7^2 = 49
8^2 = 64
9^2 = 81

5^3 = 125
6^3 = 216
7^3 = 343
8^3 = 512
9^3 = 729

6^4 = 1,296
7^4 = 2,401
8^4 = 4,096
9^4 = 6,561

7^5 = 16,807
8^5 = 32,768
9^5 = 59,049

7^6 = 117,649
8^6 = 262,144
9^6 = 531,441

8^7 = 2,097,152
9^7 = 4,782,969

8^8 = 16,777,216
9^8 = 43,046,721

8^9 = 134,217,728
9^9 = 387,420,489

8^10 = 1,073,741,824
9^10 = 3,486,784,401

9^11 = 31,381,059,609
9^12 = 282,429,536,481
9^13 = 2,541,865,828,329
9^14 = 22,876,792,454,961
9^15 = 205,891,132,094,649
9^16 = 1,853,020,188,851,841
9^17 = 16,677,181,699,666,569
9^18 = 150,094,635,296,999,121
9^19 = 1,350,851,717,672,992,089
9^20 = 12,157,665,459,056,928,801
9^21 = 109,418,989,131,512,359,209