Palindromic numbers in two bases, Project Euler #36

Question

Here is my solution for Project Euler problem 36, which reads:

The decimal number, 585 = 1001001001₂ (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 result is somehow wrong. Could anyone help?

def findnum(n):
    a = 0
    for i in range(0, n + 1):
        temp = '{0:08b}'.format(i)
        if str(i) == str(i)[::-1] and str(temp) == str(temp)[::-1]:
            a += i 
    return a 

print findnum(1000000)

The result I got is 872096, but the correct answer seems to be 872187. But the difference of these two, 91, is not a palindrome. What am I doing wrong?

Answer 1

You missed something in the problem description:

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

Yet you are using leading zeros:

temp = '{0:08b}'.format(i)

Drop the 08 from the format; there is no need to pad it to a width at all here:

temp = '{0:b}'.format(i)

With this change you'll get the correct answer.

You may as well just use the format() function instead, as you are not putting the string into a larger template. You don't need to feed it to str() as format() already produces a string. I'd swap the tests to test for a binary palindrome first and avoid extra str() calls. The n + 1 in the range() call is not needed; the problem description asks for all such numbers below 1 million:

for i in range(n):
    temp = format(i, 'b')
    if temp == temp[::-1] and str(i) == str(i)[::-1]:
        a += i

or you could first test for the decimal palindrome, then format:

for i in range(n):
    decimal = str(i)
    if decimal != decimal[::-1]:
        continue
    binary = format(i, 'b')
    if binary == binary[::-1]:
        a += i

This shaves off quite a few calls from the overall runtime, making the final version more than twice as fast:

>>> from timeit import timeit
>>> def findnum_orig(n):
...     a = 0
...     for i in range(0, n + 1):
...         temp = '{0:b}'.format(i)
...         if str(i) == str(i)[::-1] and str(temp) == str(temp)[::-1]:
...             a += i 
...     return a 
... 
>>> def findnum_optimised(n):
...     a = 0
...     for i in range(n):
...         decimal = str(i)
...         if decimal != decimal[::-1]:
...             continue
...         binary = format(i, 'b')
...         if binary == binary[::-1]:
...             a += i
...     return a
... 
>>> timeit('fn(1000000)', 'from __main__ import findnum_orig as fn', number=10)
10.886759996414185
>>> timeit('fn(1000000)', 'from __main__ import findnum_optimised as fn', number=10)
3.7782959938049316

That's because str() is a lot faster than format():

>>> timeit('for i in range(1000): str(i)', number=1000)
0.17951107025146484
>>> timeit('for i in range(1000): format(i, 'b')', number=1000)
0.2837510108947754

As there are only 1999 decimal and 2000 binary palindromes below 1 million:

>>> sum(1 for i in range(1000000) if str(i) == str(i)[::-1])
1999
>>> sum(1 for i in range(1000000) if format(i, 'b') == format(i, 'b')[::-1])
2000

avoiding the slower operation all but those 1999 decimal palindromes saves you a lot of time.

We can make it faster still by switching how you convert the integer to binary; the bin() function produces a binary number too, albeit with the 0b prefix. Even with having to remove that prefix using that function is faster than using format():

>>> timeit('for i in range(1000): format(i, "b")', number=1000)
0.46987009048461914
>>> timeit('for i in range(1000): bin(i)[2:]', number=1000)
0.24124693870544434

and if you are using Python 2.x, you should also use the xrange() function to avoid creating a list with 1.000.000 integers. This brings the final timings to:

>>> def findnum_bin_xrange(n):
...     a = 0
...     for i in xrange(n):
...         decimal = str(i)
...         if decimal != decimal[::-1]:
...             continue
...         binary = bin(i)[2:]
...         if binary == binary[::-1]:
...             a += i 
...     return a 
... 
>>> findnum_bin_xrange(1000000)
872187
>>> timeit('fn(1000000)', 'from __main__ import findnum_bin_xrange as fn', number=10)
3.5071611404418945

That's down to about 1/3rd of your original code timings.