Find palindromes in two consecutive number bases?

Update: So far I've been able to find (I believe all) solutions for $$d=3,5,7$$, and partially for $$d=9$$. If It turns out that a closed form for all solutions for a fixed (large enough) $$d$$ is too messy to compile, I'll probably include those as a partial self-answer here.

What is allowing me to solve and find closed forms for a fixed $$d$$ case now, is solving the related system with a CAS like Mathematica - and is now summarized in the answer below.

Question

Can we generate all numbers which are palindromic in two consecutive number bases $$(b, b+1)$$ and have $$(2d+1, d\in\mathbb N)$$ digits when written in their palindromic bases?

$$3$$ digit pattern

I've found the pattern for $$d=1$$, the $$3$$ digit palindromes rather straightforward (simple):
(Just look at the examples below and you'll see it)

All solutions that are palindromic in number bases $$b\in\{n+1, n+2\}$$ for $$n\gt3$$, are given by the following equation: (pick all $$k$$ in range to get a solution per value of $$k$$)

$$P_3(n) = \begin{cases} n^3+2n^2+2n, & \text{k=1} \\ n^3-n^2(k-4)-n(k-7)-3k+4, & \text{n\gt k \gt1} \end{cases}$$

That gives you $$n-1$$ solutions, which are palindromic in $$n+1,n+2$$ bases.

The digits of given examples in base $$b=n+1$$ are: $$[n-k+1], [(n-k+2) \mod (n+1)], [n-k+1]$$

$$\text{(Examples)}$$ You can see the solutions for $$n=4,5,6$$ below:

5  67 3 [2, 3, 2] [1, 5, 1]
5  98 3 [3, 4, 3] [2, 4, 2]
5 104 3 [4, 0, 4] [2, 5, 2]

6  92 3 [2, 3, 2] [1, 6, 1]
6 135 3 [3, 4, 3] [2, 5, 2]
6 178 3 [4, 5, 4] [3, 4, 3]
6 185 3 [5, 0, 5] [3, 5, 3]

7 121 3 [2, 3, 2] [1, 7, 1]
7 178 3 [3, 4, 3] [2, 6, 2]
7 235 3 [4, 5, 4] [3, 5, 3]
7 292 3 [5, 6, 5] [4, 4, 4]
7 300 3 [6, 0, 6] [4, 5, 4]

Same pattern holds for all $$n\gt3$$, as observed.

First column is the base $$b=n+1$$, second is the number, third are the digits, and last two are number representations in number bases $$(n+1,n+2)$$.

The solutions for $$n=2,3$$ which are not included in $$P_3(n)$$ are $$10, 46$$ ;

Where number bases $$(2,3)$$, the $$n=1$$ case, has no solutions.

$$5,7,9\dots$$ digit pattern?

I've found patterns for $$5,7,9,\dots$$ digits to be similar among themselves but not so simple as the three digit one, as they seem to be more unpredictable with more digits.

Can we define a function / algorithm to generate all the solutions for some $$P_d(n)$$?

Meaning, the solutions are palindromic in bases $$(n+1,n+2)$$ and have $$d$$ digits?

$$P_3(n)$$ above is the simplest example, which generates all solutions for $$(n+1,n+2)$$ bases by iterating $$k\in(n,1]$$. How can one find patterns for other digit cases? (see linked code below to generate examples for some $$2d+1$$ digits)

Use linked code to generate solutions for any case of $$2d+1$$ digits by simply changing the digit = 4 variable to some other integer. (You can also generate from/to any number base)

$$9$$ digit pattern?

I'm interested in the $$9$$ digit pattern before the rest.

(Since this would help search for solutions for numbers palindromic in three consecutive bases which also have $$9$$ digits; where $$3,5,7$$ digit patterns were found, but no examples for $$\ge9$$ digits have been found. - I've posted these patterns in my question regarding numbers palindromic in four or more consecutive bases. The MSE version of the question is linked in the comments.)

You can see all solutions for bases up to $$32$$ here, which were generated by my python code.

Linked code checks every palindrome in some number base to see if it is palindromic in bases $$(b, b+1)$$; but this is extremely slow at larger bases, so I need to find $$P_9(n)$$ to generate them instead.

In the linked output text, you can notice patterns in digits. For example, notice patterns emerging at base $$b=30$$, for first couple examples; highlighted here.

Can you predict these patterns for some base $$b$$, at least to some degree? I couldn't.

• You might be interested in this question about palindromes in 4 successive bases – Ross Millikan Nov 14 '17 at 20:15

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.

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: