## Project Euler Problem 63: Powerful digit counts

It’s been a long time since I’ve posted anything on here, so I decided that I might as well re-acquaint myself with how Pelican works by writing a new article! I’ve recently returned to solving Project Euler problems, and one solution that I’ve particularly enjoyed is for Problem 63.

Below is the reproduced problem statement:

The 5-digit number, \(16807=7^5\), is also a fifth power. Similarly, the 9-digit number, \(134217728=8^9\), is a ninth power.

How many \(n\)-digit positive integers exist which are also an \(n\)th power?

To summarize, the problem asks for how many numbers \(x=a^n\) also have exactly \(n\) digits, where \(x, a, n\) are positive integers. There are obviously millions of different combinations to look for if one were brute-forcing this solution. That is definitely a bad idea. I instead realized that we can probably find bounds for \(a\) and \(n\), saving a lot of computations.

I think it’d be a good idea to restate the formula for calculating the number of digits \(n\) in a given \(x\):

Through algebra, we may rearrange the left-hand side of \(x=a^n\) to look like that equation:

We can use the second and last parts of the equation to express bounds for \(a\). We may expand the floor function into an inequality

Through further manipulation, we get:

And finally:

So for a given \(n\), the lower bound for \(a\) is \(10^{\frac{n-1}{n}}\) (inclusive) and the upper bound is always 10 (non-inclusive). This makes sense, specifically for the upper bound: When \(a=10\), \(x\) will always have \(n+1\) digits, not \(n\).

It’s easier, however, to calculate the solution the other way aroudn: Find \(n\) in terms of \(a\), since we know \(1 \leq a < 10\) for all \(n\), but we don’t know the general bounds of \(n\). When we solve for \(n\) in this inequality, we get:

What this also means is that *every integer \(n\) in this range will satisfy the condition*, since we’re looking for only positive integers. With that in mind, we can easily write the following solution:

## Output

```
$ time python2 p063.py
1.0
1.43067655807
1.91248928939
2.51294159473
3.32192809489
4.50757555194
6.45569623581
10.3188511585
21.8543453268
49
real 0m0.013s
user 0m0.008s
sys 0m0.007s
```

0.013 seconds. Pretty good, if I may say so myself…

I hope you liked the walkthrough, and be sure to see all of my other Project Euler solutions on GitHub!

## Implementation differences

There was one last thing I noticed when solving this problem.
I generally use PyPy to run my Project Euler solutions for efficiency, but I wanted to make sure this solution worked on vanilla Python 2 as well.
Their implementations of `xrange`

, however, are slightly different – enough to throw an exception in one and not the other.

Simple example: suppose I was looping through divisors of a number \(n\) and wanted to iterate through numbers up until \(\sqrt n\) for efficiency.

```
xrange(1,math.sqrt(n)+1)
```

`math.sqrt`

does not return integers, but PyPy would not complain.
It would just truncate the decimal and continue peacefully.
But vanilla Python gives a painful death:

```
>>> xrange(1,math.sqrt(n)+1)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: integer argument expected, got float
```

The solution is simple of course, but nonetheless, I thought the difference in implementations was interesting.