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.)
I go about this by generating palindromes in base 10 and checking whether they're also palindromic in base 2. All base 10 palindromes below \(10^6\) are uniquely generated by taking a number less than \(10^3\), reversing it, either removing the final digit or appending any number of zeros to it, and prepending the result to the original number. Strings make this easy.
The search space can be cut down a bit: all positive numbers in base 2 have leading bit 1, so all palindromes in base 2 must have trailing bit 1, i.e., they must be odd.
def p36(m=6):
assert(m % 2 == 0)
res = 0
for i in range(1, 10 ** (m // 2), 2):
s = str(i)[::-1]
# either remove the new final digit...
pal = int(s[:-1] + str(i))
palb = bin(pal)[2:] # get rid of leading '0b'
if palb == palb[::-1]:
res += pal
# ...or append any number of zeros to it
for j in range(m - 2 * len(s) + 1):
pal = int(s + ('0' * j) + str(i))
palb = bin(pal)[2:]
if palb == palb[::-1]:
res += pal
return res