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$ – Geoffrey Trang Aug 2 '19 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$ – Vepir Aug 2 '19 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$ – user645636 Aug 2 '19 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$ – Peter Aug 3 '19 at 15:17
  • 1
    $\begingroup$ Earlier question on similar topic by same user, math.stackexchange.com/questions/2320003/… $\endgroup$ – Gerry Myerson Aug 4 '19 at 6:24
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$ – Vepir Aug 4 '19 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$ – Vepir Sep 16 '19 at 16:57
3
$\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$

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.