Zahlen

⇐ 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: https://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: https://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.


⇐⇑⇒

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert