#### 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 written with no other distinguishing feature is always in base . Otherwise, I will write an integer in its base notation as , where (i.e. the leading digit is non-zero) and (i.e. each other digit is less than ) for all other . A palindrome is an integer which reads the same forwards as backwards. More formally, an integer is a palindrome in base if and for all . Such an integer will be called a dual palindrome (or just a dual) in bases and . That’s all really, let’s get stuck in.

#### Observation:

- is a palindrome in base and base , I wonder if I can find such a palindrome for any pair of bases?
- 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 , there exists an integer such that and is a palindrome in both base and base .

#### 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 with the entry at row less than column the least non-trivial dual palindrome in bases and . 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 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: ** is a palindrome in base and .

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: ** is a palindrome in base and .

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

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 is a dual palindrome for bases and , then is a dual palindrome for bases and .

, so there is a dual palindrome for all bases of the form and , of the form . 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 is a dual palindrome for bases and , then is a dual palindrome for bases and .

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 already. Eventually we find an example like 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 a starter dual, then we can call a sequence of duals each a to the right, down knight’s move away from the starter dual a -knight’s move family.

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:

Which motivates the following:

**Remark 5: **If is a dual palindrome for bases and , then is a dual palindrome for bases and .

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 is a dual palindrome for bases and , then is a dual palindrome for bases and .

This feels like the end of the easy generalisations of what we’ve seen so far, in that we can take any dual palindrome which has two digits in both bases, and generate a knight’s move family with 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:

smallest dual palindrome in bases and | digits in base | digits in base | ||

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 |

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 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 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 is a palindrome in bases 2 and , 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 . Given the mind-bogglingly large number of palindromes in base 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 is palindrome with an even number of digits ( odd), then the formal polynomial:

has as a root.

Proof:

a palindrome is a sufficient condition for to have as a root, it is by no means necessary. This suggests some sort of Field-like behaviour with 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 for various , we get the following:

For each value of , we seem to get these consistent grid-like streaks of purple () which becomes more apparent for larger . 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 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 yield stronger lines than others.

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

**Remark C: **Of particular note is the colouring:

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:

#### 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 be the smallest non-trivial dual palindrome in bases and , Friedman attributes to Ulrich Schimke the formula for all , 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 .

At the time of writing I could not come up with a formal description of the maze-like pattern in the colouring. I now make the following observations. There are still imprecise up to some 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 diagonal and the line, there does not exist a set of four entries 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.

You must be logged in to post a comment.