A simple and seemingly unsolved palindrome problem

It seems that the symmetry-obsessive brain of a human cannot resist the simple delight of a palindrome, that is a word or number which remains unchanged when written forwards or backwards. This makes palindromic numbers a popular object of study in recreational mathematics, despite their apparent uselessness for ‘real’ maths.

As well as being pattern-mad, us humans are also mostly pentadactyl bipeds, so the palindromes we usually bump into in the wild are written in base ten. But why be constrained by our own anatomy? An integer can be a palindrome in any base, and even more delightfully, it can be a palindrome in more than one base at the same time!

Take five as an example — it is written as 101 in base 2, and 11 in base 4, so we might call it a dual palindrome for the pair of bases 2 and 4.

The question I pose is: Does every pair of bases have a dual palindrome? The answer to this question is, rather boringly, yes. The unit one is written palindromically as 1 in any base. But that answer doesn’t feel like it counts, so I choose to persevere.

Let’s say a dual palindrome is non-trivial if it has more than one digit in both bases. Now, does every pair of bases have a (non-trivial) dual palindrome? A293925 in the OEIS lists the smallest such dual palindrome for all pairs of bases less than 13, and examples for all pairs of bases less than 511 (along with a lot more details and calculations) are available in a living post on my personal page. However, as far as I can tell, the question remains unanswered in general. If you want to know all the details, head over there, but I’ll just share my favourite observations here.

Colouring by congruence class

Fix an $n$ , and for each smallest non-trivial dual palindrome in bases $a$ and $b$ , colour the $(a,b)$ entry of a table according to the palindrome’s congruence class $\mod n$ . If we assign purple to $0 \mod n$ through to yellow for $n-1 \mod n$ , then vary $n$ over $2 \leq n \leq 11$ , we get the above gif. For $n = 30, 50, 70, 100$ , we get the below images.

It only takes a bit of squinting to notice fields of green fenced off by distinctly (but not entirely) purple walls, arranged in a square grid $n$ units wide. Why?

Colouring modulo 2

Considering the $n=2$ case more carefully in the above image, we notice two different types of pattern depending on the location. Close to the $a = b$ diagonal, we see maze-like patterns reminiscent of an ancient pottery decoration. Further from the diagonal, the colouring seems much more random, but certainly there are more vertical streaks of yellow than horizontal streaks. Why?

Zooming in on different parts of the larger image above, we see clear differences in distribution.

Explicit constructions

I have been able to trace our main question back as far as Question #3 of Erich Friedman’s Problem of the month, June 1999. Letting $P(a,b)$ be the smallest non-trivial dual palindrome in bases $a$ and $b$ , Friedman attributes to Ulrich Schimke the formula $P(a,a+1) = 2a^2 + 3a +2 = (a+1)^2 + a(a+1) + 1$ for all $a \geq 4$ , which provides the smallest non-trivial dual palindrome in bases which differ by 1.

Can you see why $P(a,a+1)$ is always a dual palindrome? If so, can you prove that it is the smallest for for all $a$ ?

Friedman also attributes to Schimke a similar pair of polynomials $P(a,a+2)=(3a^2+6a+2)/2$ for even $a\geq 8$ , and $(a^2+4a+3)/2$ for odd $a \geq 5$ for bases which differ by 2, and states that Schimke believes that such a polynomial exists for all $P(a,a+n)$ .

I will leave it as another exercise to check these polynomials for yourself. That we have two different polynomials based on the parity of $a$ is not promising for a general formula for all $P(a,a+n)$ , but perhaps if we shed the need for our polynomial to yield the smallest such dual palindrome, we can make some progress on our question.