6
$\begingroup$

Is it possible to construct an arbitrarily long double palindrome?

The double palindrome of length $d$ is a number that is palindromic (digits are the same when reversed) in two consecutive number bases $b,b-1$ and has $d\gt 1$ digits in both bases.

Notice that $d$ must be odd. (Even length palindrome in base $b$ is divisible by $b+1$.)

For example, smallest such $d$ length numbers $N$ are:

$$ \begin{array}{llcc} d & N_{} & N_{b} & N_{b-1} \\ 3 & 46 & (1,4,1)_{5} & (2,3,2)_{4} \\ 5 & 2293 & (1,4,3,4,1)_{6} & (3,3,1,3,3)_{5} \\ 7 & 186621 & (1,4,0,5,0,4,1)_{7} & (3,5,5,5,5,5,3)_{6} \\ 9 & 27924649 & (1,5,2,4,1,4,2,5,1)_{8} & (4,5,6,2,3,2,6,5,4)_{7} \\ 11 & 1556085529 & (1,3,4,5,7,7,7,5,4,3,1)_{8} & (5,3,3,6,3,3,3,6,3,3,5)_{7} \end{array} $$ $$\dots$$

Where $N_b$ stands for number base $b$ representation.

Can we given an arbitrarily large odd $d$, construct such an example? Not necessarily the smallest.

If a construction is not possible, is it possible to have a non-constructive proof that there exist arbitrarily long double palindromes?


For example, the following number is a $101$ digit example in number bases $2^{100},2^{100}-1$:

11389275493313395146550195654086875480212234145731621333457701374028277774821274121186469926783503107455762545190548953087972746277002615510348197334563422536978325200285661937560186900957074547554068082502727911310565791405547335060724732113707470568348235577529877640830972500982771607908273897049269199948743133357558899129171595526095424548835696539562402541941975719433140321089322105284423292342890390079652603187050742456213860408145368644790770464116307178226032998988586618940424136245540475050784355875240485281433451060276834218332638393932165203008707194035419270702618571029287812579601921523265433357267147433086934194603149533491309767183140404297760654193824635514373780409273513236609066409655814115873504480016695859332597438995349184138935345329311518673306716195561277801893729959512933999081834483612257653972787850300719280392762476925664658660591935865676106504092843771990798455053144572289465926879848660238840554129637408892668275740988654918664500208238523360411429302322660442324629263685837983291790922905852580315488379578697246636865685154943687657307119964645764231792074703354952892843429147247242575341854166673929009183148029013620039509693002826403446352806308897367164001435010830357381781324567492563737682677932852863861449302117723604251282754369199417086956130386086250554018383792623183489254070735814262747649573875288696676020329121486019334796448294947835513725519213775802399385723069980284364403584079235958069722159900775542477497410968609873477392193126119577904849592080300359176684784985446999145681080782991658907467466272812388989103224984773755050903767298522736370550343965032093005283604035369983437697856001052564882998927925440968051579996174058908430531032383844942218086641153322735698868436889023100943941179461929266276884404712751573931271862837013375482622137967438320352207414572102449928768875364674538369782130207252079580652403427585428426714158838407919917520931159084186491247126021978306309428977838057267458089989192059324625334540178453361150563815452415194771214012690963151049023462937470365410174639417165671169169098495761925964997129692757855110276453683825293816469900688366363665542595611001399702424100153513427148085288952406920565962156464879880387606500753374731675143598406532676463603711230745131611375277036528069799694000409179025588622330937540496488329612388805508117233633052694701641815859674630886375060139622035813116201261468713599560495319754132483733034347504990201455520961778597903897765553458703276959297653931532416792717147421965389813274743401205102119712653419157697182257093836975104016020077311232928824644865884492019118992730353783294077677736829217160116897295006506938648589158119139740497859570466355595233637481562651409130811917086309202404772157419706578610699081034940181844175572714735266695085061024313566678939846144178907828403204463270606610637805786784555542060087712196658611683814223815821199303286564960925262963035771707446370895249357305674148296897358852817848939460321115610826530057710705824101184458195717372478

And it is of size $\approx10^{3040}$ (definitely not the smallest $d=101$ example).

$\endgroup$
9
  • 2
    $\begingroup$ We could also allow d to be even provided that we also allow leading zeros. A number would become palindromic after adding some leading zeros if and only if it is obtained from a palindromic number by adding some trailing zeros. $\endgroup$ Commented Aug 2, 2019 at 13:54
  • 1
    $\begingroup$ @GeoffreyTrang That is a possible extension - equivalently, we could require either $n$ or $n/b^k$ to be a palindrome for some $k$ (delete trailing zeros in base $b$). But here I'm working with the classic definition of a palindrome which does not allow leading zeros. $\endgroup$ Commented Aug 2, 2019 at 14:11
  • $\begingroup$ Lets see to be $d$ digits in bases $b,b-1$ it's between $(b-1)^{d-1}$ and $(b-1)^d$ and so is $b^{d-1}$ . Since one of $b,b-1$ is odd, we get that if the number is odd it needs the middle digit odd in that base. $\endgroup$ Commented Aug 2, 2019 at 15:45
  • $\begingroup$ @Vepir Are you actually sure that it cannot be the smallest example ? Not that I expect it to be the smallest, but I ask because you wrote "definitely" $\endgroup$ Commented Aug 3, 2019 at 15:17
  • 1
    $\begingroup$ Earlier question on similar topic by same user, math.stackexchange.com/questions/2320003/… $\endgroup$ Commented Aug 4, 2019 at 6:24

2 Answers 2

Reset to default
4
$\begingroup$

I have not worked out a proof yet , but it seems that $$n:=\frac{b^k-1}{b+1}$$ with even $k\ge 2$ is palindrome in bases $b$ and $b+1$ for sufficient large $b$. For example , $b=10^{99}$ and $k=108$ does the job.

$\endgroup$
2
  • 1
    $\begingroup$ This appears to true! Perhaps it is possible to express such $n$ in terms of digits of base $b+1$ and show it is palindromic for sufficiently large $b$. $\endgroup$ Commented Aug 4, 2019 at 7:21
  • 1
    $\begingroup$ If $k=2n$, then your expression is a palindrome in $b,b+1$ for all (if and only if) $b\ge a(n)$ where $a(n)=\text{A030662}$. We can see that $a(n)$ is also the sum of squared binomial coefficients. I haven't proven this yet. $\endgroup$ Commented Sep 16, 2019 at 16:57
4
$\begingroup$

Thanks to @Peter's answer for conjecturing a pattern that should give such a sequence.

Here, I managed to prove his proposed identity.

The linked answer proposed that the following gives $(b,b+1)$ 2-palindromes for even $k$ and large $b$:

$$ \frac{b^k-1}{b+1} $$

For large $k$, we have arbitrarily large amount of digits in those two number bases.

It is not hard to see that the given expression is palindromic in base $b$.

What is needed to prove, is it being palindromic in $b+1$ for sufficiently large $b$, for infinitely many $k$.

More specifically, what we needed to prove was the following:

For all $n,b\in\mathbb N$, if $b\ge \sum_{k=1}^n \binom{n}{k}^2$, then there exits $A_n(i)$ such that following identity is true:

$$ \frac{b^{2n}-1}{b+1}=\sum_{i=1}^{2n-1}A_n(i)(b+1)^{2n-1-i}\\ A_n(i)=A_n(2n-i),i=1,\dots,2n-1 $$

That is if $k=2n$, the expression is a $d=2n-1$ digit palindrome in base $b+1$ for all $b\ge \sum_{k=1}^n \binom{n}{k}^2$.

Initially, my conjectured pattern for $A_n(i)$ that holds so far was:

$$ A_n(i)=\begin{cases}b-a_n(i), && i\text{ is odd}\\a_n(i), && i\text{ is even}\end{cases} $$

Where $a_n(i)$ is given by: ($n$th row, $i$th element)

$$\newcommand\s[]{\space} 1\\ 3\s\s\s\s\s\s 5\s\s\s\s\s\s 3\\ 5\s\s\s\s\s\s 14\s\s\s\s\s 19\s\s\s\s\s 14\s\s\s\s\s 5\\ 7\s\s\s\s\s\s 27\s\s\s\s\s 55\s\s\s\s\s 69\s\s\s\s\s 55\s\s\s\s\s 27\s\s\s\s\s 7\\ 9\s\s\s\s\s\s 44\s\s\s\s\s 119\s\s\s\s 209\s\s\s\s 251\s\s\s\s 209\s\s\s\s 119\s\s\s\s 44\s\s\s\s\s 9\\ 11\s\s\s\s\s 65\s\s\s\s\s 219\s\s\s\s 494\s\s\s\s 791\s\s\s\s 923\s\s\s\s 791\s\s\s\s 494\s\s\s\s 219\s\s\s\s 65\s\s\s\s\s 11\\ 13\s\s\s\s\s 90\s\s\s\s\s 363\s\s\s\s 1000\s\s\s 2001\s\s\s 3002\s\s\s 3431\s\s\s 3002\s\s\s 2001\s\s\s 1000\s\s\s 363\s\s\s\s 90\s\s\s\s\s 13\\ 15\s\s\s\s\s 119\s\s\s\s 559\s\s\s\s 1819\s\s\s 4367\s\s\s 8007\s\s\s 11439\s\s 12869\s\s 11439\s\s 8007\s\s\s 4367\s\s\s 1819\s\s\s 559\s\s\s 119\s\s\s 15\\ \dots $$

Some patterns are clear, like the middle column being $\sum_{k=1}^n \binom{n}{k}^2$, for example.

After closer examination, we can notice that the diagonal elements are given by:

$$ D(r,q)=\binom{2(r+q-1)}{q}-1 $$

And when solving for $n,i$ we obtain:

$$ a_n(i)=\binom{2n}{2n-i}-1 $$

And this is indeed the correct pattern. Now we simply sum the initial sum and show the identity is true.

We can use Mathematica:

FullSimplify[Sum[(b ((-1)^(i + 1) + 1)/2 + (-1)^i (Binomial[2 n, -i + 2 n] - 1)) (b + 1)^(2 n - 1 - i), {i, 1, 2 n - 1}] - (b^(2 n) - 1)/(b + 1), Element[n, Integers]]

To obtain RHS-LHS=0. We are done!

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.