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