modulomathy.com

#math trivia for #February15: 46 is a nontrivial (multi-digit) palindrome in base 4 (46 = 232 base 4) and which four other bases?

— Burt Kaliski Jr. (@modulomathy) February 15, 2012

A positive integer x can be expressed in any base b ≥ 2 as a sum of weighted powers

x = d_k-1 b_k-1 + d_k-2 b_k-2 + … + d₁ b + d₀

where k, the number of coefficients, is a positive integer; the leading coefficient d_k-1 is at least 1; and the remaining coefficients d_k-2, …, d₀ are between 0 and b-1.  (Base 1 is special, and will be covered later.)  The k coefficients form the digits of the base-b representation, and we write:

x = (d_k-1  d_k-2  …  d₁  d₀)_b

(the subscript outside the parentheses denotes “base b“).

In base 10, we have the familiar expression

46 = 4*10 + 6 = 46₁₀

Here, b = 10, k = 2, d₁ = 4, and d₀ = 6.

The same integer may be expressed base 4 as:

46 = 2*4² + 3*4 + 2 = 232₄ ;

in this case b = 4, k = 3, d₂ = 2, d₁ = 3, and d₀ = 2.  The base-4 representation 23₂₄ is a palindrome:  the same string forward and backwards.

The problem asks for which other bases b the representation of the decimal number 46 is a palindrome.

It is easy to see that if b ≥ 46, then the representation is always a palindrome.  For such bases, the representation has only one digit, i.e., k = 1, and the digit d₀ = 46.  A one-digit string is clearly the same forward and backwards.  Such palindromes are excluded from the solution because they are “trivial”:  no special construction is required. 

The other four bases must thus fall between 1 and 46.  

Trial and error is probably the easiest way to get the solution, which has many unknowns (base, number of digits, digit values), as well as constraints on the digit values.  But we can do a little reasoning to simplify the search.  First, consider two-digit representations; for these we need b ≥ 7.   A solution will thus involve a repeated pair of digits, so we’ll have

d*b + d = 46

for some digit d between 1 and b.  Factoring out the d gives

d*(b+1) = 46

so we must have d = 1 and b = 45, or d = 2 and b = 22.   (The other possible values of b are too small.) 

Two solutions so far:  11₄₅ and 22₂₂.

The rest we can get by trial and error counting down from base 6 to base 1.

• Base 6:  46 = 1*36 + 1*6 + 4 — no
• Base 5:  46 = 1*25 + 4*5 + 1 — yes
• Base 4:  46 = 2*16 + 3*4 + 2 — in problem statement
• Base 3:  46 = 1*27 + 2*9 + 0*3 + 1 — no
• Base 2:  46 = 1*32 + 0*16 + 1*8 + 1*4 + 1*2 + 0 — no

A third solution:  141₅.

The final base is a tricky one, because by the definitions above, the digits in base 1 would always be 0!  However, base 1, or unary notation, has a special provision:  the digits are always 1.  The number of digits thus equals the value being represented, and given that the digits are all one, the representation is the same forward and backwards:  a palindrome. 

The fourth solution:  1111111111111111111111111111111111111111111111₁.  (46 ones digits in all.)

Summarizing:  The four bases are 45, 22, 5 and 1.

A note on representations:  To represent a value in a base greater than 10, we need a way to  represent digits greater than 9.  In base 16, for instance, the digits 10 through 15 are typically represented as letters a through f;  46 would be represented as 2e₁₆.  Other bases, though less common in practice, can similarly use letters, and this works fine until base 36, after which we’ll need more than a through z.