Multi-Base Palindromes

Computer Science Level 4

A number is a palindrome if it is the same number when written forward and backward. Some base-10 palindrome can be converted into other bases and still remain a palindrome. Define $f(x)$ as the total number of bases less than $x$ and greater than 1 that a base-10 palindrome $x$ can be converted into and remain a palindrome.

Find the number $n$ (in base 10) that satisfies the following conditions:

$f(x)$ is maximized over the domain $0<x<100000$ when $x=n\in \Bbb{Z}.$
$1<n<100000.$
$n$ is a palindrome.

Details and Assumptions:

$x_a$ means that $x$ is written in base $a;$ for example, $101_2=5_{10}$ .
$33_{10}=1000001_2$ and $33_{10}=11_{32}$ .
So 33 is a palindrome in base 2, 10, and 32, and thus $f(33)=3$ .
$1,6,8,0_{10}=40,40_{41},$ which means $1680$ is a palindrome in base 41 because on the RHS, each 40 represents a single digit. $($ This example uses a notation that separates digits of a number using commas. For example, $5,5,5_{10}=555_{10}.)$
Do not pad the start of the number with 0's. For example, 10 is not a palindrome, though it could be written as 010.

The answer is 48384.

2 solutions

Christopher Boo
Jun 21, 2017

The answer is $48384$ which is a palindrome in $39$ different bases.

palindromes = []

"""
  return palindromes in base _base of length _length
  while generating append the intermediate palindromes into the global palindrome list
"""
def generatePalindrome(base, length):
    global palindromes
    if length < 1:
        ret = [[]]
    elif length == 1:
        ret = [[t] for t in range(base)]
    else:
        tmp =  generatePalindrome(base, length - 2)
        ret = [[t] + pal + [t] for t in range(base) for pal in tmp]
    palindromes += ret
    return ret

def isPalindrome(num):
    if len(num) < 2:
        return True
    else:
        return num[0] == num[-1] and isPalindrome(num[1:-1])

def toBase(num, base):
    if num < base:
        return [num]
    else:
        return toBase(num / base, base) + [num % base]

generatePalindrome(10, 5) # this adds palindrome of length 1, 3, 5 to the list
generatePalindrome(10, 4) # this adds palindrome of length 2, 4 to the list

palindromes = list(filter(lambda x:            len(x) > 0 and x[0] != 0, palindromes))
palindromes = list(   map(lambda x: int(''.join(map(str, x))), palindromes))

ans = 0
palBases = []
for pal in palindromes:
    tmp = []
    for base in range(2, pal):
        if isPalindrome(toBase(pal, base)):
            tmp.append(base)
    if len(tmp) > len(palBases):
        ans = pal
        palBases = tmp

print ans, len(palBases), palBases

Nicola Mignoni
May 12, 2018

First, let's create a function (called $\text{basech}$ ) that gives as output an array that is the representation of a number $n$ in base $b$ . Basically, it's a loop that put the reminder of $\frac{n}{b}$ in the final array, than substitutes $n=\frac{n}{b}$ , until $n=0$ . Here's the MATLAB code

function [res]=basech(n,b)
h=0;
while eq(n,0)==0
    h=h+1;
    res(h)=mod(n,b);
    n=floor(n/b);
end
res=flip(res);

#Final code
clear
k=0;
b=0;
t=0;
for i=0:99999
    if flip(num2str(i))==num2str(i)
        k=k+1;
        pal(k,1)=i;
    end
end
for j=1:size(pal,1)
    for h=2:pal(j,1)-1
        if basech(pal(j,1),h)==flip(basech(pal(j,1),h))
            b=b+1;
        end
    end
    t=t+1;
    total(t,:)=[pal(j,1) b];
    b=0;
end

Multi-Base Palindromes

The answer is 48384.

2 solutions

0 pending reports