Problem #36 is one of the many problems on Project Euler that involves binary. The question reads:
Project Euler Problem 36: Double-base palindromes
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.)
This problem is not particularly interesting, as we have already encountered many problems involving palindromes. Here is my solution:
Solution #1: Brute Force Approach
We simply iterate through all of the numbers less than 1,000,000 and check if each one is a palindrome in both base 10 and base 2. Here’s an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #36
'''
import time
def isPalindrome(x):
return x%10!=0 and str(x) == str(x)[::-1]
def projectEulerProblemThirtySix(n):
total = 0
for i in range(1,n):
if(isPalindrome(i) and isPalindrome(int(bin(i)[2:]))):
total+=i
return total
start = time.time()
print projectEulerProblemThirtySix(1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
872187
--- 0.415219783783 seconds ---
for input of n = 1000000
'''
As shown above, Python has very simple means of handling strings, and this can be used to detect palindromes without too much code. Python also has relatively simple means of converting numbers to and from binary. My solution to this problem probably isn’t as efficient as it could be, and I may come back to it eventually.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 