Does every pair of bases have a shared palindrome?

The shortest possible answer:

I don’t know.

The slightly longer answer:

The evidence suggests so, but I can’t prove it, nor can I find an existing proof. Maybe you can!

Notation:

An integer $x$ written with no other distinguishing feature is always in base $10$ . Otherwise, I will write an integer $x$ in its base $b$ notation as $[a_n, a_{n-1}, \dots, a_0]_b = \sum_{i=0}^{n} a_i b^i$ , where $0 < a_n < b$ (i.e. the leading digit is non-zero) and $0 \leq a_i < b$ (i.e. each other digit is less than $b$ ) for all other $a_i$ . A palindrome is an integer which reads the same forwards as backwards. More formally, an integer $x$ is a palindrome in base $b$ if $x = [a_n, \dots, a_0]$ and $a_{i} = a_{n-i}$ for all $0 \leq i \leq \lfloor \frac{n+1}{2} \rfloor$ . Such an integer $x$ will be called a dual palindrome (or just a dual) in bases $a$ and $b$ . That’s all really, let’s get stuck in.

Observation:

$5 = [1,0,1]_2 = [1,1]_4$ is a palindrome in base $2$ and base $4$ , I wonder if I can find such a palindrome for any pair of bases?
$1 = [1]_a = [1]_b$ is a palindrome for any pair of bases, but one-digit palindromes are not very interesting. Let’s make sure our palindrome has at least 2 digits in both bases.

Formal statement of the conjecture:

For any pair of integers $2 \leq a < b$ , there exists an integer $x$ such that $b < x$ and $x$ is a palindrome in both base $a$ and base $b$ .

Numerical evidence:

After enumerating a few small examples, I did what one should always do when one stumbles on a list of interesting numbers: plug it into the OEIS. It pointed me to A293925, which enumerates exactly my sequence, first authored in 2017. Note that it is natural to view this sequence as an upper-triangular matrix $T = (t_{ij})$ with the entry $t_{ij}$ at row $i$ less than column $j$ the least non-trivial dual palindrome in bases $i$ and $j$ . So I’m not the first person to think of this problem. But the major unstated premise is that this is in fact a sequence. It is not immediately obvious that:

every pair of bases has such a nice, finite, dual palindrome;
there isn’t some point/line in the matrix beyond which all pairs of bases fail to have a dual palindrome.

As is, the OEIS listing makes no mention of proving either of these statements, and my own perusal of the literature could not find anything either. (I am not saying it couldn’t possibly be some obscure corollary of a paper too dense to read or too obscure to be findable online, but even if it is, it needs to be brought to light. The OEIS does like to make sure its sequences are well defined and actually sequences. )

The element in the ith row, jth column is the smallest dual palindrome in bases i and j. Cells coloured by number of digits in base 10.

The next step is to generate some more data. I have put together a Google Colab notebook with my computational work on the matter. You’re welcome to have a look through it yourself, but ultimately generating more finite cases doesn’t really help a great deal with proving the conjecture. The details are not worth going over here, but it does produce some lovely images which I will scatter throughout. The important takeaway is that there is fairly thorough evidence to suggest that the conjecture is true. It would be selfish to state a conjecture based on purely computational results and demand somebody else solves the problem, without at least trying to solve the problem myself, so here goes. Fair warning I have no experience in number theory, so consider that a warning if you do.

Partial theoretical results

So far I can contribute the following results. They are incredibly elementary, but it feels like I would need a much stronger understanding of number theory to make a more insightful contribution.

Remark 1: $x = a^c + 1 = [1,0,0,\dots,0,0,1]_a = [1,1]_{a^c}$ is a palindrome in base $a$ and $a^c$ .

This fact is self-evident, and enough on its own to answer the second point, namely that there are finite entries to the matrix for arbitrarily large rows and columns. But of course the number of entries guaranteed by this result is quite sparse. We can generalise it as follows:

Remark 2: $x = a^{bc} + 1 = (a^b)^c + (a^b)^0 = [1,0,0,\dots,0,1]_{a^b} = (a^c)^b + (a^c)^0 = [1,0,0,\dots,0,1]_{a^c}$ is a palindrome in base $a^b$ and $a^c$ .

That gives us many more examples, and solves the problem whenever the two bases are both powers of a common integer $a$ . The following observation gives us a much less sparse family of dual palindromes. To motivate it, observe:

Same as the previous image, with a noteworthy sequence of duals identified between the yellow tramlines.

There seems to be a sequence of duals all a knight’s move apart, and each only 2 greater than the last, while the nearby duals seem to get bigger much quicker. The following remark explains why we see such a nice sequence.

Remark 3: If $x = b+1 = [1,1]_b = 2a+2 = [2,2]_a$ is a dual palindrome for bases $a$ and $b$ , then $x + 2 = (b+1)+2 = (b+2)+1 = [1,1]_{b+2} = (2a+2)+2 = 2(a+1)+2 = [2,2]_{a+1}$ is a dual palindrome for bases $a+1$ and $b+2$ .

$8 = [1,1]_7 = [2,2]_3$ , so there is a dual palindrome $x$ for all bases of the form $7+2i$ and $3+i$ , of the form $x = 8 + 2i = [1,1]_{7+2i} = [2,2]_{3+i}$ . This is still only scratching the surface of a general solution, but in a sense it is much denser, and it seems we should be able to generalise this observation. So let’s work on that for a while.

Remark 4: If $x = b+1 = [1,1]_b = da+d = [d,d]_a$ is a dual palindrome for bases $a$ and $b$ , then $x + d = (b+1)+d = (b+d)+1 = [1,1]_{b+d} = (da+d)+d = d(a+1)+d = [d,d]_{a+1}$ is a dual palindrome for bases $a+1$ and $b+d$ .

This is technically a generalisation, but not a very useful one. A cursory search of the first few cells reveals that most of the dual palindromes which would serve as the first in a sequence of this form are all of the form $[1,1]_b = [2,2]_a$ already. Eventually we find an example like $15 = [1,1]_{14} = [3,3]_4$ which generates an infinite family, but ultimately the constraint that the dual is a 2-digit palindrome in both bases is rather restrictive. Let’s call a dual like $[1,1]_b = [d,d]_a$ a starter dual, then we can call a sequence of duals each a $d$ to the right, $1$ down knight’s move away from the starter dual a $(d,1)$ -knight’s move family.

The $(3,1)$ -knight’s move family produced by remark 4.

The $(3,1)$ -knight’s move family produced by remark 4.

If we squint at our matrix, we eventually notice other knight’s move families, but it seems that having a starter dual is the hardest part, and the easiest way to find a family is to look for a streak of blues on a knight’s move diagonal, not by looking for the starter. Further, if we pick out a random cell, it would be nice if there were another cell just down and to the right of a slightly larger value, this would suggest it belongs to some sort of knight’s move family. But we typically don’t find this. More broadly, if most duals belonged to a knight’s move family, we would expect the size of the smallest dual palindrome to grow roughly linearly as we make knight’s moves, but again, we typically don’t see this. From this we can learn that any attempt to capture a general dual palindrome as part of a knight’s move family of duals will probably need that family to grow larger than linearly. So we need to generalise more. Eventually we might spot the following family:

A $(2,5)$ -knight’s move family growing by 10 each step.

A $(2,5)$ -knight’s move family growing by 10 each step.

Which motivates the following:

Remark 5: If $x =2b+2 = [2,2]_b = 5a+5 = [5,5]_a$ is a dual palindrome for bases $a$ and $b$ , then $x + 10 = 2b+2+10 = 2b+10+2 = 2(b+5)+2 = [2,2]_{b+5} = 5a+5+10 = 5a+10+5 = 5(a+2)+5 = [5,5]_{a+2}$ is a dual palindrome for bases $a+2$ and $b+5$ .

The interesting observation being that our knight’s move is now more than 1 step in both directions, and the increase in the size of the dual at each step is a common multiple of the digits. Like a broken record, we generalise as follows:

Remark 6: If $x =cb+c = [c,c]_b = da+d = [d,d]_a$ is a dual palindrome for bases $a$ and $b$ , then $x + cd = cb+c + cd = c(b+d)+c = [c,c]_{b+d} = da+d + cd = d(a+c)+d = [d,d]_{a+c}$ is a dual palindrome for bases $a+c$ and $b+d$ .

This feels like the end of the easy generalisations of what we’ve seen so far, in that we can take any dual palindrome $x$ which has two digits in both bases, and generate a knight’s move family with $x$ as the starter. To generalise further, we would either need to:

handle starters with more than two digits in either base,
generate a knight’s move family in an arbitrary direction, not one dictated by the digits of the starter, or
envision an entirely new approach to creating dual palindromes.

The last of these is a blind hope based on unique insight (that’s where somebody else can swoop in please!), not a predictable strategy, so really we are stuck with either of the first two. The second point would itself require some new insight, as everything we have done so far carefully chooses the step size at each knight’s move so it factors nicely with both digits, in general its not clear how we could do this. So we are left with the first point. Certainly it would be relevant to understand how many bases a typical minimum dual palindrome has. We can analyse the record entries of the sequence as a heuristic for the worst case scenario:

My first thought when seeing these records is to remark that the dual palindrome in bases 2 and 3 (literally the first entry) is by far the worst in terms of number of digits, even up to the first $\binom{1727}{2}$ entries. In some sense this is promising, maybe it is the lack of choices for the digits which is the main restriction, so for larger pairs of bases it should be easier. One might go so far as to say that the pair 2 and 3 is the worst possible pair. After a bit of meditation this is clearly not true, the smallest possible palindrome in base $2^{1000}$ has at least 1001 digits in base 2, so it definitely gets worse at this pair of bases, we could just never dream of enumerating the entries this far, so we get tricked by what are ultimately only small cases. If we measure not by the number of digits in the smaller base but instead the larger, there seems to be more hope. We already know that $x = [1,0, \dots, 01]_{2} = [1,1]_{2^{1000}}$ is a palindrome in bases 2 and $2^{1000}$ , so in this sense this pair of bases isn’t so problematic. But at the moment, all bets are off regarding base 2 and base $b = 2^{1000}+1$ . Given the mind-bogglingly large number of palindromes in base $b$ with less than 5 digits, it seems unlikely that we would need 6 or more digits to find one which is also a palindrome in base 2. Nonetheless, we see the number of digits in the larger base slowly increasing in the table above, so really who is to say. What we can say with confidence is we will often need to resort to more than 2 digits in at least the smallest base, so it seems more sophisticated techniques than the remarks above are required.

Results I’m not really sure what to do with

The heading speaks for itself, perhaps someone smarter than me can figure out why these might be useful observations.

Remark A: If $[a_0, a_1, a_2, \dots a_2, a_1, a_0]$ is palindrome with an even number of digits ( $n$ odd), then the formal polynomial:

$a_0 + a_1 b + a_2 b^2 + \dots + a_2 b^{n-2} + a_1 b^{n-1} + a_0 b^n$

has $b = -1$ as a root.

Proof:

$a_0 + a_1 (-1) + a_2 (-1)^2 + \dots + a_2 (-1)^{n-2} + a_1 (-1)^{n-1} + a_0 (-1)^n$

$= a_0 - a_1 + a_2 - \dots - a_2 + a_1 - a_0 = 0$

$[a_0, a_1, a_2, \dots a_{n-2}, a_{n-1}, a_n]$ a palindrome is a sufficient condition for $\sum_{i=0}^{n} a_{i} b^i$ to have $-1$ as a root, it is by no means necessary. This suggests some sort of Field-like behaviour with $b-1$ as a factor of the polynomial, but this holds for non-prime-power bases, and our coefficients do not truly behave like Field elements, we need to maintain the “carry-the-one” behaviour inherent to our base representation when we add a pair of polynomials.

Remark B: By colouring each cell of the table by residue class $\pmod{n}$ for various $n$ , we get the following:

Table of smallest dual palindromes coloured by residue class $\pmod{n}$ for various $n$ . Purple is 0, through to yellow is $n -1$ . [Warning: very big gif, might take a while to load.]

For each value of $n$ , we seem to get these consistent grid-like streaks of purple ( $0 \pmod{n}$ ) which becomes more apparent for larger $n$ . Why are they there? We can observe the following:

There are gaps, not every element on one of the gridlines is necessarily purple.
The gridlines are spaced $n$ units apart.
The vertical gridlines seem to be one unit wide while the horizontal gridlines seem to be two units wide.
They seem to become more clearly defined further down and to the right.
Some values of $n$ yield stronger lines than others.

More images for higher values of $n$ are available on the Colab.

Remark C: Of particular note is the $\pmod{2}$ colouring:

$\pmod{2}$ colouring. For technical reasons this image only shows the 500×500 table, but if you click the image you can view an even more enormous image which shows the 1000×1000 table in its full glory. Warning, the image is 7606×7616 pixels.

What gridlines 2 units apart would look like isn’t exactly clear, but we see interesting and varied emergent behaviour in different parts of the table:

In the top right we struggle to make out a pattern. There seem to be vertical streaks but they are very muddled.

In the bottom right we make out clear maze-line patterns reminiscent of some ancient pottery decoration.

Concluding remarks

Many thanks go to Robert G. Wilson v, without whose collaboration the depth of computational results would be noticeably more meagre.

If you have any further insight, please share 🙂

Edits

January 2023

I have traced this question back to 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. Friedman also attributes to Schimke a similar pair of polynomials for bases which differ by 2, depending on their parity, and states that Schimke believes a polynomial exists for all $P(a,a+n)$ .

At the time of writing I could not come up with a formal description of the maze-like pattern in the $\mod 2$ colouring. I now make the following observations. There are still imprecise up to some $m \neq 1$ which depends on the property, mostly because an exhaustive computer search for these properties would be a headache to code up, and consequently because my eyeballs started to hurt after a while. Nonetheless, each of these properties has been tediously verified up against the main diagonal. Inside the area between the $a = b$ diagonal and the $a=mb$ line, there does not exist a set of four entries $\{(a,b), (a+1,b), (a,b+1), (a+1,b+1)\}$ all the same colour, (i.e. a 2×2 square). Similarly, I can’t find any monochromatic S-tetrominos or Z-tetrominos. Conversely, it is effortless to find I, J, L, and T-tetrominos. Why would that be?

I summarised this problem in a post on MathsFeed.

smallest dual palindrome $x$ in bases $a$ and $b$	$a$	$b$	digits in base $a$	digits in base $b$
6643	2	3	13	9
9686	4	26	7	3
9902	7	34	5	3
16008	7	35	5	3
20512	30	37	3	3
33577	5	42	7	3
33621	34	51	3	3
40243	36	54	3	3
47723	38	57	3	3
55155	10	60	5	3
56115	40	60	3	3
65347	42	63	3	3
65883	11	66	5	3
73606	44	66	3	3
120250	57	68	3	3
248833	12	71	6	3
620832	11	88	6	3
648170	90	135	3	3
694314	92	138	3	3
44838080	42	139	5	4
2000608059	18	161	8	5
4045926645	24	191	7	5
25594427566	40	399	7	5
61756843258	35	489	7	5
906370255519	60	899	7	5
2873008152176	84	1175	7	5
84598768520000	72	1727	8	5