Project Euler Problem 36 Solution

Project Euler Problem 36 Solution

Double-base Palindromes

by {BetaProjects} | Project Euler & HackerRank

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:

  1. 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.
  2. dec2bas(n,b) - Converts a decimal number n to its equivalent in base b, where 2≤b≤9. For example, if n=585 and b=2, the output is 1001001001.
  3. is_palindrome(n) - Tests if a number n is a palindrome, returning True or False.

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 logo

Solves all test cases for Hackerrank Project Euler Problem 36

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"
L,b = map(int, input().split())
s = 0

for t in [0,1]: #even and odd length palindromes
    i,n = 1,0
    while n<=L:
        n = make_palidrome(str(i),t)
        if is_palindrome(dec_to_base(n,b)): s+= n
        i+= 1
print (s)

Last Word