3
$\begingroup$

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

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$.)

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Max Alekseyev Oct 3 at 2:31
2
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Vepir Oct 3 at 16:39
  • $\begingroup$ @Vepir: I've updated my answer with the $d=7$ results. $\endgroup$ – Max Alekseyev Oct 3 at 20:06
  • $\begingroup$ 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.) $\endgroup$ – Vepir Oct 3 at 20:35
  • $\begingroup$ You say at the start $b,b+1$ but in the post you work with $b,b-1$? (Typo?) $\endgroup$ – Vepir Oct 28 at 21:15
  • $\begingroup$ @Vepir: Yes, fixed now. Thanks! $\endgroup$ – Max Alekseyev Oct 28 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.