Posts Tagged ‘prob30’

Problem 30 – Sums of Digit Powers

October 1, 2009

In problem 30 we are asked to find all the numbers that are the sum of the n-th powers of their digits. Well, the sum of those numbers. And n=5. You can just about do it in one line…

Most of this problem is fairly easy: Given a number, compute the sum of the powers of its digits, and see if you get the number you started with. If you wanna find all such numbers, just loop for a while. The trouble is how long? If you’ve got some range in mind you want to look at, you can do the following:

def solve(pow, low, hi):
    """ Find the sum of all numbers that are the sum of their pow-th powers of digits in the interval [low,hi) """
    return sum(filter(lambda n:n==sum(map(lambda d:int(d)**pow,str(n))) xrange(low, hi)))

Ok, sure, it’s a longish line, but it’s all there. Python’s syntactic sugar for handling all the little looping is awesome.

The remaining trick is to figure out those bounds. The problem mentions not using 1 as one of the numbers, so we could start at 2. However, that means we could start at 2**pow, because that’ll be the lowest digit sum we’d make. On the high end, the biggest digit-power-sum will come from digits being 9. So I figure that to find an upper bound, you can think about digit sums for longer and longer strings of 9. If you think about k 9s in a row, that’ll give a digit sum of k\cdot 9^p (if p is the specified power). Find the largest k where this value is still a k-digit number (or bigger), and you’ve got yourself an upper bound to loop to. Here’s some code to find the bound:

def bound(pow):
    """ Find bound on nums that can be sum of their pow-th powers of digits """
    if pow <= 1:
        return 9
    nine = 9**pow
    coeff = 1
    while(len(str(coeff*nine)) >= coeff):
        coeff += 1
    return (coeff - 1)*nine

Now, these bounds I’ve set up are pretty poor. In the case where the power is 4, as in the example problem, we’d loop from 2**4=16 to 32805, when the actual numbers that have the property we’re hoping for are between 1000 and 10000. We’ve overshot by something like 3 times too many values.

So, we could try to be more clever and come up with a smaller set to search in. But we could still use that one-line solver to pick from that set the appropriate values. And that makes me happy.

Advertisements