⇐ Palindrome – Zahlen
Eine Zahl, die bei Umkehrung der Ziffernfolge unverändert bleibt, nennt man «Palindrom». Eine andere Bezeichnung dafür ist einfach «symmetrische Zahl».
Beispiele: $11, 121, 1221, 44544, 92329, 7125217, $ usw.
Ob eine bestimmte Zahl Palindrom ist oder nicht, hängt natürlich vom verwendeten Ziffernsystem ab. In der folgenden Tabelle sind einige Zahlen in verschiedenen Ziffernsystemen aufgelistet. Die Palindrome sind farbig hervorgehoben.
| Basis 10 (Dezimal) | Basis 2 (Binär) | Basis 3 | Basis 5 | Basis 8 (Oktal) | Basis 16 (Hexadezimal) |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 2 | 2 | 2 |
| 3 | 11 | 10 | 3 | 3 | 3 |
| 4 | 100 | 11 | 4 | 4 | 4 |
| 5 | 101 | 12 | 10 | 5 | 5 |
| 6 | 110 | 20 | 11 | 6 | 6 |
| 7 | 111 | 21 | 12 | 7 | 7 |
| 8 | 1000 | 22 | 13 | 10 | 8 |
| 9 | 1001 | 100 | 14 | 11 | 9 |
| 10 | 1010 | 101 | 20 | 12 | A |
| 11 | 1011 | 102 | 21 | 13 | B |
| 12 | 1100 | 110 | 22 | 14 | C |
| 13 | 1101 | 111 | 23 | 15 | D |
| 14 | 1110 | 112 | 24 | 16 | E |
| 15 | 1111 | 120 | 30 | 17 | F |
| 16 | 10000 | 121 | 31 | 20 | 10 |
| 17 | 10001 | 122 | 32 | 21 | 11 |
| 18 | 10010 | 200 | 33 | 22 | 12 |
| 19 | 10011 | 201 | 34 | 23 | 13 |
| 20 | 10100 | 202 | 40 | 24 | 14 |
| 21 | 10101 | 210 | 41 | 25 | 15 |
| 22 | 10110 | 211 | 42 | 26 | 16 |
| 23 | 10111 | 212 | 43 | 27 | 17 |
| 24 | 11000 | 220 | 44 | 30 | 18 |
| 25 | 11001 | 221 | 100 | 31 | 19 |
| 26 | 11010 | 222 | 101 | 32 | 1A |
| 27 | 11011 | 1000 | 102 | 33 | 1B |
| 28 | 11100 | 1001 | 103 | 34 | 1C |
| 29 | 11101 | 1002 | 104 | 35 | 1D |
| 30 | 11110 | 1010 | 110 | 36 | 1E |
| 31 | 11111 | 1011 | 111 | 37 | 1F |
| 32 | 100000 | 1012 | 112 | 40 | 20 |
| 33 | 100001 | 1020 | 113 | 41 | 21 |
| 34 | 100010 | 1021 | 114 | 42 | 22 |
| 55 | 110111 | 2001 | 210 | 67 | 37 |
| 99 | 1100011 | 10200 | 344 | 143 | 63 |
| 100 | 1100100 | 10201 | 400 | 144 | 64 |
| 101 | 1100101 | 10202 | 401 | 145 | 65 |
| 200 | 11001000 | 21102 | 1300 | 310 | C8 |
| 499 | 111110011 | 200111 | 3444 | 763 | 1F3 |
| 500 | 111110100 | 200112 | 4000 | 764 | 1F4 |
| 501 | 111110101 | 200120 | 4001 | 765 | 1F5 |
| 502 | 111110110 | 200121 | 4002 | 766 | 1F6 |
| 503 | 111110111 | 200122 | 4003 | 767 | 1F7 |
| 504 | 111111000 | 200200 | 4004 | 770 | 1F8 |
| 511 | 111111111 | 200221 | 4021 | 777 | 1FF |
| 512 | 1000000000 | 200222 | 4022 | 1000 | 200 |
| 513 | 1000000001 | 201000 | 4023 | 1001 | 201 |
| 514 | 1000000010 | 201001 | 4024 | 1002 | 202 |
| 524 | 1000001100 | 201102 | 4044 | 1014 | 20C |
Im einfachsten Falle betrachtet man die Zahlen im Binärsystem (nur die Ziffern $0$ und $1$). Nichtsdestotrotz schreibt man die Zahlen dezimal, so sind wir es gewohnt. Z.B. ist die Nummer 16 in dieser Folge die Zahl $73=1001001$. Die ersten aufeinanderfolgenden binären Palindrome sind: $0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63,65, 73, 85, 93, 99,$ … (s. The On-Line Encyclopedia of Integer Sequences, Link: http://oeis.org/A006995 [Numbers whose binary expansion is palindromic] für weitere Zahlen).
Man kann das $n$-te binäre Palindrom bestimmen, ohne alle in Frage kommenden Zahlen im Einzelnen betrachten zu müssen. Z.B. ist das 1000ste binäre Palindrom die Zahl $249903=111101000000101111_2$, das 10-milliardste binäre Palindrom ist $24502928886295666773$. Im letzteren Falle hat die entsprechende Binärzahl bereits 65 Stellen. Eine ganz einfache allgemeine Formel für das $n$-te binäre Palindrom – wir bezeichnen es im Folgenden kurz mit $P_2 (n)$ – gibt es nicht, doch kann man in speziellen Fällen das $n$-te binäre Palindrom leicht berechnen, z.B. gilt
\begin{equation} \begin{array}{lcl} P_2 (2^m – 1) &=&2^{2m-2}-1 \\ P_2 (2^m) &=&2^{2m-2}+1 \\ P_2 ( 2^m+1) &=&2^{2m-2}+2^{m-1}+1 \\P_2( 5\cdot 2^{m-2}-1) &=&2^{2m-2}+2^{m-3}-3 \\ P_2 ( 5\cdot 2^{m-2}) &=&2^{2m-2}+2^{m-3}+3 \\ P_2 ( 6\cdot 2^{m-2}-1 ) &=&2^{2m-1}-1 \\ P_2 ( 6\cdot 2^{m-2} ) &=&2^{2m-1}+1 \\ P_2( 6\cdot 2^{m-2}+1 ) &=&2^{2m-1}+2^{m}+2^{m-1}+1 \\P_2 ( 7\cdot 2^{m-2}-1 ) &=&2^{2m-1}+2^{m-2}-3 \\ P_2 ( 7\cdot 2^{m-2} ) &=&2^{2m-1}+2^{m-2}+3 \end {array} \end{equation}
Demnach ist also $ {{2}^{{\left( {20-2} \right)}}}+{{2}^{{\left( {10-1} \right)}}}+1 = 262657 $ das 1025ste binäre Palindrom. Die unmittelbar vorhergehenden 1024sten und 1023sten Palindrome sind $262145$ und $262143$.
Für die allgemeine Bestimmung kann man eine rekursive Berechnungsmethode anwenden: \begin{align} {{P}_{2}}\left( n \right)={{2}^{{2k-q}}}+1+{{2}^{p}}\cdot {{P}_{2}}\left( m \right) \end{align} wobei $ k=\lfloor {\log}_{2}\left( {n-1} \right)\rfloor $ und die Parameter $ p,~q~\text{und}~m$ folgendermaßen bestimmt werden:
| $ n={{2}^{{k+1}}}$ : | $ p=0,~~$ $ q=0,~~$ $ m=1$ |
| $ {{2}^{k}}<n<{{2}^{k}}+{{2}^{{k-1}}}$ : | $ i=n-{{2}^{k}},~~$ $ p=k-\lfloor {\log}_{2}\left( i \right)\rfloor -1$, $ q=2,$ $ m={2}^{\lfloor{{\log}_{2}}{\left( i \right)}\rfloor}+i$ |
| $ n=~{{2}^{k}}+{{2}^{{k-1}}}$ : | $ p=0,~~$ $ q=1,~~$ $ m=1$ |
| $ {{2}^{k}}+{{2}^{{k-1}}}<n<{{2}^{{k+1}}}$ : | $ j=n-{{2}^{k}}-{{2}^{{k-1}}},~~$ $ p=k-\lfloor {\log}_{2}\left( j \right)\rfloor -1$, $ q=1,~~$ $ m=2\cdot {2}^{\lfloor{{\log}_{2}}{\left( j \right)}\rfloor}+j$ |
Eine weitere Möglichkeit zur direkten Bestimmung des $n$-ten binären Palindroms ist diese (für $ n\ge 3)$
\begin{align} \begin{array}{l} P_2\left( n \right)=&\,2^{2m-1-p}+1+p\cdot (1-{{\left( {-1} \right)}^{n}})\cdot {{2}^{m-2}}+\\&\,\sum \limits_{{k=1}}^{m-1-p} \left[ {\left( {\dfrac{{n-\left( {3-p} \right)\cdot {2^{m-1}}}}{2^{m-1-k}}\bmod~2} \right)\cdot \left( {2^k+{2^{2m-1-p-k}}} \right)} \right] \end{array} \end{align}
wobei $ m= \lfloor {\log}_{2}\left( n \right)\rfloor$ und $ p=\lfloor \frac{{3\cdot {{2}^{{m-1}}}-1}}{n}\rfloor$ oder, was das gleiche bedeutet, der Parameter nach folgender Fallunterscheidung eingesetzt wird:
| $ n\ge 3\cdot {{2}^{{m-1}}}$ | $ p=0$ |
| $ n<3\cdot {{2}^{{m-1}}}$ | $ p=1$ |
Hiermit berechnete größere binäre Palindrome sind in der nachfolgenden Tabelle aufgelistet.
| Nr. | Palindrom |
| $1$ | $0$ |
| $2$ | $1$ |
| $3$ | $3$ |
| $4$ | $5$ |
| $5$ | $7$ |
| $6$ | $9$ |
| $7$ | $15$ |
| $8$ | $17$ |
| $9$ | $21$ |
| $10$ | $27$ |
| $10^2$ | $2313$ |
| $10^3$ | $249903$ |
| $10^4$ | $24183069$ |
| $10^5$ | $2258634081$ |
| $10^6$ | $249410097687$ |
| $10^7$ | $24350854001805$ |
| $10^8$ | $2229543293296319$ |
| $10^9$ | $248640535848971067$ |
| $10^{10}$ | $24502928886295666773$ |
Die Differenzen aufeinander folgender Palindrome bilden eine interessante Folge: \[\begin {align*} &1, 2, 2, 2, 2, 6, 2, 4, 6, 4, 2, 12, 6, 12, 2, 8, 12, 8, 6, 8, 12, 8, 2, \\&24, 12, 24, 6, 24, 12, 24, 2, 16, 24, 16, 12, 16, 24, 16, 6, 16, \\&24, 16, 12, 16, 24, 16, 2, 48, \cdots \end {align*}\] (s. The On-Line Encyclopedia of Integer Sequences, Link: http://oeis.org/A164126). Die $2$ und die $6$ treten dabei unendlich oft als Folgenglieder auf. Bezeichnen wir die Glieder mit $ \Delta {{P}_{2}}\left( n \right):={{P}_{2}}\left( {n+1} \right)-{{P}_{2}}\left( n \right)$ so gilt ab $m =0$
\begin{align} \begin{array}{l} \Delta {{P}_{2}}\left( {4\cdot {{2}^{m}}-1} \right)&=2 \\ \Delta {{P}_{2}}\left( {6\cdot {{2}^{m}}-1} \right)&=2\\ \Delta {{P}_{2}}\left( {7\cdot {{2}^{m}}-1} \right)&=6 \end{array} \end{align}
und ab $m=1$
\begin{equation} \Delta {{P}_{2}}\left( {5\cdot {{2}^{m}}-1} \right)=6 \end{equation}
Die allgemeine Formel für $ \Delta {{P}_{2}}\left( n \right)$ lässt sich aus der obigen Formel für $ {{P}_{2}}\left( n \right)$ ableiten. Mit den Definitionen $ m=\lfloor {\log}_{2}\left( n \right) \rfloor $ und $ p=\lfloor \frac{{3\cdot {{2}^{{m-1}}}-1}}{n} \rfloor$ sowie
\begin{equation} \displaystyle d_{{n}{k}} = \left\lfloor {\frac{{n-\left( {3-p} \right)\cdot {2^{m-1}}}}{2^{m-1-k}}} \right\rfloor \bmod 2 \end{equation}
ergibt sich
\begin{equation} \Delta {P_2}(n)={{\left( {-1} \right)}^{m}}\cdot {{2}^{{m-1}}}+\sum\limits_{{k=1}}^{{m-1}}{{\left[ { \left( {d_{{n+1}{k}} – d_{{n}{k}}}\right) \cdot \left( {{{2}^{k}}+{{2}^{{2m-1-p-k}}}} \right)} \right]}} \end{equation}
sofern $ ~{{2}^{{m+1}}}-1>n\ge 3\cdot {{2}^{{m-1}}}$ oder $ 3\cdot {{2}^{{m-1}}}-1>n\ge {{2}^{m}}$ . In den beiden Sonderfällen $ ~n={{2}^{{m+1}}}-1$ und $ n=3\cdot {{2}^{{m-1}}}-1$ ist $ \Delta {{P}_{2}}\left( n \right)=2$.
Die Folge lässt sich auch rekursiv berechnen (wie stets, $ m=\lfloor {\log}_{2}\left( n \right) \rfloor $ gesetzt)
\begin{align} {\Delta P_2 (n)= \left\{ \begin{array}{lrcl} 2\cdot \Delta P_2\ (n-2^{m-1}) \text{,} &2^{m}\le n&<&2^{m}+2^{m-2}-1 \\ 6, &n&=&2^{m}+2^{m-2}-1 \\ \Delta P_2 (n-2^{m-2}) \text{,} &2^{m}+2^{m-2}\le n&<&2^{m}+2^{m-1}-1 \\ 2, &n&=&2^m+2^{m-1}-1 \\ ( 2+(-1)^n)\cdot \Delta P_2 (n-2^{m-1})\text{,} &2^m+2^{m-1}\le n&<&2^{m+1} \end{array} \right. } \end{align}
Die Rekursionsbeziehung gilt ab $ n=5$, die Bezugswerte für $ n=1,~2,~3,~4~$ sind $ \Delta {{P}_{2}}\left( n \right) = 1, 2, 2, 2$. Der folgenden Umschreibung kann man unmittelbar entnehmen, wie sich nachfolgende Glieder aus den vorhergehenden bestimmen lassen. \begin{align} \begin{array}{lcll} \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}+k} \right)&=&\left( {2-{{{\left( {-1} \right)}}^{k}}} \right)\cdot \Delta {{P}_{2}}\left( {{{2}^{m}}-1+k} \right) &\text{für }0\le k\le {{2}^{{m-1}}} \\ \Delta {{P}_{2}}\left( {{{2}^{m}}+k} \right)&=&2\cdot \Delta {{P}_{2}}\left( {{{2}^{{m-1}}}+k} \right) &\text{für }0\le k<{{2}^{{m-2}}}-2 \\ \Delta {{P}_{2}}\left( {{{2}^{m}}+{{2}^{{m-2}}}+k} \right)&=&\Delta {{P}_{2}}\left( {{{2}^{m}}+k} \right) &\text{für }0\le k<{{2}^{{m-2}}}-2 \end {array} \end{align}
Wenn man ab einer Stelle $n={{2}^{m}}-1$ jeweils die nächsten $ {{2}^{{m-1}}}$ Folgenglieder nebeneinander schreibt, so sieht man, dass ein symmetrisches Muster entsteht. Für $ n={{2}^{4}}-1=15$ ergibt sich zum Beispiel das Tupel $(2, 8, 12, 8, 6, 8, 12, 8, 2)$. Mit anderen Worten: Die Folge der Differenzen der binären Palindrome bildet ihrerseits wieder symmetrische Muster. Tatsächlich gilt allgemein
\begin{align} {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}-k} \right)={{P}_{2}}\left( {{{2}^{m}}-1+k} \right) \text{, für } 0\le k\le {{2}^{{m-1}}} \end{align}
Wegen $ \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}-k} \right)=2$ für $ k=0$ oder $ k={{2}^{{m-1}}}$ sowie $ \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}-k} \right)=6$ für $ k={{2}^{{m-2}}}$ , werden diese symmetrischen Muster jeweils durch eine $2$ links und rechts begrenzt und haben stets die $6$ als zentrales Element.
Und weil nach obiger Formel die Folgenglieder mit $ n={{2}^{m}}-1+k+{{2}^{{m-1}}}$ direkt aus den Gliedern mit $ n={{2}^{m}}-1+k$ bestimmt werden, ergibt sich gleichfalls
\begin{align} \begin{array}{l} \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}+k} \right)&=\left( {2-{{{\left( {-1} \right)}}^{k}}} \right)\cdot \Delta {{P}_{2}}\left( {{{2}^{m}}-1+k} \right) \\ &=\left( {2-{{{\left( {-1} \right)}}^{k}}} \right)\cdot \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}-k} \right) \\ &=\Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}+{{2}^{{m-1}}}-k} \right) \\ &=\Delta {{P}_{2}}\left( {{{2}^{{m+1}}}-1-k} \right) \end{array} \end{align}
für $ 0\le k\le {{2}^{{m-1}}}$.
Demnach bilden auch die Zahlen ab $ n={{2}^{m}}+{{2}^{{m-1}}}-1$ mit den folgenden $ {{2}^{{m-1}}}$ Gliedern symmetrische Muster von $ {{2}^{{m-1}}}+1$ Elementen, begrenzt mit je einer $2$ sowie der $6$ in der Mitte. Das entsprechende symmetrische Tupel für $ n={{2}^{4}}+{{2}^{3}}-1=23$ lautet $(2, 24, 12, 24, 6, 24, 12, 24, 2)$.
Wenn man die Folge nach den symmetrischen Mustern ordnet und untereinanderschreibt, erkennt man, dass das $n$-te Folgenglied auch einfacher berechnet werden kann.
| $m$ | Folgenglieder$ ~n={{2}^{m}}\ldots n={{2}^{m}}+{{2}^{{m-1}}}-1$ |
| $m$ | Folgenglieder $ n={{2}^{m}}+{{2}^{{m-1}}}\ldots n={{2}^{{m+1}}}-1$ |
| 0 | – |
| 0 | $1$ |
| 1 | $2$ |
| 1 | $2$ |
| 2 | $2, 2$ |
| 2 | $6, 2$ |
| 3 | $4, 6, 4, 2$ |
| 3 | $12, 6, 12, 2$ |
| 4 | $8, 12, 8, 6, 8, 12, 8, 2$ |
| 4 | $24, 12, 24, 6, 24, 12, 24, 2$ |
| 5 | $16, 24, 16, 12, 16, 24, 16, 6, 16, 24, 16, 12, 16, 24, 16, 2$ |
| 5 | $48, 24, 48, 12, 48, 24, 48, 6, 48, 24, 48, 12, 48, 24, 48, 2$ |
Es ergibt sich die folgende Darstellung:
\begin{align} \Delta P_2 (n)= \left\{ \begin{array}{lll} 2\text{,} &n=2^{m+1}-1\text{, oder } &n=3\cdot 2^{m-1}-1 \\ 2^{m-1}\text{,} &n=2^{m}+2k\text{, } &0\le k<2^{m-2} \\ 3\cdot 2^{m-2}\text{,} &n=2^{m}-1+(2k+1)2^1\text{, } &0\le k<2^{m-2} \\ 3\cdot 2^{m-3}\text{,} &n=2^{m}-1+(2k+1)2^2\text{, } &0\le k<2^{m-3} \\ 3\cdot 2^{m-4}\text{,} &n=2^{m}-1+(2k+1)2^3\text{, } &0\le k<2^{m-4} \\ \vdots &\vdots &\vdots \\ 3\cdot 2^{1}\text{,} &n=2^{m}-1+(2k+1)2^{m-2}\text{, } &0\le k<2^{1} \\ 3\cdot 2^{m-1}\text{,} &n=3\cdot 2^{m-1}+2k \text{, } &0\le k<2^{m-2} \\ \end{array} \right. \end{align}
Kompakter geschrieben folgt daraus
\begin{align} \Delta P_2 (n)= \left\{ \begin{array}{llll} 2\text{,} &n=2^{m+1}-1\text{, oder } &n=3\cdot 2^{m-1}-1 \\ 2^{m-1}\text{,} &n=2^{m}+2k\text{, } &0\le k<2^{m-2} \\ 3\cdot 2^{m-1-j}\text{,} &n=2^{m}-1+(2k+1)2^j\text{, } &0\le k<2^{m-1-j}\text{, } &1\le j<m-1 \\ 3\cdot 2^{m-1}\text{,} &n=3\cdot 2^{m-1}+2k \text{, } &0\le k<2^{m-2} \\ \end{array} \right. \end{align}
Das kann man weiter vereinfachen zu
\begin{align} \Delta P_2 (n)= \left\{ \begin{array}{cl} 2\text{,} &n+1 \in \left\{2^{m+1}\text{, } 3\cdot 2^{m-1}\right\} \\ 2^{m-1}\text{,} &n\equiv 0 {\pmod 2} \land n<3\cdot 2^{m-1} \\ 3\cdot 2^{m-1}\text{,} &n\equiv 0 {\pmod 2} \land n \ge 3\cdot 2^{m-1} \\ \dfrac{3\cdot 2^{m-1}}{\text{ggt}\left( {{n+1-2^{m}}{,2^{m}}} \right)} \text{, } &\text{sonst} \\ \end{array} \right. \end{align}
Dabei steht $ \text{ggt}\left( {a,b} \right)$ für die Funktion, die den größten gemeinsamen Teiler von $a$ und $b$ berechnet.
Eine noch etwas kompaktere Form ist die Folgende
\begin{align} \Delta P_2 (n)= \left\{ \begin{array}{cl} 2\text{,} &n+1 \in \left\{2^{m+1}\text{, } 3\cdot 2^{m-1}\right\} \\ \dfrac{\left({2 – {\left( -1 \right)}^{n-(n-1){\left\lfloor {\frac{2n}{3\cdot 2^m}}\right\rfloor} }} \right) \cdot 2^{m-1}}{\text{ggt}\left( {{n+1-2^{m}}{,2^{m}}} \right)} \text{, } &\text{sonst} \\ \end{array} \right. \end{align}
Kehren wir zurück zur Folge der Palindrome. Für die obige Formel zur Berechnung es $n$-ten binären Palindroms $ {{P}_{2}}\left( n \right)$ bekommen wir wegen
\begin{align} \displaystyle {{P}_{2}}\left( n \right)=\underset{{k=1}}{\overset{{n-1}}{\mathop \sum }}\,\Delta {{P}_{2}}\left( k \right)={{P}_{2}}\left( {{{2}^{m}}} \right)+\underset{{k={{2}^{m}}}}{\overset{{n-1}}{\mathop \sum }}\,\Delta {{P}_{2}}\left( k \right) \end{align}
nun eine Alternative auf Basis der Differenzenfolge. Man erhält mit $ m=\lfloor {\log}_{2}\left( n \right) \rfloor $
\begin{align} \begin{array}{l} \displaystyle {P_2} (n)=&\,2^{2m-2}+1+2\left\lfloor {\frac{{n-{{2}^{m}}}}{{{{2}^{{m-1}}}}}} \right\rfloor +\\&\,{{2}^{{m-1}}}\left\lfloor {\frac{1}{2}\min \left( {n+1-{{2}^{m}}{{{,2}}^{{m-1}}}+1} \right)} \right\rfloor +\\&\,3\cdot {{2}^{{m-1}}}\left\lfloor {\frac{1}{2}\max \left( {n+1-3\cdot {{2}^{{m-1}}},0} \right)} \right\rfloor +\\ &\,3\cdot \sum\limits_{{j=2}}^{{m-1}}{{\left( {\left\lfloor {\dfrac{{n+{{2}^{{j-1}}}-{{2}^{m}}}}{{{{2}^{j}}}}} \right\rfloor \cdot {{2}^{{m-j}}}} \right)}} \end{array} \end{align}
Ist $p$ ein vorgegebenes binäres Palindrom, so stellt sich die Frage, das Wievielte in der geordneten Folge der Palindrome es ist. Auch darauf gibt es eine Antwort. Für $ p\ge 1$ gilt mit $ m=\lfloor {\log}_{2}\left( p \right) \rfloor $:
\begin{align} \displaystyle P_{2}^{{-1}}(p)=\left[ {\frac{{5-{{{\left( {-1} \right)}}^{m}}}}{2}+\sum\limits_{{k=1}}^{{^{{\left\lfloor {\frac{m}{2}} \right\rfloor }}}}{{\left[ {\left( {\left\lfloor {p\cdot {{2}^{{-k}}}} \right\rfloor \bmod 2} \right)\cdot {{2}^{{-k}}}} \right]}}} \right]\cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor }}} \end{align}
Das kann man wegen $ n~\bmod~2=n-2\left\lfloor\frac{n}{2}\right\rfloor $ für $ p>2$ umformen zu
\begin{align}\begin{array}{l} P_{2}^{{-1}}(p)=\,&\left( {5-{{{\left( {-1} \right)}}^{m}}} \right)\cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -1}}}-3\cdot \sum\limits_{{k=2}}^{{^{{\left\lfloor {\frac{m}{2}} \right\rfloor }}}}{{\left\lfloor {\dfrac{p}{{{{2}^{k}}}}} \right\rfloor \cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -k}}}}}+\\ &\,\left( {\left\lfloor {\dfrac{p}{2}} \right\rfloor \cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -1}}}-2\cdot \left\lfloor {\dfrac{p}{2}\cdot {{2}^{{^{{-\left\lfloor {\frac{m}{2}} \right\rfloor }}}}}} \right\rfloor } \right)\cdot \left\lfloor {\dfrac{{m-1}}{m}+\dfrac{1}{2}} \right\rfloor \end{array} \end{align}
Zwei andere Schreibweisen ergeben sich mittels der Ersetzung $ ~n~\bmod~2=\frac{1}{2}\left( {1-{{{\left( {-1} \right)}}^{n}}} \right)$
\begin{align} \displaystyle P_{2}^{{-1}}(p)=\left[ {5-{{{\left( {-1} \right)}}^{m}}+\sum\limits_{{k=1}}^{{^{{\left\lfloor {\frac{m}{2}} \right\rfloor }}}}{{\left[ {\left( {1-{{{\left( {-1} \right)}}^{{\left\lfloor {p\cdot {{2}^{{-k}}}} \right\rfloor }}}} \right)\cdot {{2}^{{-k}}}} \right]}}} \right]\cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -1}}} \end{align}
\begin{align} \displaystyle P_{2}^{{-1}}(p)=\frac{1}{2}\left[ {\left( {6-{{{\left( {-1} \right)}}^{m}}} \right)\cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor }}}-1-\sum\limits_{{k=1}}^{{^{{\left\lfloor {\frac{m}{2}} \right\rfloor }}}}{{\left( {{{{\left( {-1} \right)}}^{{\left\lfloor {p\cdot {{2}^{{-k}}}} \right\rfloor }}}\cdot {{2}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -k}}}} \right)}}} \right] \end{align}
Daraus folgt z.B., dass $p=1011951=11010010110100011_2$ das 2012-te binäre Palindrom ist. Eine weitere Frage, die sich hier unmittelbar anschließt: Wenn eine beliebige natürliche Zahl $n$ vorgegeben ist, wie bestimmt sich dann das größte binäre Palindrom kleiner oder gleich $n$? Die Antwort gibt die folgende Formel:
\begin{align} \displaystyle \text{floorbP}(n) =\left\{ {\begin{array}{{ll}} \text{F}\left( {p,m} \right)\text{, } &\text{wenn } \text{F}\left( {p,m} \right)\le n \\ \text{F}\left( {p-{{2}^{q}},s} \right) \text{, } &\text{sonst} \end{array}} \right. \end{align}
wobei
| $ p=1+2\cdot \left \lfloor \frac{{n-1}}{2} \right \rfloor$ |
| $ m=\left \lfloor {\log}_{2}\left( n \right) \right \rfloor $ |
| $ q=\left \lfloor \frac{{m+1}}{2} \right \rfloor$ |
| $ s=\lfloor {\log}_{2}\left( {p-{{2}^{q}}} \right) \rfloor$ |
| $ \displaystyle \text{F}\left( {x,r} \right)=\left\lfloor {\frac{x}{{{{2}^{q}}}}} \right\rfloor \cdot {{2}^{q}}+\sum\limits_{{k=0}}^{{^{{q-1}}}}{{\left[ {\left( {\left\lfloor {\frac{x}{{{{2}^{{r-k}}}}}} \right\rfloor \bmod 2} \right)\cdot {{2}^{k}}} \right]}}$ |
Wie man sieht, gilt für die hier definierte Funktion $\text{F}$
\begin{align} \displaystyle \text{F}\left( {p,m} \right)=\left\lfloor {\frac{p}{{{{2}^{q}}}}} \right\rfloor \cdot {{2}^{q}}+\operatorname{Reversal}\left( p \right)\ \bmod {{2}^{q}} \end{align}
bzw.
\begin{align}\displaystyle \text{F}\left( {p-{{2}^{q}},s} \right)=\left\lfloor {\frac{{p-{{2}^{q}}}}{{{{2}^{q}}}}} \right\rfloor \cdot {{2}^{q}}+\operatorname{Reversal}\left( {p-{{2}^{q}}} \right)\ \bmod {{2}^{q}} \end{align}
Dabei steht $ \displaystyle \text{Reversal} \left( {x} \right)\ $ für die Umkehrung des Bitmusters von $x$.
Weiter kann man nun fragen, wie viele Palindrome $<2^n$ es gibt und wie groß die Summe dieser Palindrome ist. Die Anzahl der Palindrome zwischen $2^{n-1}$ und $2^n$ kann man leicht bestimmen. Es gilt (für $ n\ge 1$)
\begin{align} \displaystyle \sum\limits_{{{{2}^{{n-1}}}\le {{P}_{2}}(k)<{{2}^{n}}}}{1}={{2}^{{\left\lfloor {\frac{{n-1}}{2}} \right\rfloor }}} \end{align}
Damit berechnet man die Anzahl der Palindrome $<2^n$ zu für $ n\ge 1$
\begin{align} \begin{array}{l} {{A}_{2}}({{2}^{n}})=\sum\limits_{{0\le {{P}_{2}}(k)<{{2}^{n}}}}{1} &=\left\{ \begin{array}{ll} {2\cdot 2^{\frac{n}{2}}-1} \text{, } &n\equiv 0 {\pmod 2} \\ {3\cdot 2^{\frac{n-1}{2}}-1} \text{, } &n\equiv 1 {\pmod 2} \end{array} \right. \\ &=\dfrac{{5-{{{\left( {-1} \right)}}^{n}}}}{2}\cdot {{2}^{{\left\lfloor {\frac{n}{2}} \right\rfloor }}}-1 \ \end{array} \end{align}
Die Summe der Palindrome zwischen $2^{n-1}$ und $2^n$ ergibt sich ferner für $ n\ge 2$ zu
\begin{align} \displaystyle {{s}_{n}}=\sum\limits_{{ 2^{n-1} \le {{P}_{2}}(k)<{{2}^{n}}}}^{{}}{{{{P}_{2}}(k)}}=\frac{3}{8}\cdot {{2}^{{n+\left\lfloor {\frac{{n+1}}{2}} \right\rfloor }}} \end{align}
Und schließlich erhalten wir damit die Summe der Palindrome $<2^n$ für $ n\ge 1$ zu
\begin{align} \begin{array}{l}\displaystyle {{S}_{2}}({{2}^{n}}) &= \sum\limits_{{0\le {{P}_{2}}(k)<{{2}^{n}}}}^{{}}{{{{P}_{2}}(k)}} \\ &=1+\left\{ \begin{array}{ll} 15\cdot \dfrac{8^{\frac{n-2}{2}}-1}{7}+3\cdot {8^{\frac{n-2}{2}}} \text{, } &n\equiv 0 {\pmod 2} \\ 15\cdot \dfrac{8^{\frac{n-1}{2}}-1}{7} \text{, } &n\equiv 1 {\pmod 2} \end{array} \right. \\&=\dfrac{8}{7} \cdot \left\{ \begin{array}{ll} \dfrac{9}{16}\cdot {2^{3\frac{n}{2}}}-1 \text{, } \quad \quad \quad &n\equiv 0 {\pmod 2} \\ \dfrac{{15}}{8}\cdot {{2}^{{3\frac{{n-1}}{2}}}}-1 \text{, } \quad \quad \quad &n\equiv 1 {\pmod 2} \end{array} \right. \\ &=\dfrac{8}{7}\cdot \left( {\dfrac{3}{4}\dfrac{{4-{{{(-1)}}^{n}}}}{{3+{{{(-1)}}^{n}}}}\cdot {{2}^{{3\left\lfloor {\frac{n}{2}} \right\rfloor }}}-1} \right) \end{array} \end{align}
Weitaus komplizierter ist die Formel für die Summe der binären Palindrome, die kleiner oder gleich einem vorgegebenen Palindrom $p$ sind. Die folgende Formel gilt für binäre Palindrome , wobei $ m=\lfloor {\log}_{2}\left( p \right) \rfloor $
\begin{align} \begin{array}{l} \sum\limits_{0\le {P_2}(k)\le p}^{}{{P_2}(k)}=&\,\sum\limits_{{0 \le {P_2}(k)<{2^n}}}^{}{{P_2}(k)}+\left( {\left\lfloor {p\cdot {2^{{-\left\lfloor {\frac{m}{2}} \right\rfloor }}}} \right\rfloor \bmod 2} \right)\cdot p\,+\\ &\,{2^m}+1+\sum\limits_{k=1}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -1}}{{\left( {\left\lfloor {\dfrac{p}{2^k}} \right\rfloor \bmod 2} \right)\cdot {R_ {{m(p)}{k}}(p)}}} \end{array} \end{align}
wobei ${R_ {{m(p)}{k}}(p)}$ definiert ist als
\begin{align} \begin{array}{l} {R_ {{m(p)}{k}}(p)}=&\, {2^k}+{2^{m-k}}+\sum\limits_{j=0}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k}}{{{s_{m-2k-2j-1}}{2^{k+j+1}}}}+\\ &\, \left( {\left\lfloor {p\cdot {{2}^{{-\left\lfloor {\frac{m}{2}} \right\rfloor }}}} \right\rfloor \bmod 2} \right) \cdot \left( {\sum\limits_{j=0}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k}}{{{a_{m-2k-2j-1}}}}} \right) \cdot \sum\limits_{j=0}^{k-1} \left( {{2^j}+{2^{m-j}}} \right) \end{array} \end{align}
sowie ${{s}_{m}}$ und ${{a}_{m}}$ folgendermaßen
\begin{align} {{s}_{m}}=&\sum\limits_{{ 2^{m-1} \le {{P}_{2}}(k)<{{2}^{m}}}}^{{}}{{{{P}_{2}}(k)}}=\frac{3}{8}\cdot {{2}^{{m+\left\lfloor {\frac{{m+1}}{2}} \right\rfloor }}}\\ {{a}_{m}}=&\sum\limits_{{ 2^{m-1} \le {{P}_{2}}(k)<{{2}^{m}}}}^{{}}{1}={{2}^{{\left\lfloor {\frac{{m-1}}{2}} \right\rfloor }}} \end{align}
gesetzt sind. Die entsprechenden Summenausdrücke über ${{{s_{m-2k-2j-1}}{2^{k+j+1}}}}$ und ${{{a_{m-2k-2j-1}}}}$ in der Definition von ${R_ {{m(p)}{k}}(p)}$ kann man auswerten und findet
\begin{align} \sum\limits_{{j=0}}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k}}{{{{s}_{{m-2k-2j-1}}}}}{{2}^{{k+j+1}}}=&\,{{2}^{{m-\left\lfloor {\tfrac{m}{2}} \right\rfloor +1}}}\left( {{{4}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k-1}}}-1} \right)+\left( {2-{{{\left( {-1} \right)}}^{m}}} \right) {{2}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor}}} \\ \sum\limits_{{j=0}}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k}}{{{{a}_{{m-2k-2j-1}}}}}=&\,{{2}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k}}} \end{align}
Damit erhält man
\begin{align} \begin{array}{l} {R_{{m(p)}{k}}(p)}=&\, {{2}^{k}}+{{2}^{{m-k}}}+{{2}^{{m-\left\lfloor {\tfrac{m}{2}} \right\rfloor +1}}}\left( {{{4}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k-1}}}-1} \right) + \left( {2-{{{\left( {-1} \right)}}^{m}}} \right) {{2}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor}}} + \\ &\,{{2}^{{\left\lfloor {\tfrac{m}{2}} \right\rfloor -k}}}\left( {p-\left\lfloor {\left( {p\bmod {{2}^{{m-k+1}}}} \right)\cdot {{2}^{{-k}}}} \right\rfloor \cdot {{2}^{k}}} \right) \end{array} \end{align}
und es ergibt sich schließlich die Summenformel
\begin{align} \begin{array}{l} \sum\limits_{{0\le {{P}_{2}}\left( k \right)\le p}}^{{}}{{{{P}_{2}}(k)}}=&\,\dfrac{8}{7}\cdot \left( {\dfrac{3}{4}\cdot \dfrac{{4-{{{\left( {-1} \right)}}^{m}}}}{{3+{{{\left( {-1} \right)}}^{m}}}}\cdot {{2}^{{3\left\lfloor {\frac{m}{2}} \right\rfloor }}}-1} \right)+\\&\,\left( {\left\lfloor {p\cdot {{2}^{{-\left\lfloor {\frac{m}{2}} \right\rfloor }}}} \right\rfloor \bmod 2} \right)\cdot p+{{2}^{m}}+1+\\ &\,\sum\limits_{{k=1}}^{{\left\lfloor {\frac{m}{2}} \right\rfloor -1}}{{\left( {\left\lfloor {\dfrac{p}{{{{2}^{k}}}}} \right\rfloor \bmod 2} \right)\cdot {R_{{m(p)}{k}}(p)} }} \end{array} \end{align}
Will man die Summe der Palindrome bis zu einem bestimmten Index bestimmen, also
\begin{align} \displaystyle \sum\limits_{{k=1}}^{n}{{{{P}_{2}}(k)}} \end{align}
so muss man zunächst $p={{P}_{2}}\left( n \right)$ berechnen und kann dann die vorstehende Formel anwenden.