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$
    – Vepir
    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$
    – user645636
    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$
    – Peter
    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

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
    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$
    – Vepir
    Commented Sep 16, 2019 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$

You must log in to answer this question.

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