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.)

Before dive into the solution, let’s understand the problem properly. We’re required to find all numbers less than one million that are palindromes in both base 10 and base 2.

Let’s begin with a simple observation:

Any binary number (base 2) that is a palindrome and doesn’t have leading zeros must end in 1. Because a binary number that ends in 0 will have a leading zero when reversed. Therefore, the decimal representation of such a number must be odd. This indicates that all numbers we are looking for are odd.

### Solution:

First, we need to generate all palindromic base-10 numbers that contain less than seven digits, since they need to be less than one million, and check each to determine whether it is also a palindrome in base-2.

1. So, let start generating base-10 palindromic numbers. Keep in mind all such numbers have to be odd. We have four numbers with one digit and five numbers with two digits (all odd). For three and four digits, we have 20 each, for five and six digits, the count is 100 each.

2. Now, we need to check if these numbers are also palindromic in base-2. To convert a base-10 number to base-2, we can use inbuilt function in Python `bin(n)[2:]` where n is the decimal number.

3. Once we have binary representation of a number, we can easily check if its palindromic by comparing it with its reverse. If it is, we keep the number, if not, we discard it.

4. In the end, we sum all these numbers.

Here is the Python code implementation of the solution:

“`python
def is_palindrome(n):
return str(n) == str(n)[::-1]

total = 0
for i in range(1, 10):
for j in range(0, 10):
k = 10 * i + j

# For odd digit palindromes
if is_palindrome(bin(k)[2:]):
total += k

k = i * 100 + 10 * j + i
if is_palindrome(bin(k)[2:]):
total += k

for k in range(0, 10):
m = i * 1000 + 100 * j + 10 * k + i
if is_palindrome(bin(m)[2:]):
total += m

m = m * 10 + j
if is_palindrome(bin(m)[2:]):
total += m

print(total)
“`
Just run this code and it will print out the sum of all numbers less than one million which are palindromic in base $10$ and base $2$.
This solution works because it generates all possible base-10 palindromes less than 1,000,000 and then checks if they’re also palindromes in base-2. We don’t need to check even numbers because binary palindromes must be odd. This greatly reduces the search space and thus the computational complexity of the solution.

More Answers: