Einführung

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, 353, 757, 1221, 5335, 48584, 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 (Hex)
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

Basis 10 (Dezimal)	Basis 2 (Binär)	Basis 3	Basis 5	Basis 8 (Oktal)	Basis 16 (Hex)
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

Basis 10 (Dezimal)	Basis 2 (Binär)	Basis 3	Basis 5	Basis 8 (Oktal)	Basis 16 (Hex)
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

Basis 10 (Dezimal)	Basis 2 (Binär)	Basis 3	Basis 5	Basis 8 (Oktal)	Basis 16 (Hex)
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

Basis 10 (Dezimal)	Basis 2 (Binär)	Basis 3	Basis 5	Basis 8 (Oktal)	Basis 16 (Hex)
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

Wenden wir uns zunächst den dezimalen Palindromen zu.

Dezimale Palindrome

Die ersten dezimalen Palindrome sind:

(1) $\begin{equation*} \begin{split} &0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,\\&141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,\\&303,313,323,333,343,353,363,373,383,393,404,414,424,434,444,454,\cdots,\\&979,989,999,1001,1111,1221,1331,1441,1551,1661,1771,1881,1991,\\&2002,2112,2222,2332,2442,2552,2662,2772,2882,2992,3003,3113,3223,\cdots,\\&9779,9889,9999,10001,10101,10201,10301,10401,10501,10601,10701,\cdots,\\&10801,10901,11011,11111,11211,11311,11411,\11511,11611,11711,11811\cdots,\\&89798,89898,89998,90009,90109,90209,90309,90409,90509,90609,90709,\\&90809,90909,91019,91119,91219,91319,91419,91519,91619,91719,91819,\cdots,\\&99799,99899,99999,100001,101101,102201,103301,104401,105501,106601 \cdots \end{split} \end{equation*}$

Die Palindrome werden fortlaufend nummeriert, beginnend mit dem Index 1. Das erste solche Palindrome ist also die Zahl $0$ , das zweite die $\large 1$ , usw. Formal bezeichnen wir das $n$ -te dezimale Palindrom mit $P_{10}(n)$ . Es gilt daher z.B. $P_{10}(1) = 0$ , $P_{10}(2) = 1$ , $P_{10}(10) = 9$ , $P_{10}(11) = 11$ , $P_{10}(19) = 99$ , $P_{10}(20) = 101$ .

Wenn man die Palindrome solchermaßen fortlaufend notiert, erkennt man eine erste Gesetzmäßigkeit.

$\Large \boldsymbol {n}$	$\Large \boldsymbol {P_{10}(n)}$
$1 \cdots 10$	$0 \cdots 9$
$11 \cdots 19$	$11 \cdots 99$
$20 \cdots 109$	$101 \cdots 999$
$110 \cdots 199$	$1001 \cdots 9999$
$200 \cdots 1099$	$10001 \cdots 99999$
$1100 \cdots 1999$	$100001 \cdots 999999$
$2000 \cdots 10999$	$1000001 \cdots 9999999$

Palindrome mit der Nummer $n = 2 \cdot 10^q$ lauten daher $P_{10}(n) = 10^{2q} + 1$ . Für $n = 2 \cdot 10^q - 1$ gilt dagegen $P_{10}(n) = 10^{2q+1} - 1$ . Man erkennt ebenfalls die Abhängigkeiten $P_{10}(10^q + 10^{q-1}) = 10^{2q-1} + 1, \, q > 0$ , sowie $P_{10}(10^q + 10^{q-1} - 1) = 10^{2q-1} - 1, \, q > 0$ . Die weitergehende Analyse zeigt

(2) $\begin{equation*} P_{10}((d+1) \cdot 10^q) = d \cdot 10^{2q} +d \end{equation*}$

für $1 \le d \le 9, \, q \ge 0$ , sowie

(3) $\begin{equation*} P_{10}((d+10) \cdot 10^{q-1}) = d \cdot 10^{2q-1} + d \end{equation*}$

für $1 \le d \le 9, \,q > 0$ .

Bestimmung von dezimalen Palindromen

Im Folgenden geht es um die Bestimmung von dezimalen Palindromen, wir wollen also eine formelmäßige Beziehung für $P_{10}(n)$ . Damit wird die Frage beantwortet: Wie lautet das $n$ -te dezimale Palindrom?

Wir werden dazu drei Lösungen präsentieren: die rekursive Berechnung, die direkte formelmäßige Berechnung sowie eine anschauliche Schnellbestimmung völlig ohne Hilfsmittel.

Die rekursive Berechnung

Zunächst drängt sich ein rekursiver Ansatz auf. Nehmen wir als Beispiel das Palindrom $91319$ . Es setzt sich offensichtlich zusammen aus den drei Palindromen $90009$ , $101$ und $3$ und kann aus diesen mittels der Summe $91319 = 90009 + 10\cdot 101 + 100 \cdot 3$ rekonstruiert werden. Noch einfacher ist die zweistufige Ableitung $91319 = 90009 + 10\cdot 131$ mit $131 = 101 + 10 \cdot 3$ . Ein weiteres Beispiel: $50077005 = 50000005 + 1000\cdot 77$ . Der Rekursionsansatz könnte daher lauten:

(4) $\begin{equation*} P_{10}(n) = P_{10}(x) + 10^p \cdot P_{10}(m) \end{equation*}$

Wobei die Größen $x, m$ und der Exponent $p$ geeignet aus $n$ zu wählen bzw. zu errechnen sind. Nach der vorstehenden Betrachtung über die einfach zu bestimmenden Palindrome für Vielfache von Zehnerpotenzen $n = j \cdot 10^k$ sowie $10^k + j \cdot 10^{k-1}$ , erscheint es sinnvoll, den Wert für $x < n$ im entsprechenden Wertebereich zu wählen und die weiterten Parameter $p$ und $m$ auf dieser Basis zu bestimmen. Wir formulieren daher die folgende Rekursionsbeziehung

(5) $\begin{equation*} P_{10}(n) = d \cdot \left(10^q + 1\right) + 10^p \cdot P_{10}(m) \end{equation*}$

Damit können wir für $n > 10$ das $n$ -te dezimale Palindrom rekursiv berechnen.

Die Parameter $d,\, p,\, q$ und $m$ sind dabei folgendermaßen zu bestimmen: Wenn $\left\lfloor\log_{10}\left(\frac{10n+1}{11}\right)\right\rfloor = \left\lfloor\log_{10}\left(\frac{10n+1}{20}\right)\right\rfloor$ , dann ist

(6) $\begin{equation*} q = 2\cdot \left\lfloor\log_{10}\left(\frac{10n+1}{11}\right)\right\rfloor \end{equation*}$

ansonsten gilt

(7) $\begin{equation*} q = 2\cdot \left\lfloor\log_{10}\left(\frac{10n+1}{11}\right)\right\rfloor - 1 \end{equation*}$

Damit errechnet man den weiteren Parameter $d$ zu

(8) $\begin{equation*} d = \displaystyle \left(\left\lfloor \frac{n}{10^{\left\lfloor\frac{q}{2}\right\rfloor}} \right\rfloor - \frac{(1 + (-1)^q)}{2} \right) \bmod 10 \end{equation*}$

Schließlich erhält man $m$ und $p$ mittels des Hilfsparameters $n_0$ .

(9) $\begin{equation*} n_0 = \displaystyle \frac{1}{2}(2d+11-9(-1)^q)\cdot 10^{\left\lfloor\frac{q}{2}\right\rfloor} \end{equation*}$

(10) $\begin{equation*} m = \begin{cases}\large {1}, &\text{falls}\; n = n_0 \\ \large {n - n_0 + 10^{\left\lfloor\log_{10}\left(n-n_0\right)\right\rfloor}}, &\text{falls}\; q \bmod 2 = 0 \\ \large {n - n_0 + 10^{\left\lfloor\log_{10}\left(n-n_0\right) \right\rfloor + 1}}, &\text{sonst}\end{cases} \end{equation*}$

(11) $\begin{equation*} p = \left\lfloor\log_{10}\left(\frac{10n+1}{11}\right)\right\rfloor - \left\lfloor\log_{10}\left(\frac{10m+1}{11}\right)\right\rfloor\end{equation*}$

Ein Rechenbeispiel für $n = 237$ . Wie lautet das betreffende dezimale Palindrom?

Wegen $\left\lfloor\log_{10}\left(\frac{10 \cdot 237+1}{11}\right)\right\rfloor = 2 = \left\lfloor\log_{10}\left(\frac{10\cdot 237 +1}{20}\right)\right\rfloor$ , erhalten wir

(12) $\begin{equation*} \begin{split} q &= 2\cdot 2 = 4\) \\ d&= \left(\left\lfloor \frac{237}{10^{\left\lfloor\frac{q}{2}\right\rfloor}} \right\rfloor - \frac{(1 + (-1)^q)}{2} \right) \bmod 10 \\&= \left(\left\lfloor \frac{237}{10^2} \right\rfloor - 1 \right) \bmod 10 = 1 \\n_0 &= \frac{1}{2}(2d+11-9(-1)^q)\cdot 10^{\left\lfloor\frac{q}{2}\right\rfloor} \\&= \frac{1}{2}(2\cdot 1+11-9)\cdot 10^{2} = 200 \\n - n_0 &= 37 \\m &= 37 + 10^{\left\lfloor\log_{10}\left(37\right)\right\rfloor} = 47 \\p &= \left\lfloor\log_{10}\left(\frac{10\cdot 237+1}{11}\right)\right\rfloor - \left\lfloor\log_{10}\left(\frac{10\cdot 47+1}{11}\right)\right\rfloor = 1 \end{split} \end{equation*}$

Eingesetzt in die Rekursionsformel erhalten wir

(13) $\begin{equation*} \begin{split} P_{10}(237) &= 1 \cdot \left(10^{4} + 1\right) + 10^1 \cdot P_{10}(47) \\&= 10001 + 10\cdot P_{10}(47) \end{split} \end{equation*}$

Das Palindrom mit der Nummer $n=237$ wurde somit auf das kleinere Palindrom mit $n=47$ zurückgeführt. Zur Finalisierung der Rekursion müssen wir auch dieses berechnen.

Analog wie eben folgt:

(14) $\begin{equation*} \begin{split} q &= 2\\d&= 3\\n_0 & = 40\\n - n_0 &=7\\m &= 7 + 10^{\left\lfloor\log_{10}\left(7\right)\right\rfloor} = 8 \\ p &= \left\lfloor\log_{10}\left(\frac{10\cdot 47+1}{11}\right)\right\rfloor - \left\lfloor\log_{10}\left(\frac{10\cdot 8+1}{11}\right)\right\rfloor = 1 \end{split} \end{equation*}$

Damit bekommen wir nun, $P_{10}(8) = 7$ berücksichtigend

(15) $\begin{equation*} \begin{split} P_{10}(237) &= 10001 + 10\cdot P_{10}(47) \\ &= 10001 + 10\cdot \left( 3\cdot \left(10^2 +1\right) + 10 \cdot P_{10}(8) \right) \\&= 10001 + 10\cdot \left(303 + 10 \cdot P_{10}(8)\right) \\&= 10001 + 10\cdot 303 + 100 \cdot P_{10}(8) \\&= 10001 + 3030 + 700 \\&= 13731 \end{split} \end{equation*}$

Die direkte Berechnung

Für $n>10$ kann man mit der Definition $m = \lfloor \log_{10}(n) \rfloor$ das $n$ -te dezimale Palindrom nach folgender Fallunterscheidung berechnen:

Fall 1: $\displaystyle \left\lfloor \frac{n}{10^m}\right\rfloor \bmod 10 > 1$

(16) $\begin{equation*} \begin{split} P_{10}(n) &=(n \bmod 10) \cdot 10^m - \left(1 + 10^{2m}\right) + \\ &\quad \quad \sum \limits_{k=0}^{m-1} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right)\left(10^k + 10^{2m-k}\right) \\ &= \left(n - 10^m\right) \cdot 10^m + \left\lfloor \frac{n}{10^m}\right\rfloor - 1\; + \\& \quad \quad\sum \limits_{k=1}^{m-1} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right) \cdot 10^k \end{split} \end{equation*}$

Fall 2: $\displaystyle \left\lfloor \frac{n}{10^m}\right\rfloor \bmod 10 = 1$ und $\displaystyle\left\lfloor \frac{n}{10^{m-1}}\right\rfloor \bmod 10 = 0$

(17) $\begin{equation*} \begin{split} P_{10}(n) &=(n \bmod 10)\cdot 10^m + 9 \left(1 + 10^{2m}\right) + \\ &\quad \quad \sum \limits_{k=2}^{m-1} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right)\left(10^k + 10^{2m-k}\right) \\ &= \left(n - 10^{m-1}\right) \cdot 10^{m-1} + 9\; + \\ &\quad \quad \sum \limits_{k=1}^{m-2} \left(\left\lfloor \frac{n}{10^{m-k-1}}\right\rfloor \bmod 10\right)\cdot 10^k \end{split} \end{equation*}$

Fall 3: $\displaystyle \left\lfloor \frac{n}{10^m}\right\rfloor \bmod 10 = 1$ und $\displaystyle \left\lfloor \frac{n}{10^{m-1}}\right\rfloor \bmod 10 > 0$

(18) $\begin{equation*} \begin{split} P_{10}(n) &=\sum \limits_{k=1}^{m} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right)\left(10^{k-1} + 10^{2m-k}\right) \\ &= \left(n \bmod 10^m \cdot 10 + n \bmod 10\right) \cdot 10^{m-1} + \\ &\quad \quad \sum \limits_{k=0}^{m-2} \left(\left\lfloor \frac{n}{10^{m-k-1}}\right\rfloor \bmod 10\right)\cdot 10^k \end{split} \end{equation*}$

Eine einfache Formel zur Bestimmung von dezimalen Palindromen

Aus dem Vorstehenden ergibt sich eine anschauliche und leicht ohne jegliche Hilfsmittel durchführbare Ableitung für die Berechnung des $n$ -ten Palindroms. Sei $\left(d_1\; d_2\; d_3 \cdots d_k\right)$ die Ziffernfolge von $n$ als $k$ -Tupel und $\left(p_1\; p_2\; p_3 \cdots p_m\right)$ die Ziffernfolge des entsprechenden Palindroms $p$ als $m$ -Tupel. Man erhält das $n$ -te Palindrom $P_{10}(n)$ nach folgender einfacher Formel:

(19) $\begin{equation*} P_{10}(n) = \begin{cases} \large \left(d_1-1\; d_2\; d_3 \cdots d_k \cdots d_3\; d_2\; d_1 -1\right), & \text{falls}\; d_1 > 0 \\\large \left(9\; d_3 \cdots d_k \cdots d_3\; 9\right), & \text{falls}\; d_1 = 1 \; \text{und} \; d_2 = 0 \\\large \left(d_2\; d_3 \cdots d_k\; d_k \cdots d_3\; d_2\right), & \text{falls}\; d_1 = 1 \; \text{und} \; d_2 > 0 \end{cases} \end{equation*}$

Beispiel 1: $n = 237$ . Wir haben $d_1=2$ , $d_2=3$ , $d_3=7$ . Es gilt $k = 3$ . Nach der Fallunterscheidung trifft der erstgenannte Fall zu. Demzufolge bekommen wir die Ziffernfolge von $P_{10}(n)$ zu $\left( 1 \; 3 \; 7 \; 3 \; 1\right)$ , also $P_{10}(n) = 13731$ .

Beispiel 2: $n = 1082$ . Wir haben $d_1=1$ , $d_2=0$ , $d_3=8, \(d_4=2$ . Es gilt $k = 4$ . Nach der Fallunterscheidung trifft der zweite Fall zu. Nun erhalten wir die Ziffernfolge von $P_{10}(n)$ zu $\left( 9 \; 8 \; 2 \; 8 \; 9\right)$ , mithin $P_{10}(n) = 98289$ .

Beispiel 3: $n = 1546$ . Wir haben $d_1=1$ , $d_2=5$ , $d_3=4, \(d_4=6$ . Es gilt $k = 4$ . Nach der Fallunterscheidung trifft der dritte Fall zu. Wir erhalten für die Ziffernfolge von $P_{10}(n)$ demnach $\left( 5 \; 4 \; 6 \; 6 \; 4 \; 5\right)$ , und folglich $P_{10}(n) = 546645$ .

Die Umkehrung der Palindromformel

Wir fragen nun umgekehrt: Welche Nummer trägt ein vorgegebenes dezimales Palindrom? Konkret: $P = 21312$ . Wie lautet das $n$ , für das gilt: $P_{10}(n) = 21312$ ?

Wegen $P_{10}(3 \cdot 10^2) = 2 \cdot 10^{4} +2 = 20002$ und $P_{10}(4 \cdot 10^2) = 3 \cdot 10^{4} +3 = 30003$ ist $n$ größer als $300$ aber kleiner als $400$ . Für die genaue Bestimmung gehen wir zurück auf die vorstehend dargestellte anschauliche Palindromformel, aus welcher sich die algorithmische Vorschrift zur Berechnung unmittelbar ergibt.

Sei $\left(p_1\; p_2\; p_3 \cdots p_k \cdots p_3\; p_2\; p_1 \right)$ bzw. $\left(p_1\; p_2\; p_3 \cdots p_k \; p_k \cdots p_3\; p_2\; p_1 \right)$ die Ziffernfolge von $P$ als $2k-1$ -Tupel bzw. als $2k$ -Tupel und $\left(d_1\; d_2\; d_3 \cdots d_j\right)$ die Ziffernfolge des gesuchten Wertes für $n$ als $j$ -Tupel. Man erhält $n$ nach folgender Fallunterscheidung in sinngemäßer Umkehrung der Direktformel:

(20) $\begin{equation*} n = \begin{cases} \Large \left(p_1+1\; p_2\; p_3 \cdots p_k \right), \\ \quad \quad \quad \text{falls}\; P \text{ eine ungerade Anzahl von Stellen hat und}\;1 < p_1 < 9 \\\Large \left(1 \; 0 \; p_2 \;p_3 \cdots p_k \right), \\ \quad \quad \quad \text{falls}\; P \text{ eine ungerade Anzahl von Stellen hat und}\; p_1 = 9\\ \Large \left(1 \; p_1 \; p_2 \; p_3 \cdots p_k \right), \\ \quad \quad \quad \text{falls}\; P \text{ eine gerade Anzahl von Stellen hat} \end{cases} \end{equation*}$

Für die formale algorithmische Berechnung definieren wir $m = \left\lfloor \log_{10}(P)\right\rfloor$ und unterscheiden ebenfalls explizit drei Fälle.

Fall 1: $\displaystyle m \bmod 2 = 0\; \text{und}\; 0 < P \bmod 10 < 9$

(21) $\begin{equation*} \begin{split} n &=10^{\frac{m}{2}} + \sum \limits_{k=0}^{\frac{m}{2}} \left(\left\lfloor \frac{P}{10^{k}}\right\rfloor \bmod 10\right) 10^{\frac{m}{2}-k} \\&= \left\lfloor \frac{P}{10^{\frac{m}{2}}}\right\rfloor + 10^{\frac{m}{2}} \end{split} \end{equation*}$

Fall 2: $\displaystyle m \bmod 2 = 0\; \text{und}\; P \bmod 10 = 9$

(22) $\begin{equation*} \begin{split} n &= 10^{\frac{m}{2}+1} + \sum \limits_{k=1}^{\frac{m}{2}} \left(\left\lfloor \frac{P}{10^{k}}\right\rfloor \bmod 10\right) 10^{\frac{m}{2}-k} \\ &= \left\lfloor \frac{P}{10^{\frac{m}{2}}}\right\rfloor + 10^{\frac{m}{2}} \end{split} \end{equation*}$

Fall 3: $\displaystyle m \bmod 2 = 1$

(23) $\begin{equation*} \begin{split} n &= 10^{\frac{m+1}{2}} + \sum \limits_{k=0}^{\frac{m-1}{2}} \left(\left\lfloor \frac{P}{10^{k}}\right\rfloor \bmod 10\right) 10^{\frac{m-1}{2}-k} \\&= \left\lfloor \frac{P}{10^{\frac{m+1}{2}}}\right\rfloor + 10^{\frac{m+1}{2}} \end{split} \end{equation*}$

Beispiel 1: $P = 13731$ . Wir haben $m=4$ und $0 < P \bmod 10 = 1 < 9$ . Nach der Fallunterscheidung trifft der erstgenannte Fall zu. Demzufolge bekommen wir $n = 10^2 +1\cdot 10^2 + 3\cdot 10^1 + 7\cdot 10^0 = 237$ bzw. $\displaystyle \left\lfloor \frac{13731}{10^{\frac{4}{2}}}\right\rfloor + 10^{\frac{4}{2}} = 137+100 = 237$ .

Beispiel 2: $n = 98289$ . Wir haben $m=4$ und $P \bmod 10 = 9$ . Nach der Fallunterscheidung trifft der zweite Fall zu. Nun erhalten wir $n = 10^3 +8\cdot 10^1 + 2\cdot 10^0 = 1082$ bzw. $\displaystyle \left\lfloor \frac{98289}{10^{\frac{4}{2}}}\right\rfloor + 10^{\frac{4}{2}} = 982 + 100 = 1082$ .

Beispiel 3: $n = 546645$ . Wir haben $m=5$ . Nach der Fallunterscheidung trifft der dritte Fall zu. Wir erhalten $n = 10^3 +5\cdot 10^2 + 4\cdot 10^1 +6\cdot 10^0 = 1546$ bzw. $\displaystyle \left\lfloor \frac{546645}{10^{\frac{5+1}{2}}}\right\rfloor + 10^{\frac{5+1}{2}} = 546 + 1000 = 1546$ .

In komprimierter Form können wir für $P>0$ die Umkehrfunktion ohne Fallunterscheidung folgendermaßen auch so schreiben:

(24) $\begin{equation*} \begin{split} n &= \left\lfloor \frac{ P}{ 10^{\left\lfloor \frac{m+1}{2} \right\rfloor}} \right\rfloor + 10^{ \left\lfloor \frac{m+1}{2} \right\rfloor} \\ &= \left\lfloor \frac{\displaystyle P}{\displaystyle 10^{\displaystyle \left\lfloor \frac{\left\lfloor \log_{10}(P) \right\rfloor +1}{2} \right\rfloor}} \right\rfloor + 10^{\displaystyle \left\lfloor \frac{\left\lfloor \log_{10}(P) \right\rfloor +1}{2} \right\rfloor} \end{split} \end{equation*}$

Die Unterscheidung der Fälle wird hier implizit durch die ganzzahlige Division im Exponenten der Zehnerpotenz vorgenommen.

Die Anzahlfunktion für dezimale Palindromen

Aus den oben angegebenen Formeln über dezimale Palindrome für Vielfache von Zehnerpotenzen folgt direkt die Anzahl der Palindrome zwischen $10^{n-1}$ und $10^{n}$ zu

(25) $\begin{equation*} A_{10}\left(10^{n}\right) - A_{10}\left(10^{n-1}\right) = 9\cdot 10^{\left\lfloor\frac{n-1}{2}\right\rfloor}, \; n > 0 \end{equation*}$

Für die Anzahl der dezimalen Palindrome $< 10^{n}$ , $n \ge 0$ , folgt daher nach Aufaddieren vorgenannter Partialsummen

(26) $\begin{align*} A_{10}\left(10^{n}\right) &= \displaystyle \begin{cases} 2\cdot 10^{\frac{n}{2}} - 1, \; &n \bmod 2 = 0 \\\displaystyle 11\cdot 10^{\frac{n-1}{2}} - 1, \; &n \bmod 2 = 1 \end{cases} \\ &= \displaystyle \frac{13 - 9\cdot (-1)^n}{2} \cdot 10^{\left\lfloor\frac{n}{2}\right\rfloor} - 1\end{align*}$

Das Wachstum der Folge dezimaler Palindrome

Dezimale Palindrome gehorchen für $n>1$ der Ungleichung

(27) $\begin{equation*} \frac{10}{121} \cdot n^2 < P_{10}(n) < \frac{1}{4} (n+1)^2 \end{equation*}$

Den folgenden Abbildungen kann man entnehmen, wie die Folge der dezimaler Palindrome mit $n$ wächst und wie die Folgenglieder durch die Ungleichung begrenzt werden.

Beim Grenzübergang $n \rightarrow \infty$ gilt

(28) $\begin{equation*} \liminf_{n \rightarrow \infty} \frac{P_{10}(n)}{n^2} = \frac{10}{121} \end{equation*}$

sowie

(29) $\begin{equation*} \limsup_{n \rightarrow \infty} \frac{P_{10}(n)}{n^2} = \frac{1}{4} \end{equation*}$

Dezimale Palindrome mit einer ungeraden Anzahl von Stellen

Wie man der Diskussion zu den dezimalen Palindromen entnimmt, gibt es prinzipiell zwei verschiedene Arten solcher Palindrome. Solche mit einer ungeraden Anzahl von Stellen und solche mit einer geraden Anzahl von Stellen. Beide haben unterschiedliche Charakteristika und gaben oben diversen Anlass zu Fallunterscheidungen.

Die ersten dezimalen Palindrome mit einer ungeraden Anzahl von Stellen sind:

(30) $\begin{equation*} \begin{split} &0,1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202,212,222,\\&232,242,252,262,272,282,292,303,313,323,333,343,353,363,373,383,393,\\&404,414,424,434,444,454,464,474,484,494,505,515,512,535,545,555,\cdots,\\&969,979,989,999,10001,10101,10201,10301,10401,10501,10601,10701,\cdots,\\&10801,10901,11011,11111,11211,11311,11411,\11511,11611,11711,11811\cdots,\\&89798,89898,89998,90009,90109,90209,90309,90409,90509,90609,90709,\\&90809,90909,91019,91119,91219,91319,91419,91519,91619,91719,91819,\cdots,\\&98989,99099,99199,99299,99399,99499, 99599,99699,99799,99899,99999,\cdots \end{split} \end{equation*}$

Die rekursive Bestimmung

Wir benennen die Palindrome mit dem Formelzeichen $P_{10}^{U}(n)$ . Man kann diese Palindrome ebenfalls rekursiv bestimmen. Der Algorithmus ist sogar einfacher als im allgemeinen Falle.

(31) $\begin{equation*} P_{10}^{U}(n) = d \cdot \left(10^q + 1\right) + 10^p \cdot P_{10}^{U}(m) \end{equation*}$

Damit können wir für $n > 10$ das $n$ -te dezimale Palindrom mit einer ungeraden Anzahl von Stellen effizient berechnen.

Die Parameter $d,\, p,\, q$ und $m$ sind dabei folgendermaßen zu bestimmen:

(32) $\begin{equation*} q = 2\cdot \left\lfloor\log_{10}\left(n-1)\right\rfloor \end{equation*}$

(33) $\begin{equation*} d = \displaystyle \left\lfloor \frac{n-1}{10^{\left\lfloor\frac{q}{2}\right\rfloor}} \right\rfloor \bmod 10 \end{equation*}$

(34) $\begin{equation*} m = (n-1) \bmod 10^{\frac{q}{2}} + 1 \end{equation*}$

(35) $\begin{equation*} p = \frac{q}{2} - \left\lfloor \log_{10}(\max(1,m-1))}\right}\rfloor \end{equation*}$

Rechenbeispiel für $n = 50$ . Wie lautet das betreffende dezimale Palindrom mit einer ungeraden Anzahl von Stellen?

(36) $\begin{equation*} \begin{split} q &= 2\cdot \left\lfloor\log_{10}(49)\right\rfloor= 2 \cdot 1 = 2 \\ d&= \left\lfloor \frac{49}{10^{\frac{2}{2}}} \right\rfloor \bmod 10 = 4 \\m &= 49 \bmod 10^{\frac{2}{2}} + 1 = 10 \\p &= \frac{2}{2} - \left\lfloor \log_{10}(\max(1,9))\right\rfloor = 1 \end{split} \end{equation*}$

Eingesetzt in die Rekursionsformel erhalten wir

(37) $\begin{equation*} \begin{split} P_{10}^{U}(50) &= 4 \cdot \left(10^{2} + 1\right) + 10^1 \cdot P_{10}^{U}(10) \\ &= 404 + 10\cdot P_{10}^{U}(10) \\&= 404 + 10\cdot 9 \\&= 404 + 90 \\ &= 494 \end{split} \end{equation*}$

Die direkte Bestimmung

Für $n > 0$ kann man mit der Definition $m = \lfloor \log_{10}(n-1) \rfloor$ das $n$ -te solche dezimale Palindrom folgendermaßen direkt berechnen:

(38) $\begin{equation*} \begin{split} P_{10}^{U}(n) &=\left((n-1) \bmod 10\right)\cdot 10^m \;+ \\ & \quad \sum \limits_{k=0}^{m-1} \left(\left\lfloor \frac{n-1}{10^{m-k}}\right\rfloor \bmod 10\right)\left(10^k + 10^{2m-k}\right) \\&=\left( n-1 \right) \cdot 10^m + \left\lfloor \frac{n-1}{10^{m}}\right\rfloor \;+ \\ & \quad \sum \limits_{k=1}^{m-1} \left(\left\lfloor \frac{n-1}{10^{m-k}}\right\rfloor \bmod 10\right) \cdot 10^k \end{split} \end{equation*}$

Auch hier ergibt sich eine anschauliche und leicht durchführbare Ableitung für die Berechnung des $n$ -ten solchen Palindroms. Sei $\left(d_1\; d_2\; d_3 \cdots d_k\right)$ die Ziffernfolge von $n-1$ als $k$ -Tupel und $\left(p_1\; p_2\; p_3 \cdots p_m\right)$ die Ziffernfolge des entsprechenden Palindroms $p$ als $m$ -Tupel. Man erhält das $n$ -te Palindrom $P_{10}^{U}(n)$ nach der folgenden einfachen Vorschrift:

(39) $\begin{equation*} \LARGE P_{10}^{U}(n) \Leftrightarrow \large \left(d_1 \; d_2 \; d_3 \cdots d_k \cdots d_3\; d_2\; d_1\right) \end{equation*}$

Man beachte, dass hier $n-1$ und nicht $n$ als Ausgangspunkt für die Zifferndarstellung herangezogen wird.

Beispiel: $n = 140$ . Wir haben $\Large n-1 \Leftrightarrow (1 \; 3 \; 9)$ , also $d_1=1$ , $d_2=3$ , $d_3=9$ . Es gilt $k = 3$ . Demzufolge bekommen wir die Ziffernfolge von $P_{10}^{U}(n)$ zu $\left( 1 \; 3 \; 9 \; 3 \; 1\right)$ , also $P_{10}^{U}(140) = 13931$ . Entsprechend ergibt sich mittels der direkten Bestimmungsformel $P_{10}^{U}(140) = 139 \cdot 10^2 + \left\lfloor \frac{139}{10^2} \right\rfloor + \left\lfloor \frac{139}{10^1} \right\rfloor \bmod 10 \cdot 10^1 = 13900 + 30 + 1 = 13931$ .

Die Umkehrfunktion

Auch hier können wir fragen: Welche Nummer $n$ trägt ein vorgegebenes dezimales Palindrom $P$ mit einer ungeraden Anzahl von Stellen??

Der Blick auf die dargestellte anschauliche Berechnungsvorschrift liefert sofort einen Ansatz für die Umkehrfunktion, da in der Ziffernfolge des Palindroms $P$ die Ziffernfolge von $n-1$ enthalten ist. Mit $m = \lfloor \log_{10}(P) \rfloor$ gilt

(40) $\begin{equation*} \begin{split} n &= 1 + \left\lfloor \frac {P}{10^{\displaystyle \frac{m}{2}}} \right \rfloor \\ &= 1 + \left\lfloor \frac {P}{10^{\displaystyle \frac{\lfloor \log_{10}(P) \rfloor}{2}}} \right \rfloor \end{split} \end{equation*}$

Da wir nur Palindrome mit einer ungeraden Anzahl von Stellen betrachten, gibt es stets eine gerade Zahl $k, \, k \ge 0$ , so dass $10^k \le P <10^{k+1}$ . Nach Definition ist $m$ diese gerade Zahl, so dass der Exponent $\frac{m}{2}$ in der Formel ganz ist.

Die Anzahlfunktion

Die Anzahl der Palindrome $P$ mit einer ungeraden Anzahl von Stellen zwischen $10^{n-1}$ und $10^{n}$ , genauer, $10^{n-1} \le P < \(10^{n}$ , ist

(41) $\begin{equation*} \begin{split} A_{10}^U\left(10^{n}\right) - A_{10}^U\left(10^{n-1}\right) &= \begin{cases} 0, &\text{falls} \; n \bmod 2 = 0 \\ \displaystyle 9\cdot 10^{\frac{n-1}{2}}, &\text{sonst} \end{cases} \\ \\ &= \displaystyle 10^{\displaystyle \left\lfloor\frac{n+1}{2}\right\rfloor} - 10^{\displaystyle \left\lfloor\frac{n}{2}\right\rfloor} \end{split} \end{equation*}$

Dies gilt für $n > 0$ , die letzte Form auch für $n=0$ .

Für die Anzahl solcher Palindrome $< 10^{n}$ , $n \ge 0$ , folgt daher nach Aufaddieren vorgenannter Differenzen

(42) $\begin{equation*} A_{10}^U\left(10^{n}\right) &=10^{\displaystyle \left\lfloor\frac{n+1}{2}\right\rfloor} \end{equation*}$

Das Wachstum der Folge

Für $n>1$ gilt die Ungleichung

(43) $\begin{equation*} \frac{(n-1)^2}{10} < P_{10}^U(n) < n^2 \end{equation*}$

Beim Grenzübergang $n \rightarrow \infty$ gilt

(44) $\begin{equation*} \liminf_{n \rightarrow \infty} \frac{P_{10}^U(n)}{n^2} = \frac{1}{10} \end{equation*}$

sowie

(45) $\begin{equation*} \limsup_{n \rightarrow \infty} \frac{P_{10}^U(n)}{n^2} = 1 \end{equation*}$

Dezimale Palindrome mit einer geraden Anzahl von Stellen

Die ersten dezimalen Palindrome mit einer geraden Anzahl von Stellen sind:

(46) $\begin{equation*} \begin{split} &11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661,1771,1881,1991\\&2002,2112,2222,2332,2442,2552,2662,2772,2882,2992,3003,3113,3223,3333,\cdots,\\&9779,9889,9999,100001,101101,102201,103301,104401,105501,106601,107701,\cdots,\\ &108801,109901,110011,111111,112211,113311,114411,115511,116611,117711,\cdots,\end{split} \end{equation*}$

Die rekursive Bestimmung

Ähnlich wie oben kann man auch die Palindrome mit einer geraden Anzahl von Stellen rekursiv berechnen. Wir benennen diese Palindrome mit dem Formelzeichen $P_{10}^{G}(n)$ .

(47) $\begin{equation*} P_{10}^{G}(n) = d \cdot \left(10^q + 1\right) + 10^p \cdot P_{10}^{G}(m) \end{equation*}$

Zusätzlich definieren wir $P_{10}^{G}(0) := 0$ . Damit können wir für $n > 0$ das $n$ -te solche Palindrom effizient bestimmen.

Die Parameter $d,\, p,\, q$ und $m$ sind dabei folgendermaßen zu bestimmen:

(48) $\begin{equation*} q = 2\cdot \left\lfloor\log_{10}\left(n)\right\rfloor + 1\end{equation*}$

(49) $\begin{equation*} d = \displaystyle \left\lfloor \frac{n}{10^{\frac{q-1}{2}}} \right\rfloor \bmod 10 \end{equation*}$

(50) $\begin{equation*} m = n \bmod 10^{\frac{q-1}{2}} \end{equation*}$

(51) $\begin{equation*} p = \frac{q-1}{2} - \left\lfloor \log_{10}(\max(1,m))}\right}\rfloor \end{equation*}$

Rechenbeispiel für $n = 53$ . Wie lautet das betreffende dezimale Palindrom mit einer geraden Anzahl von Stellen?

(52) $\begin{equation*} \begin{split} q &= 2\cdot \left\lfloor\log_{10}(53)\right\rfloor= 2 \cdot 1 + 1= 3 \\ d&= \left\lfloor \frac{53}{10^{\frac{3-1}{2}}} \right\rfloor \bmod 10 = 5 \\m &= 53 \bmod 10^{\frac{3-1}{2}} = 3 \\p &= \frac{3-1}{2} - \left\lfloor \log_{10}(\max(1,3))\right\rfloor = 1 \end{split} \end{equation*}$

Eingesetzt in die Rekursionsformel erhalten wir

(53) $\begin{equation*} \begin{split} P_{10}^{G}(53) &= 5 \cdot \left(10^{3} + 1\right) + 10^1 \cdot P_{10}^{G}(3) \\ &= 5005 + 10 \cdot P_{10}^{G}(3) \\&= 5005 + 10 \cdot 33 \\&= 5005 + 330 \\ &= 5335 \end{split} \end{equation*}$

Die direkte Bestimmung

Für $n > 0$ kann man mit Hilfe der Definition $m = \lfloor \log_{10}(n) \rfloor$ das $n$ -te solche dezimale Palindrom folgendermaßen direkt berechnen:

(54) $\begin{equation*} \begin{split} P_{10}^{G}(n) &=\sum \limits_{k=0}^{m} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right)\left(10^k + 10^{2m+1-k}\right) \\&=\sum \limits_{k=0}^{m} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right)\left(10^k + 10^{2m+1-k}\right) \end{split} \end{equation*}$

Die anschauliche Ableitung für die Berechnung des $n$ -ten mit einer geraden Anzahl von Stellen ist ähnlich einfach wie im Falle der ungeraden Palindrome. Sei $\left(d_1\; d_2\; d_3 \cdots d_k\right)$ die Ziffernfolge von $n$ als $k$ -Tupel und $\left(p_1\; p_2\; p_3 \cdots p_m\right)$ die Ziffernfolge des entsprechenden Palindroms $p$ als $m$ -Tupel. Man erhält das $n$ -te Palindrom $P_{10}^{G}(n)$ nach folgender simplen Vorschrift:

(55) $\begin{equation*} \LARGE P_{10}^{G}(n) \Leftrightarrow \large \left(d_1 \; d_2 \; d_3 \cdots d_k \; d_k \cdots d_3\; d_2\; d_1\right) \end{equation*}$

Beispiel: $n = 139$ . Wir haben $\Large n \Leftrightarrow (1 \; 3 \; 9)$ , also $d_1=1$ , $d_2=3$ , $d_3=9$ . Es gilt $k = 3$ . Demzufolge bekommen wir die Ziffernfolge von $P_{10}^{G}(n)$ zu $\left( 1 \; 3 \; 9 \; 9 \; 3 \; 1\right)$ , also $P_{10}^{G}(139) = 139931$ .

Die Umkehrfunktion

Wir fragen analog: Welche Nummer $n$ trägt ein vorgegebenes dezimales Palindrom $P$ mit einer geraden Anzahl von Stellen?

Auch hier liefert der Blick auf die dargestellte anschauliche Berechnungsvorschrift sofort einen Ansatz für die Umkehrfunktion, da in der Ziffernfolge des Palindroms $P$ die Ziffernfolge von $n$ enthalten ist. Mit $m = \lfloor \log_{10}(P) \rfloor$ gilt

(56) $\begin{equation*} \begin{split} n &= \left\lfloor \frac {P}{10^{\displaystyle \frac{m+1}{2}}} \right \rfloor \\ &= \left\lfloor \frac {P}{10^{\displaystyle \frac{\lfloor \log_{10}(P) \rfloor +1}{2}}} \right \rfloor \end{split} \end{equation*}$

Da nur Palindrome mit einer geraden Anzahl von Stellen betrachtet werden, gibt es stets eine ungerade Zahl $k$ , so dass $10^k < P <10^{k+1}$ . Nach Definition ist $m$ diese ungerade Zahl, und somit der Exponent $\frac{m+1}{2}$ in der Formel eine ganze Zahl.

Die Anzahlfunktion

Die Anzahl der Palindrome $P$ mit einer geraden Anzahl von Stellen zwischen $10^{n-1}$ und $10^{n}$ ist

(57) $\begin{equation*} A_{10}^G\left(10^{n}\right) - A_{10}^G\left(10^{n-1}\right) = \displaystyle \begin{cases} 9\cdot 10^{\frac{n}{2}-1}, &\text{falls} \; n \bmod 2 = 0 \\ 0, &\text{sonst} \end{equation*}$

(58) $\begin{equation*} \begin{split} A_{10}^U\left(10^{n}\right) - A_{10}^U\left(10^{n-1}\right) &= \begin{cases} \displaystyle 9\cdot 10^{\frac{n-2}{2}}, &\text{falls} \; n \bmod 2 = 0 \\ 0, &\text{sonst} \end{cases} \\ \\ &= \displaystyle 10^{\displaystyle \left\lfloor\frac{n}{2}\right\rfloor} - 10^{\displaystyle \left\lfloor\frac{n-1}{2}\right\rfloor} \end{split} \end{equation*}$

wobei $n > 0$ .

Für die Anzahl solcher Palindrome $< 10^{n}$ , $n \ge 0$ , folgt daher nach Aufaddieren vorgenannter Differenzen

(59) $\begin{equation*} A_{10}^G\left(10^{n}\right) =10^{\displaystyle \left\lfloor\frac{n}{2}\right\rfloor} - 1 \end{equation*}$

Das Wachstum der Folge

Für $n>1$ gilt die Ungleichung

(60) $\begin{equation*} n^2 < P_{10}^G(n) < 10 \cdot (n+1)^2 \end{equation*}$

Beim Grenzübergang $n \rightarrow \infty$ gilt

(61) $\begin{equation*} \liminf_{n \rightarrow \infty} \frac{P_{10}^G(n)}{n^2} = 1 \end{equation*}$

sowie

(62) $\begin{equation*} \limsup_{n \rightarrow \infty} \frac{P_{10}^G(n)}{n^2} = 10 \end{equation*}$

Beim Vergleich mit dem Wachstum der Palindrome mit einer ungeraden Anzahl von Stellen fällt auf, dass $P_{10}^G(n)$ offenbar schneller wächst als $P_{10}^U(n)$ . Tatsächlich ist $P_{10}^G(n)$ für große $n$ ungefähr $\Large 10\times$ größer als $P_{10}^U(n+1)$ . Dies erkennt man auf Basis des Zusammenhangs

(63) $\begin{equation*} \begin{split} P_{10}^G(n)&= 10 \cdot \left(P_{10}^U(n+1) - P_{10}^U(n+1) \bmod 10^{m} \right) \;+ \\ & \quad \left\lfloor\frac{P_{10}^U(n+1)}{10^{m}}\right\rfloor \bmod 10 \cdot 10^{m} + P_{10}^U(n+1) \bmod 10^{m} \\ &= 10 \cdot P_{10}^U(n+1) + \left\lfloor\frac{P_{10}^U(n+1)}{10^{m}}\right\rfloor \bmod 10 \cdot 10^{m} \;- \\ & \quad \quad 9 \cdot P_{10}^U(n+1) \bmod 10^{m} \end{split} \end{equation*}$

woraus folgt

(64) $\begin{equation*} \begin{split} \frac{P_{10}^G(n)}{P_{10}^U(n+1)}&= 10 + \frac{\left\lfloor\frac{P_{10}^U(n+1)}{10^{m}}\right\rfloor \bmod 10 \cdot 10^{m} - 9\cdot P_{10}^U(n+1) \bmod 10^{m}}{P_{10}^U(n+1)} \\ &= 10 + O\left(10^{-m}\right) \end{split} \end{equation*}$

Dabei haben wir $\displaystyle m = 2\cdot \lfloor \log_{10}(n) \rfloor$ und $\displaystyle \frac{1}{P_{10}^U(n+1)} = O(10^{-2m})$ berücksichtigt. Es gilt demnach

(65) $\begin{equation*} \lim_{n \rightarrow \infty} \frac{P_{10}^G(n)}{P_{10}^U(n+1)} = 10 \end{equation*}$

Der Zusammenhang zwischen der Folge der ungeraden, geraden und allgemeinen dezimalen Palindromen

Jedes dezimale Palindrom mit einer ungeraden oder einer geraden Anzahl von Stellen ist auch ein allgemeines dezimales Palindrom, allerdings zu einem anderen Index $n$ . Umgekehrt hat natürlich jedes dezimale Palindrome entweder einer ungerade oder eine gerade Anzahl von Stellen. In diesem Falle stellt sich jeweils die Frage, für welchen Index $n$ ?

Binäre Palindrome

Im Folgenden betrachten wir 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 17 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).

In der nachfolgenden Tabelle sind die ersten 32 binären Palindrome in binärer und dezimaler Darstellung aufgelistet.

$\Large \boldsymbol {n}$	$\Large \boldsymbol {P_2(n)}$ – binär –	$\Large \boldsymbol {P_2(n)}$ – dezimal –
1	0	0
2	1	1
3	11	3
4	101	5
5	111	7
6	1001	9
7	1111	15
8	10001	17
9	10101	21
10	11011	27
11	11111	31
12	100001	33
13	101101	45
14	110011	51
15	111111	63
16	1000001	65
17	1001001	73
18	1010101	85
19	1011101	93
20	1100011	99
21	1101011	107
22	1110111	119
23	1111111	127
24	10000001	129
25	10011001	153
26	10100101	165
27	10111101	189
28	11000011	195
28	11011011	219
30	11100111	231
31	11111111	255
32	100000001	257

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

(66) $\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 $P_2(2^{10}+1) = {{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:

(67) $\begin{equation*} {{P}_{2}}\left( n \right)={{2}^{{2k-q}}}+1+{{2}^{p}}\cdot {{P}_{2}}\left( m \right) \end{equation*}$

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 Möglichkeit zur direkten Bestimmung des $n$ -ten binären Palindroms ist die Folgende (für $n\ge 3$ ):

(68) $\begin{equation*} \begin{split} 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) \left( {2^k+{2^{2m-1-p-k}}} \right)} \right] \end{split} \end{equation*}$

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:

Hiermit berechnete binäre Palindrome sind in der nachfolgenden Tabelle aufgelistet.

$\Large \boldsymbol {n}$	$\Large \boldsymbol {P_2(n)}$	$\Large \boldsymbol {n}$	$\Large \boldsymbol {P_2(n)}$
$10$	$27$	$200$	$9225$
$20$	$99$	$500$	$62511$
$30$	$231$	$10^3$	$249903$
$40$	$387$	$10^4$	$24183069$
$50$	$585$	$10^5$	$2258634081$
$60$	$903$	$10^6$	$249410097687$
$70$	$1241$	$10^7$	$24350854001805$
$80$	$1539$	$10^8$	$2229543293296319$
$90$	\1879\)	$10^{9}$	$248640535848971067$
$100$	$2313$	$10^{10}$	$24502928886295666773$

Wachstum der Folge binärer Palindrome

Binäre Palindrome gehorchen für $n>1$ der Ungleichung

(69) $\begin{equation*} \frac{2}{9} n^2 < P_2(n) < \frac{1}{4} (n+1)^2 \end{equation*}$

Den folgenden Abbildiungen kann man entnehmen, wie die Folge der binären Palindrome mit $n$ wächst und wie die Folgenglieder durch die Ungleichung begrenzt werden.

Beim Grenzübergang $n \rightarrow \infty$ gilt

(70) $\begin{equation*} \liminf_{n \rightarrow \infty} \frac{P_2(n)}{n^2} = \frac{2}{9} \end{equation*}$

sowie

(71) $\begin{equation*} \limsup_{n \rightarrow \infty} \frac{P_2(n)}{n^2} = \frac{1}{4} \end{equation*}$

Differenzen von binären Palindromen

Die Differenzen aufeinander folgender Palindrome bilden eine interessante Folge:

$\begin{equation*} \begin{split} &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{split} \end{equation*}$

(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$

(72) $\begin{equation*} \begin{split} \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{split} \end{equation*}$

und ab $m=1$

(73) $\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

(74) $\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

(75) $\begin{equation*} \begin{split} \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{split} \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)

(76) $\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.

(77) $\begin{equation*} \begin{split} \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}+k} \right)&=\left( {2-{{{\left( {-1} \right)}}^{k}}} \right) \Delta {{P}_{2}}\left( {{{2}^{m}}-1+k} \right) \quad \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) \quad \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) \quad \text{für }0\le k<{{2}^{{m-2}}}-2 \end{split} \end{equation*}$

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

(78) $\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

(79) $\begin{equation*} \begin{split} \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{split} \end{equation*}$

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.

~n={{2}^{m}}\ldots n={{2}^{m}}+{{2}^{{m-1}}}-1

Es ergibt sich die folgende Darstellung:

(80) $\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

(81) $\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

(82) $\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

(83) $\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

(84) $\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$

(85) $\begin{equation*} \begin{split} \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{split} \end{equation*}$

Die Umkehrung der Palindromformel

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$ :

(86) $\begin{equation*} \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{equation*}$

Das kann man wegen $n~\bmod~2=n-2\left\lfloor\frac{n}{2}\right\rfloor$ für $p>2$ umformen zu

(87) $\begin{equation*} \begin{split} 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{split} \end{equation*}$

Zwei andere Schreibweisen ergeben sich mittels der Ersetzung $~n~\bmod~2=\frac{1}{2}\left( {1-{{{\left( {-1} \right)}}^{n}}} \right)$

(88) $\begin{equation*} \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{equation*}$

(89) $\begin{equation*} \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{equation*}$

Daraus folgt z.B., dass $p=1011951=11010010110100011_2$ das 2012-te binäre Palindrom ist.

Das größte binäre Palindrom zu einer vorgegebenen Zahl

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:

(90) $\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

Wie man sieht, gilt für die hier definierte Funktion $\text{F}$

(91) $\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.

(92) $\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$ .

Die Anzahl binärer Palindrome

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$ )

(93) $\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$ für $n\ge 1$ zu

(94) $\begin{equation*} \begin{split} {{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{split} \end{equation*}$

Die Summe binärer Palindrome

Die Summe der Palindrome zwischen $2^{n-1}$ und $2^n$ ergibt sich ferner für $n \ge 2$ zu

(95) $\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{equation*} \begin{split} \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 \end{split} \end{equation*}$

Mithin

(96) $\begin{equation*} \displaystyle {{S}_{2}}({{2}^{n}}) =\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{equation*}$

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$

(97) $\begin{equation*} \begin{split} \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{split} \end{equation*}$

wobei ${R_ {{m(p)}{k}}(p)}$ definiert ist als

(98) $\begin{equation*} \begin{split} {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{split} \end{equation*}$

sowie ${{s}_{m}}$ und ${{a}_{m}}$ folgendermaßen

(99) $\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

(100) $\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

(101) $\begin{equation*} \begin{split} {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{split} \end{equation*}$

und es ergibt sich schließlich die Summenformel

(102) $\begin{equation*} \begin{split} \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{split} \end{equation*}$

Will man die Summe der Palindrome bis zu einem bestimmten Index bestimmen, also

(103) $\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.

Palindrome mit beliebigen Basen

Wachstum der Folge von Palindromen zur Basis b

Palindrome zur Basis $b$ gehorchen für $n>1$ der Ungleichung

(104) $\begin{equation*} \frac{b}{(b+1)^2} \cdot n^2 < P_b(n) < \frac{1}{4} (n+1)^2 \end{equation*}$

Beim Grenzübergang $n \rightarrow \infty$ gilt

(105) $\begin{equation*} \liminf_{n \rightarrow \infty} \frac{P_b(n)}{n^2} = \frac{b}{(b+1)^2} \end{equation*}$

sowie

(106) $\begin{equation*} \limsup_{n \rightarrow \infty} \frac{P_b(n)}{n^2} = \frac{1}{4} \end{equation*}$

$n\ge 3\cdot {{2}^{{m-1}}}$	$p=0$
$n<3\cdot {{2}^{{m-1}}}$	$p=1$

$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$

Palindromische Zahlen

Einführung

Dezimale Palindrome

Bestimmung von dezimalen Palindromen

Die rekursive Berechnung

Die direkte Berechnung

Eine einfache Formel zur Bestimmung von dezimalen Palindromen

Die Umkehrung der Palindromformel

Die Anzahlfunktion für dezimale Palindromen

Das Wachstum der Folge dezimaler Palindrome

Dezimale Palindrome mit einer ungeraden Anzahl von Stellen

Die rekursive Bestimmung

Die direkte Bestimmung

Die Umkehrfunktion

Die Anzahlfunktion

Das Wachstum der Folge

Dezimale Palindrome mit einer geraden Anzahl von Stellen

Die rekursive Bestimmung

Die direkte Bestimmung

Die Umkehrfunktion

Die Anzahlfunktion

Das Wachstum der Folge

Der Zusammenhang zwischen der Folge der ungeraden, geraden und allgemeinen dezimalen Palindromen

Binäre Palindrome

Wachstum der Folge binärer Palindrome

Differenzen von binären Palindromen

Die Umkehrung der Palindromformel

Das größte binäre Palindrom zu einer vorgegebenen Zahl

Die Anzahl binärer Palindrome

Die Summe binärer Palindrome

Palindrome mit beliebigen Basen

Wachstum der Folge von Palindromen zur Basis b

Schreibe einen Kommentar Antwort abbrechen