Project Euler: #36 Binary and Base 10 Palindromes

Question

Here is the Euler problem referenced, it says:

The decimal number, 585 = 1001001001\$_2\$ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

My solution is as follows:

def check_palindrome_base_ten(num):
    a = str(num) 
    return a == a[::-1]

def check_palindrome_base_two(num):
    a = str(bin(num))[2:]
    return a == a[::-1]

def check_palindrome(num):
    return check_palindrome_base_ten(num) and check_palindrome_base_two(num)

def sum_palindrome_in_a_range(lower_limit, upper_limit):
    return sum(x for x in xrange(lower_limit, upper_limit+1, 2) if check_palindrome(x))

%timeit sum_palindrome_in_a_range(1,1000000)
1 loops, best of 3: 247 ms per loop

I noticed by the end of the solution after just brute forcing it that the step could be changed to 2 to use only odd numbers because the binary 1st digit should always be 1 if the number was greater than 1 and a palindrome. This cut my execution time in literal half from ~480ms to 247ms.

In addition I thought that perhaps writing mini functions and then running a reverse index on that number would be faster than doing say:

str(a) == str(a)[::-1]

Because I get to avoid running str and bin twice. Is that correct logic?

Are there any such other optimizations that I have missed that I can use to reduce runtime and in general make my code more useful. I feel as though I may be stuck in a for loop / list comprehension trap and perhaps am not thinking creatively enough when approaching these solutions. I'm scared that's going to cause my solutions when I code actual problems to be inefficient. So perhaps it's also a code methodology review in that respect.

Answer 1

Are there any such other optimizations that I have missed that I can use to reduce runtime and in general make my code more useful.

Yes. You're thinking about the problem backwards. As far as I can tell, your solution may be as fast as you can do in Python solving the problem directly. That is, something like:

sum(filter(satisfies_problem, xrange(1, 1000000))

But we can do way better. Palindromes are fairly sparse, so rather than go through a million numbers and checking them to see, we can actually just generate all the palindromes in one base and just check if they're a palindrome in the other base. Basically, for every number from 1 to 1000 we can just add its reverse with or without duplication (e.g. 146 can become the palindromes 14641 and 146641). That is:

def make_palindrome(p, repeat):
    result = p 
    if not repeat: p //= 10
    while p > 0:
        result = result * 10 + p % 10
        p //= 10
    return result

Then we can just generate all the right palindromes, base 10, and check if they match base 2:

total = 0 
cap = upper_limit / 10 ** (math.log10(upper_limit)/2)
for p in xrange(int(cap) + 1): 
    for repeat in (True, False):
        pal = make_palindrome(p, repeat)
        if pal & 1 and lower_limit <= pal <= upper_limit:
            as_bin = bin(pal)[2:]
            if as_bin == as_bin[::-1]:
                total += pal 

return total

Timing comparison, this is 100x faster:

Brute Force Search    0.3477s
Palindrome Generator  0.0030s