/home/avaidya

May 17, 2016

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:

p063.py download 
#!/usr/bin/env python2

# Project Euler: problem 63
# https://projecteuler.net/problem=63

import math

if __name__=="__main__":
    ans = 0
    for a in xrange(1,10):
        print 1./(1-math.log(a, base=10))
        ans += int(1./(1-math.log(a, base=10)))
    print ans

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.

posted at 22:04  ·   ·  Python