Find palindromes in two consecutive number bases?

This is a (partial) answer for $d=3,5,7,\ge 9$. - I doubt there is a nice general from for all $d$.

Update: The relevant Diophantine system is now asked about on Math Overflow.

The problem in terms of Diophantine equations

Notation

We have palindrome in base $b$ digits: $(a_1,\dots,a_d)$ and it holds $a_i=a_{d-i+1}$, we write:

$$(a_1,\dots,a_d)_b=\sum_{i=1}^{d}a_i b^{d-1}$$

The problem: Finding palindromes in two consecutive bases for a fixed case of $d=2l+1$ digits.

Finding $b,b+1$ palindromes is equivalent to $b,b-1$ palindromes, so lets work with the latter.

We want to find palindromes with $d$ digits in both bases exactly. - Thus we will exclude solutions with $(d,d+k)$ digits for $k\gt 0$ (according to the question, we are after $d$ digit palindromes in both bases). This means that we:

Want to find solutions for $b,a_i,A_i$ where $a_{i}=a_{d-i+1},A_{i}=A_{d-i+1}$:

$$ \sum_{i=1}^{d} a_i b^{d-i}=\sum_{i=1}^{d} A_i (b-1)^{d-i} $$

And $0\le a_i\lt b,0\le A_i\lt b-1,a_1\ne 0,A_1\ne 0$.

We can express $A_i$ in terms of $a_i$ by expanding $((b-1)+1)^{d-i}$ by binomial theorem. We can also use a trick and introduce $o_i\in\mathbb Z$ parameters that are defined such that inequalities for $A_i$ are satisfied. We have:

$$ A_i=\sum_{k=1}^{i}\binom{d-k}{i-k}a_k + o_{i} - o_{i-1} (b-1) $$

Since all palindromes are known, $a_i$ are chosen such that $a_i$ inequalities are satisfied. By going over all valid sets of $\{o_1,\dots,o_d\}$ parameters such that the $A_i$ inequalities are satisfied as well, we have split the original problem into just solving a bunch of linear Diophantine equations whose order depends on $d$.

Note: If we want to generalize this for $k\gt 0$ cases, we can simply handle them by introducing additional digits $A_i$ and additional $o_i$ parameters and having:

$$A_i=o_{i} - o_{i-1} (b-1)$$

For $i\le 0$. And then we need to adjust the equality for palindromes:

$$A_{i_A}=A_d,A_{i_A+1}=A_{d-1},\dots \le b-1,A_{i_A}\ne 0$$

Where $i_A$ is the smallest index of the non-zero $A_i$ digit.

Solving the above system

We are interested in palindromes in two consecutive bases with $2d+1$ digits in both of those bases, so we have $k=0$ always. This means we aren't after solutions like $10=(1,0,1)_3=(2,2)_4$ for example.

The above system can be partially solved using a Computer-Algebra-System, that is, a CAS, for fixed cases of $d$. Doing it by hand appears to be too messy to do with my current approach for $d\gt 3$ (See $d=3$ solution for $b,b-1,b-2$ palindromes from this question). A manual obstacle is handling all the $o_i$ cases individually which get more numerous the larger the $d$ case, and more complex to find.

But this does have limitations, as it gets harder to solve fully for larger $d$ computationally.

Now, lets call each valid $\{o_1,\dots,o_d\}$ pick of parameter values a normalization case of the digits. Each valid normalization can either yield none, finitely, or infinitely many solutions.

Solutions for $d=3$

It turns out the only $o_i$ normalizations that can give solutions are $\{1,1\},\{2,1\}$, which give the following solutions for $x,y\in\mathbb N_0$:

$$\begin{array}{} 1.^* & (1+x,4+y,1+x)_{5+x+y} \\ 2. & (2+x,5,2+x)_{6+x} \end{array}$$

In base $b,b-1$. This gives solutions like you described and explains why your $P_3$ has two cases. There are two families of solutions like you can see here. For example, the smallest given is: $46=(1,4,1)_5=(2,3,2)_4$ for $x=y=0$ and from first family.

Notice the $*$ next to the first pattern. This marks that a subuset of those solutions can be palindromic in a third consecutive base $b-2$.

Solutions for $d=5$

It can be shown there are $12$ normalizations that yield solutions, among which $8$ give familie(s) of solutions, and the other $4$ give finitely many solutions.

Here are the families of solutions based on the $1.-8.$ normalizations, where $a_2,a_3$ were expressed in terms of $b,a_1$, for $x,y\in\mathbb N_0$ (where $*$ marks that a subset of these solutions can also be palindromic in a thrid consecutive base $b-2$), we have $(a_1,a_2,a_3,a_2,a_1)_b$ given by:

$$\begin{array}{} & a_1 & a_2 & a_3 & b \\ 1. & 3+x+y & -2 a_1+b-1 & 3 a_1 -b+2 & 11+3x+2y \\ 2. & 11+2x+y&-2 a_1+2 b&3 a_1-2b+1 &17+3 x+y \\ 3.^* & 20+2x+y&-2 a_1+2b+1 &3a_1 -b-2 & 38+3 x+2 y \\ 4. & 1+x & -2 a_1+b & 3a_1-1 & 11+3x+y \\ 5. & 14+x &-2a_1+2b+2 & 3a_1-2b-2 & 20+x \\ 6. & 4+x &-2a_1+b-1&3a_1+1 &14+3x \\ 6. & 3+x &-2a_1+b-1&3a_1+1 &12+3x \\ 6. & 2+x &-2a_1+b-1&3a_1+1 &10+3x \\ 6. & 1+x &-2a_1+b-1&3a_1+1 &9+3x \\ 6. & 1+x &-2a_1+b-1&3a_1+1 &8+3x \\ 7. & 12+x &-2a_1+b+1&3 a_1 -b-1 &23+2 x \\ 7. & 10+x &-2a_1+b+1&3 a_1 -b-1 &20+2 x \\ 7. & 8+x &-2a_1+b+1&3 a_1 -b-1 &17+2 x \\ 7. & 6+x &-2a_1+b+1&3 a_1 -b-1 &14+2 x \\ 7. & 7+x &-2a_1+b+1&3 a_1 -b-1 &20+2 x \\ 7. & 6+x &-2a_1+b+1&3 a_1 -b-1 &17+2 x \\ 7. & 5+x &-2a_1+b+1&3 a_1 -b-1 &14+2 x \\ 7. & 4+x &-2a_1+b+1&3 a_1 -b-1 &11+2 x \\ 8. & 11+2x &-2 a_1 + 2 b& 3 a_1 -b & 17+3x \\ 8. & 10+2x &-2 a_1 + 2 b& 3 a_1 -b & 16+3x \\ 8. & 16+2x &-2 a_1 + 2 b& 3 a_1 -b & 31+3x \\ 8. & 15+2x &-2 a_1 + 2 b& 3 a_1 -b & 29+3x \\ 8. & 14+2x &-2 a_1 + 2 b& 3 a_1 -b & 27+3x \\ 8. & 13+2x &-2 a_1 + 2 b& 3 a_1 -b & 25+3x \\ 8. & 12+2x &-2 a_1 + 2 b& 3 a_1 -b & 23+3x \\ 8. & 11+2x &-2 a_1 + 2 b& 3 a_1 -b & 21+3x \\ 8. & 10+2x &-2 a_1 + 2 b& 3 a_1 -b & 19+3x \\ 8. & 9+2x &-2 a_1 + 2 b& 3 a_1 -b & 17+3x \\ 8. & 9+2x &-2 a_1 + 2 b& 3 a_1 -b & 15+3x \\ 8. & 8+2x &-2 a_1 + 2 b& 3 a_1 -b & 15+3x \\ 8. & 8+2x &-2 a_1 + 2 b& 3 a_1 -b & 14+3x \\ 8. & 7+2x &-2 a_1 + 2 b& 3 a_1 -b & 13+3x \end{array}$$

And here are solutions for normalizations $9.-12.$, where we have solution, base lists:

9. {2293, 6, 6148, 7, 10658, 8}
10. {344954, 14, 502179, 15, 712154, 16, 987167, 17, 1341282, 18}
11. {3074, 6, 5854, 7, 7703, 7, 13459, 8, 16708, 8, 27310, 9, 42324, 10, 50605, 10, 75157, 11, 125430, 12, 174596, 13, 270487, 14, 526600, 16}
12. {7801, 8, 12547, 9, 17876, 9, 27472, 10, 40504, 11, 52825, 11, 75399, 12, 93088, 12, 104549, 13, 129198, 13, 174934, 14, 208423, 14, 231874, 15, 276395, 15, 359797, 16, 460807, 17, 535336, 17, 675996, 18, 842732, 19, 1183747, 20, 1444009, 21, 2347894, 23}

Partial solutions for $d=7$

There appear to be $61$ normalizations that have solutions, out of which $24$ give familie(s) of infinite solutions each. So the list of the closed forms will be at least as three times as long as the previous case.

Here are some of those infinite families: (these were not sorted like the previous case since this digit case is not complete yet) given $c_1,\dots,c_6\in\mathbb N$, we have $(a_1,a_2,a_3,a_4,a_3,a_2,a_1)_b$ given by:

$$\begin{array}{} & a_1 & a_2 & a_3 & a_4 & b \\ 1. & 64+4 c_1+2 c_2+c_3 & -1+3 b-3 a_1 & c_2 & 5-4 b+5 a_1-2 c_2 & 71+5 c_1+2 c_2+c_3\\ 2. & 63+4 c_1+3 c_2+2 c_3 & -2+2 b-3 a_1 & c_1 & 6-3 b+5 a_1-2c_1&101+6c_1+5c_2+3c_3 \\ 3. & 3+c_1+c_2+c_3+c_4 & -2+b-3 a_1 & c_1 & 4-b+5 a_1-2 c_1 &15+3c_1+5c_2+4c_3+3 c_4\\ 4. & 1+c_1 & 1+b-3 a_1& 26+5 c_1+c_2+c_3& -5+2 b+5 a_1-2 a_3 & 51+5 c_1+c_2+2 c_3 \\ 5. & 4+2 c_1+c_2+c_3+c_4 & -1+b-3 a_1 & 4+5 c_1+2 c_2+c_3 & 1+5 a_1-2 a_3 & 19+6 c_1+3 c_2+3 c_3+5 c_4+c_5 \\ 5. & 3+2 c_1+c_2+c_3+c_4 & -1+b-3 a_1 & 1+5 c_1+2 c_2+c_3 & 1+5 a_1-2 a_3 & 16+6 c_1+3 c_2+3 c_3+5 c_4+c_5 \\ 5. & 3+2 c_1+c_2+c_3+c_4 & -1+b-3 a_1 & 5 c_1+2 c_2+c_3 & 1+5 a_1-2 a_3 & 17+6 c_1+3 c_2+3 c_3+5 c_4+c_5 \\ 6. & 19+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 47+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 65+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 17+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 42+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 60+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 15+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 37+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 55+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 13+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 32+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 50+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 11+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 27+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 45+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 9+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 22+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 40+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 7+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 17+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 35+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 5+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 12+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 30+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 3+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 9+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 27+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 3+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 8+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 26+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 3+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 7+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 25+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 2+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 5+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 24+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 6. & 1+2 c_1+c_2+c_3+c_4 & b-3 a_1 & 2+5 c_1+5 c_2+4 c_3+3 c_4+c_5 & -2+b+5 a_1-2 a_3 & 23+6 c_1+5 c_2+4 c_3+3 c_4+2 c_5+c_6 \\ 7. & ? & ? & ? & ? & ? \end{array}$$ $$ \dots $$

Where the rest are not yet solved via my method. I've implemented it in Mathematica to solve the stated problem system of equations, but it is having trouble getting solutions in terms of some parameters. The $o_i$ sets of parameters which haven't been solved yet, and represent normalizations $7.-24.$, are:

$$\begin{array}{} & \{o_1,o_2,o_3,o_4,o_5,o_6\} \\ 7. & \{1, 6, 14, 17, 12, 4\} \\ 8. & \{1, 6, 12, 14, 9, 3\} \\ 9. & \{2, 5, 10, 10, 7, 2\} \\ 10. & \{2, 5, 8, 7, 4, 1\} \\ 11. & \{3, 10, 17, 17, 10, 3\} \\ 12. &\{3, 10, 19, 20, 13, 4\} \\ 13. &\{3, 10, 21, 23, 16, 5\} \\ 14. &\{3, 11, 20, 21, 13, 4\} \\ 15. &\{3, 10, 15, 14, 7, 2\} \\ 16. &\{3, 11, 18, 18, 10, 3\} \\ 17. &\{4, 10, 14, 11, 5, 1\} \\ 18. &\{4, 10, 16, 14, 8, 2\} \\ 19. &\{5, 15, 23, 21, 11, 3\} \\ 20. &\{5, 15, 25, 24, 14, 4\} \\ 21. &\{5, 15, 27, 27, 17, 5\} \\ 22. &\{5, 16, 26, 25, 14, 4\} \\ 23. &\{5, 16, 24, 22, 11, 3\} \\ 24. &\{6, 15, 24, 21, 12, 3\} \end{array}$$

For some reason I was unable to directly get an output in terms of $c_i$ constants for these unsolved normalizations. It is still possible to get solutions from unsolved cases for fixed bases $b$ at a time, and then extract the patterns and families from the solutions. - The difference being, we then can't claim these are all and proven solutions like those in $d=3,5$ cases, unless we also manually prove them afterwards.

The $25.-61.$ normalization cases give finitely many solutions. This list of solutions is too long to include here, so it will be accessible on an external source.

Solving for $d\ge 9$

Using the system presented, it should be possible to find all closed forms for a fixed case of $d$ digits like I have done for first three.

The case $d=9$ has at least $443$ normalizations and at least $77$ of those give familie(s) of infinitely many solutions. (At least - I haven't yet computed all the normalizations).

The larger cases have much more. But searching for all solutions for fixed $d\ge 9$ does not seem practical as there does not appear to be a nice closed form to encapsulate them all - and they get very hard to fully normalize in all possible ways using my current computational method of the mentioned problem system.

A solution to this would be to find an efficient algorithm to compute these patterns and then store and access them computationally?

So far, we can notice patterns in these families:

$$\begin{array}{|cccccccc} \hline d & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & \dots \\ \hline 1 & \color{blue}{a_1} & 0 & 0 & 0 & 0 & 0 & \dots \\ 3 & c_0 & \color{blue}{-1a_1+c} & 0 & 0 & 0 & 0 & \dots \\ 5 & c_0 & -2a_1+c & \color{blue}{3a_1+c} & 0 & 0 & 0 & \dots \\ 7 & c_0 & -3a_1+c & c_0 & \color{blue}{5a_1-2a_3+c} & 0 & 0 & \dots \\ 9 & c_0 & -4a_1+c & c_0 & 14a_1-3a_3+c & \color{blue}{-21a_1+4a_3+c} & 0 & \dots \\ 11 & ? & ? & ? & ? & ? & \color{blue}{?} & \dots \\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \color{blue}{\dots} \\ \end{array}$$

Where $c_0$ is an expression depending on some free parameters $c_i\in\mathbb N$, and $c$ is an expression depending on $c_0$ and base $b$.

Maybe finding these patterns for all $d$ can help solve the problem of finding such an efficient algorithm.

This table is explored further here, based on data of $d$ up to $29$.

Alternate approach

Perhaps closed forms for fixed $d$ are not realistically possible to tabulate all. Alternate ways of finding more palindromes in two consecutive bases that might not belong to these solutions is to try to find isolated patterns across cases of $d$ which is no longer fixed:

• This question asks if at least one such pattern can be found.