# Arbitrarily long palindromes in two consecutive number bases

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

• 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. – Geoffrey Trang Aug 2 '19 at 13:54
• @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. – Vepir Aug 2 '19 at 14:11
• 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. – user645636 Aug 2 '19 at 15:45
• @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" – Peter Aug 3 '19 at 15:17
• Earlier question on similar topic by same user, math.stackexchange.com/questions/2320003/… – Gerry Myerson Aug 4 '19 at 6:24

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.

• 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$. – Vepir Aug 4 '19 at 7:21
• 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. – Vepir Sep 16 '19 at 16:57

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!