Hard system in integers related to natural number representations

Update: Observing a necessary condition, and "unbalanced" variation

A necessary (but not sufficient) condition for a number to be a solution to this Diophantine system (Representing "balanced" triple palindromes) presented in the "The problem-system" section of this question, is for it to be a solution of the following linked Diophantine System (Representing "balanced" double palindromes).

Number is a triple (double) palindrome if it is palindromic in three (two) consecutive number bases.

Double and triple palindromes are "balanced", if they have the same number of digits in all of their consecutive palindromic bases. Otherwise, they are unbalanced.

Unbalanced variation of this problem is not known if it has solutions or not, at all; Does there exits an "unbalanced" triple palindrome?

• I suspect that there are finitely many "unbalanced" double palindromes for every fixed case of digits? - where it is also not known if an unbalanced triple palindrome exists. This conjecture was motivated by the fact that the opposite is true for "balanced" double palindromes: It is known that there exists infinitely many "balanced" double palindromes for every fixed case of digits.

Update on $d\ge 5$ cases

The case $d=5$ is now proven computationally. But the case is still referenced as conjectured in the text below. - A human solution would still be very useful if possible. (Can we bypass the 2-palindrome step and solve directly for 3-palindromes?)

The solutions for 2-palindromes from this answer's $d=5$ case are extendable computationally to base $b-2$ and yield the conjectured $d=5$ solutions presented here.

I'm not sure if it is possible to do the similar thing with $d\ge 7$. - The obstacle being the limitations of using a CAS to solve the given system of equations.

Table of contents

This post will be a bit longer than usual, so here is a table of contents:

• Problem and progress: Stating the problem and presenting known solutions so far.

• Questions on possible ways to continue making progress?

• Context of the problem and some basic stated theory used to prove $d=3$ solutions.

• Going over the proof of $d=3$, can we extend it to conjectured $d=5,7,\dots$ solutions?

• Related problems and the generalized system-problem, motivation

In short, progress in this helps solve problems related to special numbers that depend on representations in multiple number bases, especially ones that deal with the digits of the number.

Such as the two linked questions on existence of a $4$-palindrome and finding $3$-palindromes.

Problem and progress

The problem-system

Let $a_i,A_i,B_i,o_i,h_i,b,d\in\mathbb N_0,i\in\{1,\dots,d\}$ be non-negative integers. Can we solve:

$$ 0 \le a_i\lt b,a_1\ne0 \\ 0 \le A_i=A_{d-i+1}\lt b-1,A_1\ne 0\\ 0 \le B_i=B_{d-i+1}\lt b-2,B_1\ne 0 $$

If it is given $d\gt 1$, and:

$$ a_{j}=a_{d-j+1},j\in\{1\dots d\} \\ A_i=\sum_{k=1}^{i}\binom{d-k}{i-k}a_k + o_{i} - o_{i-1} (b-1) \\ B_i=\sum_{k=1}^{i}\binom{d-k}{i-k}2^{i-k}a_k + h_{i} - h_{i-1} (b-2) $$

For all $(a_1,\dots,a_d;b),o_i,h_i$ that satisfy these conditions?

Where also note that $o_i,h_i=0$ for $i=0,d$.

These equations in short, arise from:

$$ \sum_{k=1}^d a_kb^{d-k}=\sum_{k=1}^d A_k(b-1)^{d-k}=\sum_{k=1}^d B_k(b-2)^{d-k} $$

By writing $A_k,B_k$ in terms of $a_k$, and using $o_i,h_i$ to regularize the equations - which is explained in the context of the problem part of this post.

When the equations are regularized by $o_i,h_i$, the $a_k,A_k,B_k$ can be viewed as digits of a number in bases $b,b-1,b-2$ that are required to be palindromic by the problem-system.

Progress so far

$(0)\space$ If solution exists: $(a_1,\dots,a_d;b)$ for some $d$, then $o_i,h_i$ that allow it are unique.

$(1)\space$ If $d$ is even, the system has no solutions.

$(2)\space$ If $d=3$, I have all the solutions.

$(3^*)\space$ For $d=5,7$, I conjecture I have all the solutions.

$(4^*)\space$ For $d\ge 9$, I suspect there are no solutions, or at most finitely many solutions. I do not have yet any examples (counterexamples) for this.

$(\infty)\space$ Mathematica can solve any $d$ case for $(a_1,\dots,a_d)$, but for one fixed $b$ at a time.

Observation: If there are families of infinitely many solutions, they will appear periodically among consecutive values of $b$. Otherwise, only a finite number of solutions could exist, for small enough values of $b$.

This observation can be used to computationally solve individual $d$ cases - but I have no ways of proving there aren't any more solutions, because I do not know how to set up any upper bounds, even thought they should clearly exist in the context of periods and the smallest base after which all periods should be visible.

Known infinite families of solutions

For $d=3,5,7$, I strongly conjecture I have all such solutions. For $d=3$ only, I managed to actually prove it by exhausting all $o_i,h_i$ cases (by going over all regularized expressions) systematically (which is explained by the end of this post).

For convenience, lets write the the solutions in terms of the smallest one $+$ increment for $a_i$ terms, and $b$ in terms of a constant $+$ period of the solutions in the family. Also, since $a_i=a_{d-i+1}$, we can write solutions by writing only the first $\frac{d+1}{2}$ values of $a_i$. Then:

We have for $k\in\mathbb N_0$ the families with infinitely many solutions:

$$ (a_1+c_1k,\dots,a_{(d+1)/2}+c_{(d+1)/2}k)=(a_i)+(c_i)k $$

$$ \begin{array}{l,l,l,l} d & (a_i)&(c_i)k & b\\ d=3 & (2,6)&(1,1)k & 2k+8\\ d=5 & (31,32,0)&(3,2,1)k & 4k+47 \\ d=7 & (34,50,10,74)&(1,1,1,1)k & 2k+76 \\ d=7 & (8,33,0,41)&(1,3,1,3)k & 6k+58 \\ d=7 & (112,15,0,36)&(4,0,1,0)k & 6k+175 \\ d=7 & (227,160,187,200)&(5,3,5,3)k & 6k+280 \\ d=7 & (5,23,6,14)&(2,6,5,0)k & 12k+39 \\ d=7 & (93,78,30,50)&(10,6,7,0)k & 12k+119 \\ d=7 & (47,150,249,26)&(2,6,11,0)k & 12k+291 \\ \end{array} $$

Notice solutions for $d=3,5,7$ have (largest) periods $p=2,4,12$.

For $d=9,11$, if infinite solution families exist, period is greater than $500,300$ respectively. (Checked bases $b$ from $10^9$ to $10^9+p$), which seems unlikely - That is, it seems unlikely that these cases have solutions at all- And this would be an unexpected result for me.

Known finite sets of solutions

We have for $d=3$ the $(3,6;9)$ solution, for $d=5$ none, for $d=7$ we have $12$ solutions among $b$ from $11$ to $51$. For $d=9,11$ there also seem to be none so far.

Question - Possible ways to make progress?

Fully solve the system?

$Q_1:$ Is it possible to solve this problem-system for general expressions in terms of $b$?

I can do it for one fixed $b$ at a time like mentioned in $(\infty)$ claim, then find general expressions in terms of $b$ by observing consecutive $b$ values. For example, like I did for $d=3,5,7$.

But I have no ways of proving there aren't any more solutions I have missed.

If it is not possible to directly find (prove all) solutions in terms of $b$ for given $d$, an alternate way that could attack this problem, partially instead:

Start partially solving cases of $d$?

$Q_2:$ Can we give an upper bound on the period $p$ for solutions of the infinite families, and an upper bound for the value $b$ after which no new families can exist?

For example, for $d=3,5,7$, these periods are exactly $p=2,4,12$, and such $b$ are exactly $b_p=8,47,291$. (True for $d=3$, conjectured for $d=5,7$).

If we can find such upper bounds, the lower bounds can be increased computationally using $(\infty)$ claim, until reacing or surprassing the upper bounds, and thus we can start proving all solutions for one case of $d$ at a time.

Computationally solve (prove) cases of $d$?

$Q_3:$ Is it possible to generalize the approach used to prove $d=3$, and make a CAS use it to prove individual cases of $d$ systematically?

But I'm having trouble figuring out how to systematically go over all regularized expressions for given $d$ in an effective and usable way. - Which $o_i,h_i$ combinations make sense to verify for solutions and which ones can we disprove (prove yield no solutions)?

Context of the problem and theory for proving $d=3$ case

The context of the system

The context in which this problem-system arises is, the problem of finding all $3$-palindromes. - Numbers palindromic in three consecutive number bases. We are also requiring them to have $d$ digits in those number bases.

Lets define a number representation in base $b$, but also allow the irregular representations - that the digit are $\in\mathbb Z$ or $\ge b$.

Every number $n\in\mathbb N$ has infinitely many irregular expressions in base $b$, and one unique expression - the standard regular representation in a number base.

$$n=\overline{a'_1a'_2\dots a'_{d'}}=(a_1,\dots,a_d)_{b}=\sum_{k=1}^{d}a_kb^{d-k}$$

For example: $100=(1,0,0)_{10}=(1,2,1)_{9}=(2,-7,1)_{9}=(11,1)_{9}=\dots$ Where the first two expressions are regular, and the other two are irregular.

From here, we can get the inequalities by definition for some $n\in\mathbb N$:

$$n=(a_i)_b=\sum_{k=1}^{d}a_kb^{d-k}=\sum_{k=1}^{d}a_k((b-1)+1)^{d-k}=\sum_{k=1}^{d}A_k(b-1)^{d-k}=(A_i)_{b-1}$$

Where you expand $a_k((b-1)+1)^{d-k}$ by binomial theorem to get the expressions for $A_i$, which are given at the beginning if you ignore the $o_i$ parameters.

In this case, the representation given by $A_i$ is irregular, unless $A_i<b-1$ for all $i$, but in that case, we cannot have a palindrome in $b-1$ (observe the formula for $A_i$ without $o_i$ parameters).

This means we are working with irregular expression for $A_i$ if we want to find solutions.

Regularizing the representations

This is where $o_i$ parameters come into place. To actually check for the digits $A_i$ to make a palindrome in base $b-1$, they need to be a part of the regular expression.

This means we need to regularize these $A_i$ expressions so they make up a regular representation in number base $b-1$. Only then we can actually verify whether $n$ can be palindromic in $b-1$.

By definition, you can borrow "from" or "to" neighbouring digits, without changing the value of $n$, like so:

$$ n=(\dots,a_t,a_{t+1},\dots)_b=(\dots,a_t+o_{t},a_{t+1}-o_{t}b,\dots)_b $$

For $o_i\in\mathbb Z$. But since we have observed that $A_i\lt b-1$ does not work assuming $(A_i)_b$ is regular for all $o_i=0$, and since $A_i\gt 0$, we need to reduce the $A_i$ digits to get to a regular representation. Thus, we can work with $o_i\in\mathbb N_0$.

Similar story with $B_i$ and base $b-2$, and "borrowings" to regularize the expression with $h_i$.

If we were working with $b,b+1,b+2$ instead of $b,b-1,b-2$, then $o_i,h_i$ could also be negative, which gives a harder system to analyse.

Claims $(0)$ and $(1)$

From the uniqueness of the regular expression and definition of $o_i,h_i$, the $(0)$ follows easily.

The $(1)$ is true (for the presented system at the beginning), since it can be shown that if a number is palindromic in number base $b$ and has an even number of digits, then it is divisible by $b+1$. This means if we have a palindrome with $d=2l$ digits in base $b-1$, then it cannot be palindromic in base $b$, because of divisibility it should end with $0$, and we have that $a_1,A_1\ne0$.

Solving the system for $d=3$ - proving $(2)$ claim.

Here, the system presented at the beginning is based on bases $b,b-1,b-2$ and works in terms of $o_i,h_i$. By using the definition of irregular expressions, we can avoid writing down $o_i,h_i$ and the system explicitly.

We will first find all $2$-palindromes then extend to $3$-palidnromes. We will do this, by finding all possible regularized expressions for base $b-1$ by going over $o_i$ parameters. Then we will go over $h_i$ just for the now found $2$-palindromes, to again find and check all regular expressions for being a palindrome.

We have that:

$$n=(a_1,a_2,a_1)_b=(A_1,A_2,A_3)_{b-1}=(a_1,2a_1 + a_2,2a_1+ a_2)_{b-1}$$

We will observe two cases:

$1.)\space a_1 \le a_2$, That is, we can parameterize: $a_2 = a_1 + r_1,r_1\in\mathbb N_0$.

Now we can also parameterize the number base:

$$b=\max\{a_1,a_2\}+t=a_2+t=a_1+r_1+t,t\in\mathbb N$$

Like this, since $a_1,a_2$ need to be $<b$, since $(a_1,a_2,a_1)_b$ is a regular expression.

Now we have:

$$ (A_i)_{b-1}=(a_1,3a_1 + r_1,3a_1+ r_1)_{a_1+r_1+t-1} $$

If we assume $b-1\gt 3a_1+r_1$, then we have a regular expression, but it can't be a palindrome since $A_1=a_1\lt A_3=3a_1+r_1 \implies A_1\ne A_3$.

Thus, $b-1\le 3a_1+r_1$. Now we have an irregular expression. Lets regularize it:

$$ (a_1,3a_1 + r_1,3a_1+ r_1)_{b-1} \\ =(a_1+1,3a_1 + r_1-(b-1)+1,3a_1+ r_1-(b-1))_{b-1} \\ =(1+a_1,2-t+2 a_1,1-t+2 a_1)_{a_1+r_1+t-1} \\ $$ By applying the first case of $o_i$ parameters - By using the "borrowings" to satisfy regularization under $b-1\le 3a_1+r_1$ condition.

Now this is either regularized or not. If you assume not, and continue going for other cases of $o_i$ and regularizing in all other possible ways, you'll every time reach a case with no solutions for $A_1=A_3$.

Thus lets assume this is now regularized.

Thus we need to solve:

$$ A_1=A_3\iff 1+a_1=1-t+2 a_1\iff t=a_1 $$

If you also look at the conditions under which this is regularized, you'll get:

$$ (c_1):\space (1 \le a_1 \le 3 \land r_1 \ge 4 - a_1) \lor (a_1 \ge 4 \land r_1 \ge 0) $$

We have now solved case $1.)$ for $2$-palindromes. That is, we have solutions:

$$ (a_1,a_2;b)=(a_1,a_1+r_1;2a_1+r_1),a_1,r_1\in\mathbb N\land(c_1) $$

Or in the context of $2$-palindromes:

$$ (a_1,a_1+r_1,a_1)_{2a_1+r_1}=(1+a_1,2+a_1,1+a_1)_{2a_1+r_1-1} $$

Now we need to check the expression in base $b-2$ and go over all regular expressions by going over $h_i$ combinations. After now checking these for $B_i$ conditions for base $b-2$, you can show that the final solution to the $d=3$ for case $1.)$ is:

$$ (a_1,a_2;b)=(a-2,a+2;2a),a\ge 4 \lor (a_1,a_2;b)=(3,6;9) $$

Or in $3$-palindrome context (the first part, the second part is just number $n=300$ in bases $9,8,7$):

$$ (a-2,a+2,a-2)_{2a}=(a-1,a,a-1)_{2a-1}=(a,a+1,a)_{2a-2},a\ge 4 $$

Now, in a similar way, you can handle the $2.)\space a_1\gt a_2$ case, and find all $2$-palindromes in bases $b,b-1$. But when checking for $B_i$ as well, for base $b-2$, there will be no final solutions for $3$-palindromes.

That is, for $2.)\space a_1\gt a_2$, we can show there aren't any solutions after doing a similar process for $A_i$ and then finally considering $B_i$ conditions as well.

Thus, we can show the final solution for $d=3$ is:

$$ (a_1,a_2;b)=(a-2,a+2;2a),a\ge 4 \lor (a_1,a_2;b)=(3,6;9) $$

Which agrees with solutions given in $(2)$ claim.

Generalizing the proof for $(2)$ claim?

Is it possible to implement this process in a CAS? To solve for any given $d$ in general?

I've tried in Mathematica, but I'm not sure how to properly go over all regular expression.

My idea was to go over all $\frac{d+1}{2}!$ cases of permuting $a_i$ in $a_1\le a_2\le \dots\le a_{(d+1)/2}$.

Now we can parameterize the base $b=\max\{a_i\}+t,t\in\mathbb N$, and every digit in terms of $r_i\in\mathbb N_0$ and $\min\{a_i\}$. Then, what is left, is to go over all regular expressions in each of these cases, and then solve just the system of equalities $A_i=A_{d-i+1}$ now. This will give all $2$-palindromes.

What is left then, is to apply the same process but now only for these $2$-palindromes, and in base $b-2$. We will be again solving just a system of equalities $B_i=B_{d-i+1}$ in every case, for every regular expression in that case.

But I had trouble going over all regular expressions and of keeping track of $o_i,h_i$ that make sense to consider (Not all need to be considered, depending on the sizes and conditions so far on $b,A_i,B_i$), and also getting duplicate solutions for $2$-palindromes in supposedly different regularized expressions. And on top of that, it was running extremely slowly to find the next set of $2$-palindrome solutions for $d\gt 3$.

So I'm not sure how to implement this process properly, or if it can actually work for a general case of $d$ in current CAS that are avaliable?

Generalized system and related problems

This system of inequalities and palindromic equalities, is related to the a bit more general similar system - where there can be more $A_i,B_i$ expressions instead of exactly $d$ such expressions.

The general problem

The generalized inequalities also allows $A_i,B_i$ for $i\le 0$, where then they are just given as:

$$ A_i=o_{i} - o_{i-1} (b-1) \\ B_i=h_{i} - h_{i-1} (b-2) $$

And if $i_A$ is the smallest such $i$ for which $A_i$ is not zero, and if $i_B$ is the smallest such $i$ for which $B_i$ is not zero, then the system we are solving changes to:

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

Such that the equalities stay palindromic.

And now these along with given $a_i=a_{d-i+1}$, actually represent equations for digits of a number $n\in\mathbb N$ in number bases $b,b-1,b-2$, which are required to be palindromic in all of those three number bases, which is the context this system was found in.

Find all numbers palindromic in three consecutive number bases?

That have $d$ digits in number base $b$. In the general problem, number of digits does not need to be equal in all number bases as implied by $i_A,i_B$ - just in the base $b$, where $b-1,b-2$ could have more digits. If $i_A,i_B=1$, that is, the problem-system in this post is given, then number of digits, is required to be equal in all bases $b,b-1,b-2$ and is exactly $d$.

Related problems

Even thought related problems imply the generalized system, all infinite families of solutions that are known so far, are given by the problem-system, $i_A=i_B=1$.

Also note that in the related problems (of mine), it is considered $b,b+1,b+2$ instead of $b,b-1,b-2$, and it is talked in context of palindromes themselves, as those posts predate this system and the $b,b-1,b-2$ approach. - Which is equivalent to $b,b+1,b+2$ in terms of solutions, but easier to work with in the terms of the problem-system.

The related problems and motivation:

• The motivation behind searching for these so called $3$-palindromes, is to answer the question, whether there exists a $4$-palindrome?

• The solutions from $(2),(3^*)$ were already mentioned in a question that is asking about $3$-palindromes in that context, without setting up a system.

Note that as those questions predate this system and the ability to solve for any fixed $b$ using it in Mathematica - I used to have to run an optimized brute force search in c++ instead, which was exponentially slower and was impossible to be used on bases like $10^9$ which now take similar time as bases $10^2$. - Now the computations are still exponentially related to $d$, but near constant time related to $b$, where they used to be exponentially related to both in a brute force search.

Motivation

Similar systems could be set up for problems that depend on digits of numbers in number bases - or for diophantine equations that can be related to such problems.

Solution 1:

These questions have been addressed here and there. To summarize:

Answer to $Q_1$ and $Q_3$ is Yes as explained in my answer at MO. (3*) is also confirmed there.

As of (4*), I've confirmed that there are no parametric 3-palindromes for $d=9$ and $d=11$. UPDATE: and $d=13$.