Project Euler Problem 36 Statement
The decimal number, 585 = 10010010012 (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.)
Solution
Look, I am growing very weary of these inane, novelty questions. Solution (only odd numbers stand a chance):
print (sum (n for n in range(1, 1000000, 2) if str(n)==str(n)[::-1] and str(bin(n))[2:]==str(bin(n))[2:][::-1]))
The Project Euler problem is a subset of the HackerRank version, so I’ll solve that one next.
The solution presented below uses three key lambda functions:
make_palindrome(x,t)
- Makes palindromes, duh. Given a number as a string, it creates two types of palindromes:- Even length (t=0): If x=12345, produces 1234554321. The given x concatenated with its reverse.
- Odd length (t=1): If x=12345, produces 123454321. The given x concatenated by is reverse with the last digit removed.
dec2bas(n,b)
- Converts a decimal number n to its equivalent in base b, where 2≤b≤9. For example, ifn=585
andb=2
, the output is 1001001001.is_palindrome(n)
- Tests if a number n is a palindrome, returningTrue
orFalse
.
To find these special numbers, we don't need to examine every single number under a million. Instead, we can narrow our search by focusing only on palindromes, reducing the possibilities from a million to just over a thousand. Then, we check each of these palindromes to see if they remain a palindrome when converted to base b and add them to the sum if they do. Lastly, we, um, well, print the sum.
HackerRank version
HackerRank Project Euler 36 Find the sum of all natural numbers, less than N, which are palindromic in base 10 and base b, where 2≤b≤9.
Python Source Code
make_palidrome = lambda x, t: int(x + (x[::-1] if t==0 else x[:-1][::-1]))
is_palindrome = lambda n: str(n)==str(n)[::-1]
dec_to_base = lambda n, b: (dec_to_base(n // b, b) + str(n % b)).lstrip("0") if n > 0 else "0"
N, K = map(int, input().split())
s = 0
for t in [0,1]: #even and odd length palindromes
i,n = 1,0
while n<=N:
n = make_palidrome(str(i),t)
if is_palindrome(dec_to_base(n,K)): s+= n
i+= 1
print(s)
Last Word
- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A007632: Numbers that are palindromic in bases 2 and 10.
- Results <1,000,000,000,000, i.e., 12 or fewer digits (reduced to 1,111,114 palindromic base 2 numbers):
sum([1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939, 1290880921, 7451111547, 10050905001, 18462126481, 32479297423, 75015151057, 110948849011, 136525525631]) = 394832891346