# Special linear Diophantine system - is it solvable in general?

Background: An equivalent question was asked on MSE almost two years before this post now. It was never fully resolved. - Here, we are asking if further progress can be made.

Motivation

• Solving this will help find a "closed form" for double palindromes: A279092.

• Solving this, will help solve a similar Diophantine system whose solutions are "intersections" of: solutions to this problem for variable $$b=b_0$$ with solutions to this problem for variable $$b=b_0-1$$.

• Solving this problem, or solving the above linked similar Diophantine system using this problem's solution, will then help answer the question: Can a number be palindromic in more than 3 consecutive number bases?

Context

Let $$n=(a_1,a_2,\dots,a_{l},a_{l+1},a_{l+2},\dots,a_{d-1},a_d)_b$$ be digits of a $$d=2l+1,l\in\mathbb N$$ palindrome $$n\in\mathbb N$$ in some number base $$b\in\mathbb N,b\gt 2$$. "Palindrome" means: $$a_i=a_{d-i+1},i=1,\dots,l+1$$.

Solving the Diophantine system presented in the problem section, is equivalent to finding numbers that are simultaneously palindromic (palindromes) in two consecutive number bases $$b,b-1$$, and have exactly $$d$$ digits in both bases.

This can be generalized to $$d_1,d_2$$ digits in those two bases respectively, then $$d=\max\{d_1,d_2\}$$ is called the degree of palindrome $$n$$. We are observing the $$d_1=d_2=d$$ case, and the corresponding Diophantine system, in the problem section.

"Almost-all" numbers from A279092 are solutions to the below given Diophantine system. Specifically, all numbers from the linked OEIS sequence are either:

• a solution to the Diophantine system given in the problem section. (This system represents the $$d_1=d_2$$ case in the context of the mentioned generalization to $$d$$ as a degree.)
• a solution to the other part of the mentioned generalization. That is, the $$d_1\ne d_2$$ case.

We want to find "closed forms" for these simultaneous palindromes in two consecutive bases.

We formulated the following equivalent Diophantine system:

• Write the base $$b$$ palindrome $$n$$ in base $$b-1$$, using the binomial theorem on $$a_i(b)^j=A_i((b+1)-1)^j,j=0,\dots,d-1$$, to have base $$b-1$$ digits $$A_i$$ in terms of base $$b$$ digits $$a_i$$. Then introduce $$o_i$$ parameters defined to satisfy the inequalities on digits in base $$b-1$$, so we actually can have a valid base $$b-1$$ representation. Now solve for $$A_{i}=A_{d-i+1},i=1,\dots,l+1$$ to obtain palindromes, which is the given Diophantine system below (under conditions, so representations in both bases are valid):

Problem

Given $$d=2l+1,l\in\mathbb N$$, find all integers $$a_1\in[1,b),a_2,\dots,a_{l+1}\in[0,b),b \gt 2$$ such that:

$$\sum_{s=1}^{i}\binom{d-s}{d-i}a_s + o_{i} - o_{i-1} (b-1)= \sum_{s=1}^{d-i+1}\binom{d-s}{i-1}a_s + o_{d-i+1} - o_{d-i+1} (b-1)$$

For $$i=1,2,\dots,l+1$$, where $$o_1,\dots,o_{d-1}\in\mathbb Z$$, $$o_0=o_{d}=0$$ are some integers, and such that for all $$i\gt 1$$, both LHS and RHS from all of the $$l+1$$ equalities are $$\in[0,b-1)$$, and for $$i=1$$, they are $$\in[1,b-1)$$. Notice that for $$i=l+1$$, equalitiy holds, and only RHS,LHS conditions need to be applied.

For every $$x=(a_1,\dots,a_{l+1};b)$$, there either exist unique $$o_1,\dots,o_{d-1}$$ such that (under which) $$x$$ is a solution to the system, or it is not a solution to the system.

The $$d=3,5,7,\dots$$ is called the degree, and $$l=1,2,3,\dots$$ the order, of this system.

Is this solvable for $$d=2l+1$$ in general, for all $$x=(a_1,a_2,\dots,a_{l+1};b)$$?

• So far, I found one family of solutions, that gives infinitely many solutions $$x$$, for every fixed $$d$$. But this is just a drop in the ocean of all solutions (families) that haven't been found.

Or, how can we go about solving this, and obtaining solutions, for arbitrary fixed $$d$$?

• I've solved it for $$d=3,5$$. For fixed $$d=5$$ already, the "closed form" for all of the solutions seems messy, as you will see by the end of this post.

My progress on families of solutions across all $$d$$

I don't know how to solve for all solutions in general. But I did find one family of solutions, giving infinitely many solutions for every $$d$$ (Thanks to @Peter). - This result is given in the context of double palindromes in the linked Peter's claim. This claim (result) is now proven.

That is, we have the following family of solutions;

$$x=\left(\left\{a_i=\begin{cases}b-\binom{2l_0}{2l_0-i},& i\text{ is odd}\\\binom{2l_0}{2l_0-i}-1, &i \text{ is even}\end{cases},i=1,\dots,l_0\right\};b\ge \binom{2l_0}{l_0}\right)$$

...is a solution to the Diophantine system for every $$d=2l_0-1,l_0\in\mathbb N$$ and $$b\ge \binom{2l_0}{l_0}$$. Since $$d=1$$ is not considered in the problem statement: let $$l_0\gt 1$$.

That is, substituting the above $$x$$ into the Diophantine system, will result in $$"b-2=b-2","0=0"$$ for "LHS=RHS" equations, for odd,even $$i$$ respectively,for all $$d=2l+1,l=l_0+1$$, for corresponding $$o_i$$ parameters.

For example, for $$l=1,2,3,4,\dots$$ we have $$(o_i,i=1,\dots,2l)$$ equal to: $$(2,1),(4,6,6,2),(6,15,24,21,12,3),(8,28,62,85,80,49,20,4),\dots$$ These are easy to determine since we know expected "LHS==RHS" for this family. That is, a closed form is possible for these $$o_i$$, but it is irrelevant since we know all $$a_i,i=1,\dots,l+1$$ and $$b$$ explicitly, for this family.

Question $$1$$. How can we generalize this $$x=(a_1,\dots,a_{l+1};b)$$, to find similar families, to encompass more solutions across more different $$o_i$$ sets of parameters, for every $$d$$?

My progress on solving for all solutions for a fixed $$d$$

I've also made computational progress, in cases of first few fixed values of $$d$$.

I have solved it computationally for smallest case, $$d=3$$, finding all solutions $$(a_1,a_2;b)$$.

For the next case, $$d=5$$, I needed to make some workarounds. That is, solve the system under fixed $$o_i$$ parameters. I individually look at sets of $$o_i$$ parameters under which the system has solutions, after eliminating sets of $$o_i$$ parameters under which the system can't have solutions, computationally, to be able to now solve for all $$(a_1,a_2,a_3;b)$$ computationally. Like this, I also managed to solve the $$d=5$$ case, for all soltuions.

But for $$d\ge 7$$, even when trying to solve under individual fixed $$o_i$$ parameters, some sets of such parameters can't be solved (with my implementation). I have some families of solutions for $$d=7$$, but I have not solved this case completely (for all families of solutions), using my computational implementation.

For $$d\ge 9$$, my implementation can't solve for entire families. I can only computationally solve for individual solutions, under fixed $$(d,b)$$ parameters. - This gets on average, exponentially solver in regards to increasing $$d$$ needed to be solved.

Even If I could solve for them, there does not seem to be a "nice closed form" to represent the solutions, when working with fixed cases of $$d$$.

Question $$2$$. Is it possible to make further progress on this problem?

More details about my progress on solving fixed $$d$$

I tried using a Computer-Algebra-System, namely Mathemtica, to try to solve this for small $$d$$.

First case, $$d=3$$, can be solved using Reduce[], after implementing the system in Mathematica.

$$(d=3)$$ That is, we have the equalities $$1,\dots,l$$ (that is, one equality in this case): $$a_1+o_1=2 a_1+a_2-o_2(b-1)$$ With conditions on LHS,RHS for $$i=1,\dots,l+1$$ as: $$a_1+o_1\in[1,b-1)\\ 2 a_1+a_2-o_2(b-1)\in[1,b-1)\\ 2 a_1+a_2-o_2(b-1)\in[0,b-1)\\$$ Where the problem conditions are $$o_1,o_2\ge 0,a_1\in[1,b),a_2\in[0,b),b\gt 2$$.

$$(d=3)$$ solutions are possible only if $$(o_1,o_2)\in\{(1,1),(2,1)\}$$. Each gives one family:

$$\begin{array}{} (o_1,o_2) & a_1 & a_2 & b \\ (1,1) & x+1 & y+4 & a_1+a_2 \\ (2,1) & x+2 & 5 & a_1+4 \end{array}$$

Where $$x,y\in\mathbb N=\{0,1,2,\dots\}$$. Here is the Mathematica code.

But for $$d\ge 5$$, the Reduce[] halts - keeps running forever, and can't solve it for all $$((a_i);b)$$.

For $$d=5$$, it is still possible to extract and solve all fixed $$o_i$$ parameter sets with solutions, if handled individually (after eliminating family of sets that do not have solutions).

$$(d=5)$$ That is, we have the equalities $$1,\dots,l=2$$, in this case: \begin{align} a_1 + o_1 &= 2 a_1 + 2 a_2 + a_3 - o_4 (b-1) \\ 4 a_1 + a_2 - o_1 (b-1) + o_2 &= 4 a_1 + 4 a_2 + 2 a_3 - o_3(b-1)+o_4 \end{align} With conditions on LHS,RHS for $$i=1,\dots,l+1$$ as: \begin{align} a_1 + o_1&\in[1,b-1)\\ 2 a_1 + 2 a_2 + a_3 - o_4(b-1)&\in[1,b-1)\\ 4 a_1 + a_2 - o_1(b-1) + o_2&\in[0,b-1)\\ 4 a_1 + 4 a_2 + 2 a_3 - o_3(b-1) + o_4&\in[0,b-1)\\ 6 a_1 + 3 a_2 + a_3 - o_2(b-1) + o_3&\in[0,b-1) \end{align} Where the problem conditions are $$o_1,o_2,o_3,o_4\ge 0,a_1\in[1,b),a_2,a_3\in[0,b),b\gt 2$$.

I have solved this case computationally to obtain all the solutions:

$$(d=5)$$ There are $$12$$ sets $$(o_1,o_2,o_3,o_4)$$ under which solutions can be obtained:

$$\begin{array}{} (o_1,o_2,o_3,o_4) & a_1 & a_2 & a_3 & b \\ (2,4,3,1) & 2 & \in\{2,3\} & a_1-a_2+1 & 2a_1+a_2 \\ (2,4,3,1) & \in\{3,4\}& \in\{1,2\} & a_1-a_2+1 & 2a_1+a_2 \\ (2,4,3,1) &\in[4,8]&0 & a_1-a_2+1 & 2a_1+a_2 \\ (2,4,3,1) &\in\{5,6\} & 1 & a_1-a_2+1 & 2a_1+a_2 \\ (2,5,5,2) &2 &\in\{3,4\} &3a_1 & 2a_1+a_2 \\ (2,5,5,2) &1 &4 &3a_1 & 2a_1+a_2 \\ (2,4,5,2) &\in\{1,7\} &\in\{7,8\} &3a_1-2 & 2a_1+a_2-1 \\ (2,4,5,2) &\in\{2,3,6\} &\in\{6,7,8\} &3a_1-2 & 2a_1+a_2-1 \\ (2,4,5,2) &\in\{4,5\} &\in[5,8] &3a_1-2 & 2a_1+a_2-1 \\ (2,4,5,2) &8 &8 &3a_1-2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+4 &4 &a_1-a_2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+5 &5 &a_1-a_2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+6 &\in\{3,6\} &a_1-a_2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+7 &7 &a_1-a_2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+8 &2 &a_1-a_2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+10 &1 &a_1-a_2 & 2a_1+a_2-1 \\ (2,3,3,1) &x+12 &0 &a_1-a_2 & 2a_1+a_2-1 \\ (4,8,8,3) &8 &13 &9 &14 \\ (4,8,8,3) &9 &13 &11 &15 \\ (4,8,8,3) &10 &13 &13 &16 \\ (4,8,8,3) &11 &13 &15 &17 \\ (4,8,8,3) &12 &13 &17 &18 \\ (4,6,6,2) &2x+14 &14 &a_1-14 & 2x+20 \\ (4,6,6,2) &2x+15 &14 &a_1-14 & 2x+21 \\ (1,3,4,2) &x+1 &x+y+9 &3a_1-1 &2a_1+a_2 \\ (1,3,2,1) &x+y+3 &y+4 &a_1-a_2+1 &2a_1+a_2+1 \\ (1,4,4,2) &x+1 &x+\{5,6\} &3a_1+1 &2a_1+a_2+1 \\ (1,4,4,2) &x+\{2,3,4\} &x+5 &3a_1+1 &2a_1+a_2+1 \\ (3,6,5,2) &2x+2y+12 &2x+12 &a_1-a_2+1 &3x+2y+18 \\ (3,6,5,2) &2x+2y+11 &2x+12 &a_1-a_2+1 &3x+2x+17 \\ (3,6,7,3) &2x+2y+20 &4x+2y+37 &2x+3y+20 &4x+3y+38 \\ (3,6,7,3) &2x+2y+21 &4x+2y+39 &2x+3y+21 &4x+3y+40 \\ (3,7,7,3) &2 (4+x) &2 (x+\{6,7\}) &4 (4+x) - (x+\{6,7\}) &2 (4+x) + (x+\{6,7\}) \\ (3,7,7,3) &2 (5+x) &2 (x+\{6,9\}) &4 (5+x) - (x+\{6,9\}) &2 (5+x) + (x+\{6,9\}) \\ (3,7,7,3) &2 (6+x) &2 (x+11) &4 (6+x) - (x+11) &2 (6+x) + (x+11) \\ (3,7,7,3) &2 (7+x) &2 (x+13) &4 (7+x) - (x+13) &2 (7+x) + (x+13) \\ (3,7,7,3) &2 (8+x) &2 (x+15) &4 (8+x) - (x+15) &2 (8+x) + (x+15) \\ (3,7,7,3) &2 (x+[3,5]) + 1 &2 (x+6) &4 (x+[3,5]) - (x+6) +2 &2 (x+[3,5]) + (x+6) +1 \\ (3,7,7,3) &2 (x+4) + 1 &2 (x+8) &4 (x+4) - (x+8) +2 &2 (x+4)+ (x+8) +1 \\ (3,7,7,3) &2 (x+5) + 1 &2 (x+10) &4 (x+5) - (x+10) +2 &2 (x+5) + (x+10) +1 \\ (3,7,7,3) &2 (x+6) + 1 &2 (x+12) &4 (x+6) - (x+12) +2 &2 (x+6) + (x+12) +1 \\ (3,7,7,3) &2 (x+7) + 1 &2 (x+14) &4 (x+7) - (x+14) +2 &2 (x+7) + (x+14) +1 \\ \end{array}$$

Where $$x,y\in\mathbb N=\{0,1,2,\dots\}$$. Here is the raw solution output.

$$(d=7) \text{ Partial solution.}$$ We can similarly obtain some solution families for some $$o_i$$ parameters for the $$d=7$$ case, but my implementation couldn't solve it in general. This can be seen by the end of the following answer - which also has $$d=5$$ written out in a different format of expressions, separating finite and infinite families.

$$(d\ge 9) \text{ Unsolved.}$$ I couldn't solve for entire families of solutions with my implementation, for $$d\ge 9$$ cases of the Diophantine system. Solutions for fixed $$(d,b)$$ cases can be obtained using the Mathematica code from the end of the following answer that solves a similar system in the context of double and triple palindromes.

I also forgot to mention, that it is sufficient to observe $$o_i\in\mathbb N=\{0,1,2,\dots\}$$ instead in $$\mathbb Z$$, to obtain all solutions for some $$d$$. (Look at the equalities when $$o_i\le 0$$.)

• Btw, some rows in your table can be combined -- for example, the two rows labeled $(4,6,6,2)$ can be described by a single row: $$\begin{array}{} x+14 &14 &a_1-14 & x+20 \end{array}$$ That is, $2x$ and $2x+1$ in these rows are replaced by just $x$. – Max Alekseyev Oct 3 at 2:31

The given equation is rather cryptic (e.g., $$o_i$$ are not clearly defined) and thus I will rather address the original problem of finding two palindromes of $$d=2l+1$$ digits each in bases $$b\geq 2$$ and $$b-1$$. This corresponds to solving the equation: $$\sum_{i=0}^{l-1} a_i (b^i + b^{2l-i}) + a_l b^l = \sum_{i=0}^{l-1} c_i ((b-1)^i + (b-1)^{2l-i}) + c_l (b-1)^l$$ in integers $$a_0\in[1,b-1]$$, $$c_0\in[1,b-2]$$, $$a_i\in [0,b-1]$$ and $$c_i\in[0,b-2]$$ for $$i\in\{1,2,\dots,l\}$$.

I will show how to solve this equation in a finite number of steps (in particular, finding all finite and infinite series of solutions). For the sake of exposition, let us consider a particular value of $$d=5$$ ($$l=2$$).

Step 1. We represent the equation in the form $$P=0$$, where $$P$$ is a polynomial in $$b$$ with coefficients being linear functions in $$a_i,c_i$$: $$P := (a_0 - 2c_0 + 2c_1 - c_2) + (a_1 + 4c_0 - 4c_1 + 2c_2)b + (a_2 - 6c_0 + 3c_1 - c_2)b^2 + (a_1 + 4c_0 - c_1)b^3 + (a_0 - c_0)b^4.$$

Step 2. We linearize the equation $$P=0$$ as follows. First, from the bounds for $$a_i,c_i$$ we obtain bounds for the free term of $$P$$ (i.e., the coefficient of $$b^0$$): $$a_0 - 2c_0 + 2c_1 - c_2 \in [1,b-1] - 2[b-2,1] + 2[0,b-2] - [b-2,0] = [-3b+7,3b-7].$$ Then we notice that $$P=0$$ implies that the free term of $$P$$ is divisible by $$b$$, that is $$a_0 - 2c_0 + 2c_1 - c_2 = k_0 b$$ for some integer $$k_0$$. From the bounds above we have $$-3 + \tfrac{7}{b} \leq k_0 \leq 3-\tfrac{7}{b}$$, implying that $$k_0\in [-2,2]$$.

Next, we replace the free term in $$P$$ with $$k_0 b$$ and divide the equation $$P=0$$ by $$b$$, obtaining $$k_0 + a_1 + 4c_0 - 4c_1 + 2c_2 + (a_2 - 6c_0 + 3c_1 - c_2)b + (a_1 + 4c_0 - c_1)b^2 + (a_0 - c_0)b^3=0.$$ Here we again consider the free term that must be divisible by $$b$$ and replace it with $$k_1b$$, and so on.

This results in the system of equations: $$\begin{cases} a_0 - 2c_0 + 2c_1 - c_2 = k_0 b, \\ k_0 + a_1 + 4c_0 - 4c_1 + 2c_2 = k_1b,\\ k_1 + a_2 - 6c_0 + 3c_1 - c_2 = k_2 b,\\ k_2 + a_1 + 4c_0 - c_1 = k_3b,\\ k_3 + a_0 - c_0 = 0, \end{cases}$$ where $$k_0\in [-2,2]$$, $$k_1\in [-3, 6]$$, $$k_2\in [-6, 3]$$, $$k_3\in [-1, 4]$$.

Step 3. We iterate the $$k_i$$ over their ranges to obtains a finite number of systems of linear equations over variables $$a_i$$, $$c_i$$, and $$b$$. Together with the bounding conditions for $$a_i$$ and $$c_i$$, each such system defines a polyhedron (possibly unbounded), whose integer points can be found with existing algorithms.

For example, this can be done in SageMath with integral_points_generators() function, which uses the PyNormaliz backend.

I implemented this the described algorithm in SageMath, and confirm that the solutions for $$d=5$$ listed in the table are complete modulo the following typos:

• In the rows labeled $$(1,4,4,2)$$, the base should be $$2a_1+a_2+1$$ rather than $$a_1+a_2+1$$;
• In the last five rows, the value of $$a_2$$ should be decreased by $$1$$ (e.g., $$2(x+6)$$ instead of $$2(x+6)+1$$).

This way we can get all solutions for $$d=7$$ and possibly larger $$d$$'s, but Step 3 needs to be optimized to avoid choices of $$k_i$$'s that are not feasible.

UPDATE. I've processed the case of $$d=7$$ and found all 2- and 3-palindromes. Unfortunately, there are no 4-palindromes. Here is the complete list of 19 3-palindromes:

11, [1, 9, 9, 5]
15, [1, 11, 4, 12]
17, [1, 13, 10, 2]
24, [2, 18, 19, 17]
28, [3, 19, 8, 25]
30, [3, 21, 29, 14]
30, [15, 16, 2, 11]
38, [15, 31, 0, 37]
42, [17, 33, 3, 37]
44, [30, 42, 16, 31]
45, [31, 42, 28, 10]
50, [35, 45, 24, 28]
6k + 58, [k + 8, 3k + 33, k, 3k + 41]
2k + 76, [k + 34, k + 50, k + 10, k + 74]
6k + 175, [4k + 112, 15, k, 36]
6k + 280, [5k + 227, 3k + 160, 5k + 187, 3k + 200]
12k + 39, [2k + 5, 6k + 23, 5k + 6, 14]
12k + 119, [10k + 93, 6k + 78, 7k + 30, 50]
12k + 291, [2k + 47, 6k + 150, 11k + 249, 26]

• This looks very nice, I'll take a closer look and try to play with this once I find time. The $k_i$'s remind me of $o_i$'s, but $k_i$'s being more useful to work with now. (Mentioned $d=5$ typos in OP are corrected as of this comment, thank you for noticing.) – Vepir Oct 3 at 16:39
• @Vepir: I've updated my answer with the $d=7$ results. – Max Alekseyev Oct 3 at 20:06
• I see you also extracted the $3$-palindromes from $d=7$ as well. That part of your answer then confirms (computationally proves) all the proposed solutions for $d=7$ 3-palindromes: last part of claim $(3^*)$ from $3$-palindrome system. (where we only consider "equally long" 3-palindromes, since it is not known if any of the finite 2-palindromes extend to a "not-equally-long" 3-palindrome or not.) – Vepir Oct 3 at 20:35
• You say at the start $b,b+1$ but in the post you work with $b,b-1$? (Typo?) – Vepir Oct 28 at 21:15
• @Vepir: Yes, fixed now. Thanks! – Max Alekseyev Oct 28 at 23:28