Posts Tagged ‘prob36’

Problem 36 – Simultaneous Palindromes

February 10, 2010

In problem 36 we are asked to find all the numbers below a bound that are simultaneously palindromic in both base 10 and base 2. Not the most interesting problem, but for something like completeness sake (and probably to delay doing other things) I thought I’d post about it. I probably learned things, so it was probably worthwhile.

The problem text points out that the leading digit can’t be 0, in either base, so we know that all of the numbers to consider are odd. That’ll likely cut down list iteration by a factor of two. No matter how we set things up, we’ll likely want to reverse a string. Here’s what I rigged up:

def reverse(str):
    return "".join([str[len(str)-1-n] for n in xrange(0, len(str))])

Then I got curious if there was something built-in. There is a built-in way to reverse a list, but not a string. There’s also a “reversed” method that’ll reverse an iterator. And strings have iterators, so you could also do

def reverse(str):
    return "".join(reversed(str))

which seems to have the same affect as

def reverse(str):
    return "".join([i for i in reversed(str)])

It’d probably be fun to compare all of these for speed, but the strings we’re doing are only so big, so it seems to not matter a whole lot for this problem.

We’ll also likely need to test if a string is a palindrome. Here’s what I did:

def ispali(str):
    idx = 0
    while 2*idx <= len(str):
        if not str[idx] == str[len(str)-1-idx]:
            return False
        idx += 1
    return True

The idea being that you only need to go half-way in to see if a string is palindromic. I realized you could also just return “str == reverse(str)”. Mine looks to be slightly faster 🙂

Ok, so, the final bit is converting an integer to binary. It’s built-in (who would have guessed). “bin(n)” converts an integer to a string containing the binary representation of n. It also tacks a ’0b’ at the beginning, so we’ll drop that with “[2:]”.

I think all the bits are in place now. It’s easy enough to write the stupid loop that checks every single thing number up to the bound. In fact, you can do it in a line, if you’ve got an upper bound variable called “bound”:

sum([n for n in xrange(1,bound) if ispali(str(n)) and ispali(bin(n)[2:])])

Surely there’s more efficient code.

I decided to go about it by building up strings I already knew were palindromic decimal numbers. That is, make the right half, and flip it to get the left half. Of course, all of the strings will have even length, and so you’ll never get, for example, a 3 digit number. So I also toss in a pivot digit, which can either be empty or any single digit.

After a while I realized this had a slight glitch. Namely, if your right half is a valid decimal, it won’t have 0s as leading digits, so your palindromes will never have 0s in the middle (or more than one 1, if you set up 0 as a pivot digit), when clearly they should. So in addition to flipping the right side to make the left side, I also allow for middle pivots that are larger strings of 0s.

Here’s what I have:

def solve(digits):
    """ Sum of decimal and binary palindromes up to a bound

    The bound is given by a number of decimal digits.
    E.g., digits = 6 is a bound of 1000000

    Simulatenously palindromic, e.g. 585=1001001001_2
    """
    vals = [1, 3, 5, 7, 9] # all valid answers
    pivots = [''] + [str(n) for n in xrange(0,10)]
    pivots += ['0'*n for n in xrange(2,digits-1)]
    for rhs in xrange(1,10**(digits//2),2): # 2 because only odds
        rhsstr = str(rhs)
        lhs = reverse(rhsstr)
        for p in pivots:
            palstr = lhs+p+rhsstr
            if len(palstr) <= digits and ispali(bin(int(palstr))[2:]):
                vals.append(int(palstr))
    return sum(vals)

Good times. Also good times: writing this post in emacs, and using Eric Finster’s wplatex python package to post it. Well, once I got plastex working in my Ubuntu install. Something strange was going on with an import statement, but I hacked around it a little.

Advertisements