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

Improve this question
$\endgroup$
1
  • $\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
    Commented Oct 3, 2019 at 2:31

1 Answer 1

Reset to default
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]
Improve this answer
$\endgroup$
5
  • $\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
    Commented Oct 3, 2019 at 16:39
  • $\begingroup$ @Vepir: I've updated my answer with the $d=7$ results. $\endgroup$
    – Max Alekseyev
    Commented Oct 3, 2019 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
    Commented Oct 3, 2019 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
    Commented Oct 28, 2019 at 21:15
  • $\begingroup$ @Vepir: Yes, fixed now. Thanks! $\endgroup$
    – Max Alekseyev
    Commented Oct 28, 2019 at 23:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .