# /home/avaidya

## 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$$:

$$\lfloor\log_{10} x\rfloor + 1 = n$$

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

$$\lfloor \log_{10} x \rfloor + 1 = \lfloor n\log_{10} a \rfloor + 1 = n$$

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

$$n-1 \leq n\log_{10} a < n$$

Through further manipulation, we get:

$$\frac{n-1}{n} \leq \log_{10} a < 1$$

And finally:

$$10^{\frac{n-1}{n}} \leq a < 10$$

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:

$$n \leq \frac{1}{1 - \log_{10} a}$$

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.