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

2 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 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$ . Die weitergehende Analyse zeigt

(2) $\begin{equation*} \begin{array} {lll} P_{10}(10^q + 10^{q-1}) &= 10^{2q-1} + 1, &\text{für}\; q > 0 \\[8pt]P_{10}(10^q + 10^{q-1} - 1) &= 10^{2q-1} - 1, &\text{für}\; q > 0 \\[8pt] P_{10}((d+1) \cdot 10^q) &= d \cdot 10^{2q} +d, &\text{für}\; 0 < d \le 9, \, q \ge 0 \\[8pt] P_{10}((d+10) \cdot 10^{q-1}) &= d \cdot 10^{2q-1} + d, &\text{für}\; 0 < d \le 9, \, q > 0 \end{array} \end{equation*}$

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.

Nach der vorstehenden Tabelle gibt es einen direkten Zusammenhang zwischen bestimmten Wertebereichen von $n$ und der Stellenanzahl des zugeordneten dezimalen Palindroms. Diese Stellenanzahl ist von Bedeutung, weil sie den Charakter der Symmetrieeigenschaft des Palindroms unmittelbar beeinflusst. Bei einer ungeraden Anzahl von Ziffern liegt die Symmetrieachse genau auf der mittleren Ziffer, bei einer geraden Anzahl von Stellen dagegen zwischen den beiden mittleren Ziffern.

Die Anzahl der Ziffern des $n$ -ten Palindrom lässt sich aus der Anzahl der Stellen von $n$ und dem betreffenden Wertebereich bestimmen. Die Stellenanzahl des resultierenden Palindroms ist das Doppelte der Ziffernanzahl von $n$ minus $1$ , minus $2$ oder minus $3$ , je nachdem, in welchem Wertebereich $n$ liegt.

Die nachfolgend für $n>0$ definierten Hilfsfunktionen $\lambda(n)$ und $\overline{\lambda}(n)$ erlauben direkt die Bestimmung der gesuchten Stellenanzahl $L\left(P_{10}(n)\right)$ . Mit

(3) $\begin{equation*} \begin{split} \lambda(n) &:= \left\lfloor \log_{10}\left(\max\left(1,\frac{10}{11}\cdot n \right) \right) \right\rfloor \\[8pt] \overline{\lambda}(n) &:= \left\lfloor \log_{10}\left(\max\left(1,\frac{1}{2} \cdot n\right) \right) \right\rfloor \end{split} \end{equation*}$

ergibt sich

(4) $\begin{equation*} L\left(P_{10}(n)\right) = \begin{cases} 2 \cdot \lambda(n) +1, &\text{wenn} \; \lambda(n) = \overline{\lambda}(n) \\[8pt]2 \cdot \overline{\lambda}(n), &\text{sonst} \end{cases} \end{equation*}$

Da $\overline{\lambda}(n)$ entweder gleich $\lambda(n)$ oder um $1$ kleiner ist, wird die Stellenanzahl von $P_{10}(n)$ im Falle der Ungleichheit $\lambda(n) \ne \overline{\lambda}(n)$ auch durch die Summe $2 \cdot \overline{\lambda}(n) +2$ bestimmt. Man kann daher für die Stellenanzahl von $P_{10}(n)$ auch schreiben

(5) $\begin{equation*} L\left(P_{10}(n)\right) = \lambda(n) + \overline{\lambda}(n) + 1\end{equation*}$

Nach dem Vorstehenden ist somit die Stellenanzahl ungerade im ersteren Falle, wenn also $\lambda(n) = \overline{\lambda}(n)$ , andernfalls, wenn also $\lambda(n) \ne \overline{\lambda}(n)$ , ist sie gerade.

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

(6) $\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 weiteren Parameter $p$ und $m$ auf dieser Basis zu bestimmen. Wir formulieren daher die folgende Rekursionsbeziehung

(7) $\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,\, m,\, q$ und $p$ sind dabei folgendermaßen zu bestimmen:

(8) $\begin{align*} q &= \lambda(n) + \overline{\lambda}(n) \\[8pt]d &= \displaystyle \left(\left\lfloor \frac{n}{10^{ \left\lfloor\frac{q}{2}\right\rfloor}} \right\rfloor -1 + q \bmod 2 \right) \bmod 10 \end{align*}$

Wegen $q \bmod 2 = \lambda(n) - \overline{\lambda}(n)$ kann man dabei auch direkt auf die $\lambda$ -Funktionen zurückgreifen. Die weiteren Parameter $m$ und $p$ erhält man mittels des nachfolgend definierten Hilfsparameters $N$ .

(9) $\begin{equation*} \begin{split} N &= \displaystyle \left(d+1+ 9\cdot \left(q \bmod 2 \right) \right) \cdot 10^{ \left\lfloor\frac{q}{2}\right\rfloor} \\[8pt] m &= \begin{cases} 1, &\text{wenn} \; n = N \\[4pt] n - N + 10^{\displaystyle \left\lfloor\log_{10}\left(n-N\right) \right\rfloor + q \bmod 2}, &\text{sonst} \end{cases} \\[8pt]p &= \lambda(n) - \lambda(m) \end{split} \end{equation*}$

Die Stellenanzahl $L\left(P_{10}(n)\right)$ des Palindroms ist $q + 1$ . Demnach hat das gesuchte Palindrom eine ungerade Anzahl von Stellen, wenn $q$ gerade ist, und eine gerade Anzahl von Stellen, wenn $q$ ungerade ist.

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

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

Eingesetzt in die Rekursionsformel ergibt sich

(11) $\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 folgt:

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

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

(13) $\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 7\right) \\&= 10001 + 10\cdot 373 \\&= 10001 + 3730 \\&= 13731 \end{split} \end{equation*}$

2.2 Die direkte Berechnung

Für $n>10$ kann man das $n$ -te dezimale Palindrom auch auf direktem Wege berechnen. Dazu definieren wir $m := \lambda(n)$ und erinnern an $\lambda(n)= \left\lfloor \log_{10}\left(\max\left(1,\frac{10}{11} \cdot n \right) \right) \right\rfloor$ , sowie $\overline{\lambda}(n)= \left\lfloor \log_{10}\left(\max\left(1,\frac{1}{2} \cdot n \right) \right) \right\rfloor$ . Wir unterscheiden zwei Fälle.

Fall 1: $\lambda(n) = \overline{\lambda}(n)$

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

Fall 2: $\lambda(n) \ne \overline{\lambda}(n)$

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

Beispiel 1: $n = 237$ . Wie man leicht errechnet. ergibt sich $\lambda(237) = 2 = \overline{\lambda}(237)$ . Es gilt daher $m = 2$ . Nach der Fallunterscheidung trifft der erstgenannte Fall zu. Für den Summenausdruck mit dem einzigen Term $k=1$ bekommen wir $\left(\left\lfloor \frac{237}{10^{2-1}}\right\rfloor \bmod 10\right) \cdot 10^1 = 30$ . Die Summanden außerhalb sind $(237 - 10^2) \cdot 10^2 = 13700$ und $\left\lfloor \frac{237}{10^{2}}\right\rfloor - 1 = 1$ . Das ergibt $P_{10}(237) = 30 + 13700 + 1= 13731$ .

Beispiel 2: Wir haben $\lambda(082) = 2 = \overline{\lambda}(1082)$ . Wieder ist $m = 2$ , somit trifft erneut der erstgenannte Fall zu. Der einzige Term des Summenausdrucks mit dem Index-Term $k=1$ ist $\left(\left\lfloor \frac{1082}{10^{2-1}}\right\rfloor \bmod 10\right) \cdot 10^1 = 80$ . Die Terme ausßerhalb der Summe sind $(1082 - 10^2) \cdot 10^2 = 98200$ und $\left\lfloor \frac{1082}{10^{2}}\right\rfloor - 1 = 9$ . Das ergibt $P_{10}(1082) = 80 + 98200 + 9= 98289$ .

Beispiel 3: Nun haben wir $\lambda(1546) = 3 \ne 2 = \overline{\lambda}(1546)$ , das ist der zweite Fall mit $m = 3$ . Der finale Summenausdruck mit den beiden Index-Termen für $k=1$ und $k=2$ ergibt $\left(\left\lfloor \frac{1546}{10^{3-1}}\right\rfloor \bmod 10\right) \cdot 10^0$ sowie
$\left(\left\lfloor \frac{1546}{10^{3-2}}\right\rfloor \bmod 10\right) \cdot 10^1$ mit der Summe $45$ . Die Summanden außerhalb sind $(1546- 10^3) \cdot 10^3 = 546000$ und $\left(1546 \bmod 10 \right) \cdot 10^{3-1} = 600$ . Zusammen resultiert das in $P_{10}(1546) = 45 + 546000 + 600 = 546654$ .

2.3 Ein einfacher Algorithmus 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 die Ziffernfolge des $n$ -ten Palindroms $P_{10}(n)$ nach folgender einfacher Berechnungsvorschrift:

(16) $\begin{equation*} P_{10}(n) \Leftrightarrow \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 > 1 \\[4pt]\large \left[ \, 9\; d_3 \cdots d_k \cdots d_3\; 9 \, \right], & \text{falls}\; d_1 = 1 \; \text{und} \; d_2 = 0 \\[4pt]\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$ .

2.4 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 bekommt die Ziffernfolge von $n$ nach folgender Fallunterscheidung in sinngemäßer Umkehrung der Direktformel:

(17) $\begin{equation*} n = P_{10}^{-1}(p) \Leftrightarrow \begin{cases} \Large \left[\, p_1+1\; p_2\; p_3 \cdots p_k \,\right], &\text{falls}\; L(P) \bmod 2 = 1 \; \text{und}\; 0< p_1 < 9 \\[4pt]\Large \left[ \,1 \; 0 \; p_2 \;p_3 \cdots p_k \, \right], &\text{falls}\; L(P) \bmod 2 = 1 \; \text{und}\; p_1 = 9 \\[4pt] \Large \left[ \,1 \; p_1 \; p_2 \; p_3 \cdots p_k \, \right], &\text{falls}\; L(P) \bmod 2 = 0 \end{cases} \end{equation*}$

Für die formale algorithmische Berechnung definieren wir $m = \left\lfloor \log_{10}(P)\right\rfloor$ und orientieren wir uns an den vorgenannten drei Fällen. Wenn $\;\displaystyle m \bmod 2 = 0$ , das sind die beiden obigen Fälle mit $L(P) \bmod 2 = 1$ , dann haben wir

(18) $\begin{equation*} \begin{split} n = P_{10}^{-1}(P) &=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} \\[8pt]&= \left\lfloor \frac{P}{10^{\frac{m}{2}}}\right\rfloor + 10^{\frac{m}{2}} \end{split} \end{equation*}$

Wie man sich leicht klar macht, muss man den Fall $P \bmod 10 = 9$ nicht separieren, weil sich der Summationsterm für den Index $k = 0$ , nämlich $9 \cdot 10^{\frac{m}{2}}$ , mit dem Term vor der Summe zu $10^{\frac{m}{2}+1}$ ergänzt, so dass $n$ korrekterweise mit der Ziffernfolge $10 \dots$ beginnt. Für den obigen dritten Fall $\; \displaystyle L(P) \bmod 2 = 0$ , der gleichbedeutend ist mit $\;\;\displaystyle m \bmod 2 = 1$ , erhalten wir

(19) $\begin{equation*} \begin{split} n = P_{10}^{-1}(P) &= 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} \\[8pt]&= \left\lfloor \frac{P}{10^{\frac{m+1}{2}}}\right\rfloor + 10^{\frac{m+1}{2}} \end{split} \end{equation*}$

Zusammen können wir dies in kompakter Form für alle $P>0$ und ohne Fallunterscheidung folgendermaßen schreiben:

(20) $\begin{equation*} n = P_{10}^{-1}(P) = \left\lfloor \frac{ P}{ 10^{\left\lfloor \frac{m+1}{2} \right\rfloor}} \right\rfloor + 10^{ \left\lfloor \frac{m+1}{2} \right\rfloor} \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$ .

2.5 Die Anzahlfunktion für dezimale Palindrome

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

(21) $\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$ , ergibt sich daher nach Aufaddieren vorgenannter Partialsummen

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

2.6 Das Wachstum der Folge dezimaler Palindrome

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

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

Die folgenden Abbildungen zeigen, wie die Folge der dezimalen Palindrome mit $n$ wächst und wie die Folgenglieder durch die Ungleichung begrenzt werden (exemplarisch für $n = 1 \dots 500$ bzw. $n = 1 \dots 2000$ ).

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

(24) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10}(n)}{n^2} &= \frac{10}{121} \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10}(n)}{n^2} &= \frac{1}{4} \end{split} \end{equation*}$

Der Kurvenverlauf $\displaystyle \frac{P_{10}(n)}{n^2}$ mit Bezug auf die Referenzkurve $n^2$ ist für $n = 1 \dots 5000$ im nachfolgenden Diagramm mit den beiden Häufungspunkten bei $\limsup = \frac{1}{4}$ und $\liminf = \frac{10}{121}$ dargestellt. Im Unterschied zu oben ist die x-Achse hier logarithmisch skaliert.

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

(25) $\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*}$

Wir benennen die Palindrome mit dem Formelzeichen $P_{10\vert U}(n)$ .

Die ungeraden Palindrome mit der Nummer $n = 10^q$ lauten daher $P_{10\vert U}(n) = 10^{2q-1} - 1$ . Für $n = 10^q + 1$ gilt dagegen $P_{10\vert U}(n) = 10^{2q} + 1$ . Die weitere Analyse ergibt die folgenden Beziehungen:

(26) $\begin{equation*} \begin{array} {lll} P_{10\vert U}\left(d \cdot 10^q \right) &= (d-1) \cdot 10^{2q} + 9 \cdot 10^q + d - 1,\; &\text{für}\; 2 \le d \le 10 \\[8pt] P_{10\vert U}\left(d \cdot 10^q + 1\right) &= d \cdot 10^{2q} + d,\; &\text{für}\; 1 \le d \le 9 \\[8pt] P_{10\vert U}\left(d \cdot 10^q + j\right) &= d \cdot 10^{2q} + (j-1) \cdot 10^q+ d,\; &\text{für}\; 1 \le d \le 9, \; 1 \le j \le 10 \end{array} \end{equation*}$

3.1 Die rekursive Bestimmung

Man kann diese Palindrome ebenfalls rekursiv bestimmen. Der Algorithmus ist sogar einfacher als im allgemeinen Falle.

(27) $\begin{equation*} P_{10\vert U}(n) = d \cdot \left(10^q + 1\right) + 10^p \cdot P_{10\vert 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:

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

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

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

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

3.2 Die direkte Bestimmung

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

(31) $\begin{equation*} \begin{split} P_{10\vert U}(n) &= \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) \;+ \\[4pt] & \quad \left((n-1) \bmod 10\right)\cdot 10^m \\[8pt]&= \sum \limits_{k=1}^{m-1} \left(\left\lfloor \frac{n-1}{10^{m-k}}\right\rfloor \bmod 10\right) \cdot 10^k \;+ \\[4pt] & \quad \left( n-1 \right) \cdot 10^m + \left\lfloor \frac{n-1}{10^{m}}\right\rfloor \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\vert U}(n)$ aus der Ziffernfolge von $n - 1$ nach der folgenden einfachen Vorschrift:

(32) $\begin{equation*} \LARGE P_{10\vert 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\vert U}(n)$ zu $\left[ \,1 \; 3 \; 9 \; 3 \; 1 \, \right]$ , also $P_{10\vert U}(140) = 13931$ . Entsprechend ergibt sich die Summe in der Bestimmungsformel (31) zu $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$ und somit P_{10\vert U}(140) = 13900 + 30 + 1 = 13931\).

3.3 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

(33) $\begin{equation*} n = P_{10\vert U}^{-1}(P) = 1 + \left\lfloor \frac {P}{10^{ \frac{m}{2}}} \right \rfloor \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.

3.4 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

(34) $\begin{equation*} \begin{split} A_{10\vert U}(n)\left(10^{n}\right) - A_{10\vert U}(n)\left(10^{n-1}\right) &= \begin{cases} 0, &\text{falls} \; n \bmod 2 = 0 \\[4pt] \displaystyle 9\cdot 10^{\frac{n-1}{2}}, &\text{sonst} \end{cases} \\[8pt] &= \displaystyle 10^{ \left\lfloor\frac{n+1}{2}\right\rfloor} - 10^{ \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

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

3.5 Das Wachstum der Folge

Für $n>1$ gilt die Ungleichung

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

Den folgenden exemplarischen Abbildungen kann man für $n = 1 \dots 1000$ bzw. $n = 1 \dots 2000$ entnehmen, wie die Folge der dezimalen Palindrome mit einer ungeraden Anzahl von Stellen mit $n$ wächst und wie die Folgenglieder durch die Ungleichung begrenzt werden.

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

(37) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert U}(n)}{n^2} &= \frac{1}{10} \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert U}(n)}{n^2} &= 1 \end{split} \end{equation*}$

Zur Kurve des Quotienten $\displaystyle \frac{P_{10\vert U}(n)}{n^2}$ für Werte $n = 1 \dots 5000$ , s. das nachfolgende Diagramm (mit logarithmischer Skalierung der x-Achse) und den beiden Häufungspunkten $\limsup = 1$ und $\liminf = \frac{1}{10}$ .

4 Dezimale Palindrome mit einer geraden Anzahl von Stellen

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

(38) $\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*}$

Wir benennen diese Palindrome mit dem Formelzeichen $P_{10\vert G}(n)$ .

$\Large \boldsymbol {n}$	$\Large \boldsymbol {P_{10\vert G}(n)}$
$1 \cdots 9$	$11 \cdots 99$
$10 \cdots 99$	$1001 \cdots 9999$
$100\cdots 999$	$100001 \cdots 999999$
$1000 \cdots 9999$	$10000001 \cdots 99999999$
$10000 \cdots 99999$	$1000000001 \cdots 9999999999$

Die solchermaßen definierten Palindrome mit der Nummer $n = 10^q$ lauten daher $P_{10\vert G}(n) = 10^{2q+1} + 1$ . Für $n = 10^q - 1$ gilt dagegen $P_{10\vert G}(n) = 10^{2q} - 1$ . Die weitere Betrachtung zeigt:

(39) $\begin{equation*} \begin{array} {lll} P_{10\vert G}\left(d \cdot 10^q -1 \right) &= (d-1) \cdot 10^{2q+1} + 99\cdot 10^q + d - 1,\; &\text{für}\; 2 \le d \le 10 \\[8pt] P_{10\vert G}\left(d \cdot 10^q \right) &= d \cdot 10^{2q+1} + d,\; &\text{für}\; 1 \le d \le 9 \\[8pt] P_{10\vert G}\left(d \cdot 10^q + j\right) &= d \cdot 10^{2q+1} + 11 j \cdot 10^q+ d,\; &\text{für}\; 1 \le d \le 9, \; 1 \le j \le 9 \end{array} \end{equation*}$

4.1 Die rekursive Berechnung

Ähnlich wie oben kann man auch die Palindrome mit einer geraden Anzahl von Stellen mittels einer Rekursionsbeziehung ableiten.

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

Zusätzlich definieren wir $P_{10\vert G}(n) := 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:

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

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

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

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

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

(44) $\begin{equation*} \begin{split} P_{10\vert 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) \\[8pt]&= \sum \limits_{k=0}^{m-1} \left(\left\lfloor \frac{n}{10^{m-k}}\right\rfloor \bmod 10\right) \cdot 10^k \; + \\[4pt] & \quad \; n \cdot 10^{m+1} + \left(n \bmod 10 \right) \cdot 10^m \end{split} \end{equation*}$

Die anschauliche Ableitung für die Berechnung des $n$ -ten Palindroms mit einer geraden Anzahl von Stellen verläuft ä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. Das $n$ -te Palindrom $P_{10\vert G}(n)$ bestimmt man aus der Ziffernfolge von $n$ nach folgender simplen Vorschrift:

(45) $\begin{equation*} \LARGE P_{10\vert 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\vert G}(n)$ zu $\left[ \,1 \; 3 \; 9 \; 9 \; 3 \; 1 \, \right]$ , also $P_{10\vert G}(139) = 139931$ . Entsprechend erhalten wir auf Basis der Direktformel mit $m = 2$ die beiden Terme des Summenausdrucks zu $\left(\left\lfloor \frac{139}{10^{2-1}}\right\rfloor \bmod 10\right) \cdot 10^1 = 30$ und $\left\lfloor \frac{139}{10^{2}} \right\rfloor = 1$ . Zusammen mit den äußeren Summanden ergibt sich $P_{10\vert G}(139) = 30 + 1 + 139 \cdot 10^{2+1} + \left(139 \bmod 10 \right) \cdot 10^2 = 139931$ .

4.3 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

(46) $\begin{equation*} n = P_{10\vert G}^{-1}(P) = \left\lfloor \frac {P}{10^{ \frac{m+1}{2}}} \right \rfloor\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.

4.4 Die Anzahlfunktion

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

(47) $\begin{equation*} \begin{split} A_{10\vert G}\left(10^{n}\right) - A_{10\vert G})\left(10^{n-1}\right) &= \begin{cases} \displaystyle 9\cdot 10^{\frac{n-2}{2}}, &\text{falls} \; n \bmod 2 = 0 \\[4pt] 0, &\text{sonst} \end{cases} \\[8pt] &= \displaystyle 10^{ \left\lfloor\frac{n}{2}\right\rfloor} - 10^{ \left\lfloor\frac{n-1}{2}\right\rfloor} \end{split} \end{equation*}$

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

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

4.5 Das Wachstum der Folge

Für $n>1$ gilt die Ungleichung

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

Den beiden nachfolgenden Abbildungen kann man für $n = 1 \dots 1000$ bzw. $n = 1 \dots 2000$ entnehmen, wie die Folge der dezimalen Palindrome mit einer geraden Anzahl von Stellen mit $n$ wächst und wie die Folgenglieder durch die Ungleichung begrenzt werden.

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

(50) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert G}(n)}{n^2} &= 1 \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert G}(n)}{n^2} &= 10 \end{split} \end{equation*}$

Der Kurvenverlauf der Folge $\displaystyle \frac{P_{10\vert G}(n)}{n^2}$ ist im nachfolgenden Diagramm mit den beiden Häufungspunkten $\limsup = 10$ und $\liminf =1$ beispielhaft für $n = 1 \dots 5000$ in logarithmischer Skalierung dargestellt.

5 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$ ? Da ein dezimales Palindrom genau dann gerade ist, wenn $\lambda(n) = \overline{\lambda}(n)$ , können wir die Zuordnung einfach auf Basis dieser Fallunterscheidung treffen, wobei $\lambda(n)= \left\lfloor \log_{10}\left(\max\left(1,\frac{10}{11} \cdot n \right) \right) \right\rfloor$ und $\overline{\lambda}(n)= \left\lfloor \log_{10}\left(\max\left(1,\frac{1}{2} \cdot n \right) \right) \right\rfloor$ .

(51) $\begin{equation*} P_{10}(n) = \begin{cases} P_{10\vert U})\left(n + 1 - 10^{\lambda(n)}\right), &\text{wenn} \; \lambda(n) = \overline{\lambda}(n) \\[8pt]P_{10\vert G}\left(n - 10^{\lambda(n)}\right), &\text{sonst} \end{cases} \end{equation*}$

In der anderen Richtung ergeben sich die beiden Beziehungen

(52) $\begin{align*} P_{10\vert U}(n)) &= P_{10}\left(n - 1 + 10^{\displaystyle \left \lfloor \log_{10}(\max(1,n-1))\right \rfloor} \right) \\[8pt]P_{10\vert G}(n) &= P_{10}\left(n + 10^{\displaystyle \left \lfloor \log_{10}(n)\right \rfloor + 1} \right) \end{align*}$

Interessant sind noch eine Reihe von Grenzwerten, die die zwar ähnlichen, aber doch unterschiedlichen Verläufe der Folgen $P_{10}(n)$ , $P_{10\vert U}(n)$ und $P_{10\vert G}(n)$ mit ihren definierten Sprüngen deutlich machen. Es gilt

(53) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert U}(n)}{P_{10}(n)} &= \frac{10}{9} \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert U}(n)}{P_{10}(n)} &= \frac{100}{9} \end{split} \end{equation*}$

(54) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert G}(n)}{P_{10}(n)} &= \frac{100}{9} \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert G}(n)}{P_{10}(n)} &= \frac{1000}{9} \end{split} \end{equation*}$

Die beiden Grafiken zeigen exemplarisch die Kurvenverläufe der Quotientenfolgen $\displaystyle \frac{P_{10\vert U}(n)}{P_{10}(n)}$ und $\displaystyle \frac{P_{10\vert G}(n)}{P_{10}(n)}$ bis $n =5000$ . Die jeweiligen unteren und oberen Grenzwerte (Häufungspunkte $\liminf$ und $\limsup$ ) können ebenfalls entnommen werden.

Wenn $n$ eine Zehnerpotenz $+1$ ist, dann macht die Folge der Palindrome $P_{10\vert U}(n)$ einen Sprung. Die Höhe des Sprungs entnimmt man den beiden folgenden Grenzwerten.

(55) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert U}(n+1)}{P_{10\vert U}(n)} &= 1 \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert U}(n+1)}{P_{10\vert U}(n)} &= 10 \end{split} \end{equation*}$

Ähnlich macht auch die Folge der Palindrome $P_{10\vert G}(n)$ einen Sprung, allerdings schon einen Term vorher, also genau bei der Zehnerpotenz.

(56) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert G}(n+1)}{P_{10\vert G}(n)} &= 1 \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert G}(n+1)}{P_{10\vert G}(n)} &= 10 \end{split} \end{equation*}$

Die genannten Sprünge der beiden Quotientenfolgen $\displaystyle \frac{P_{10\vert U}(n+1)}{P_{10\vert U}(n)}$ und $\displaystyle \frac{P_{10\vert G}(n+1)}{P_{10\vert G}(n)}$ werden in den untenstehenden Diagrammen für $n = 1 \dots 5000$ anschaulich gemacht. Die Ausreißer nach oben häufen sich bei $\limsup = 10$ . Nach unten bildet sich jeweils ein Häufungspunkt bei $\liminf = 1$ .

Beim Vergleich der Palindrome mit einer ungeraden Anzahl von Stellen $P_{10\vert U}(n)$ mit den Palindromen $P_{10\vert G}(n)$ fällt auf, dass Letztere offenbar schneller wachsen als Erstere.

(57) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_{10\vert G}(n)}{P_{10\vert U}(n)} &= 10 \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_{10\vert G}(n)}{P_{10\vert U}(n)} &= 100 \end{split} \end{equation*}$

Tatsächlich ist $P_{10\vert G}(n)$ asymptotisch 10-mal größer als $P_{10\vert U}(n+1)$ . Im Gegensatz zu den oben betrachteten Fällen, wo die Quotienten stets in einem weiten Bereich von etwa 1:10 oder 10:100 schwanken oder sich sprunghaft ändern, ist die Folge der Quotienten $\displaystyle \frac{P_{10\vert G}(n)}{P_{10\vert U}(n+1)}$ konvergent mit dem Grenzwert $10$ . Dies erkennt man auf Basis der folgenden Überlegung:

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

woraus folgt

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

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

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

Das nachfolgend dargestellte Diagramm zeigt bespielhaft den Konvergenzverlauf der Folge $\displaystyle \frac{P_{10\vert G}(n)}{P_{10\vert U}(n+1)}$ in Kontrast zur Divergenz von $\displaystyle\frac{P_{10\vert G}(n)}{P_{10\vert U}(n)}$ für Werte $n = 1 \dots 5000$ . Der Grenzwert (Grafik Konvergenz: $\lim = 10$ ) sowie der obere und untere Häufungspunkt (Grafik Ausreißer: $\limsup = 100$ und $\liminf = 10$ ) sind eingetragen.

6 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
29	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

(61) $\begin{equation*} \begin{array}{lcl} P_2 (2^m - 1) &=&2^{2m-2}-1 \\[4pt] P_2 (2^m) &=&2^{2m-2}+1 \\[4pt] P_2 ( 2^m+1) &=&2^{2m-2}+2^{m-1}+1 \\[4pt]P_2( 5\cdot 2^{m-2}-1) &=&2^{2m-2}+2^{m-3}-3 \\[4pt] P_2 ( 5\cdot 2^{m-2}) &=&2^{2m-2}+2^{m-3}+3 \\[4pt]P_2 ( 6\cdot 2^{m-2}-1 ) &=&2^{2m-1}-1 \\[4pt] P_2 ( 6\cdot 2^{m-2} ) &=&2^{2m-1}+1 \\[4pt] P_2( 6\cdot 2^{m-2}+1 ) &=&2^{2m-1}+2^{m}+2^{m-1}+1 \\[4pt]P_2 ( 7\cdot 2^{m-2}-1 ) &=&2^{2m-1}+2^{m-2}-3 \\[4pt]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$ .

6.1 Rekursive Berechnung

Für die allgemeine Bestimmung kann man eine rekursive Berechnungsmethode anwenden:

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

6.2 Direkte Berechnung

Eine Möglichkeit zur direkten Bestimmung des $n$ -ten binären Palindroms ist die Folgende (für $n\ge 3$ ):

(63) $\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}} \\[4pt]&+\,\sum \limits_{{k=1}}^{m-1-p} {\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)} \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$

Hierzu noch einige Bitmuster:

$\Large \boldsymbol {n}$	$\Large \boldsymbol {P_2(n)}$ – binär –	$\Large \boldsymbol {P_2(n)}$ – dezimal –
50	1001001001	585
100	100100001001	2313
200	10010000001001	9225
300	101011000110101	22069
400	1001000000001001	36873
500	1111010000101111	62511
600	10101100000110101	88117
700	11011110001111011	113787
800	100100000000001001	147465
900	110000100001000011	198723
1000	111101000000101111	249903
1500	1111011100011101111	506095
2000	11110100000000101111	999471
5000	10111000100000100011101	6045981
10000	1011100010000000100011101	24183069
100000	10000110101000000000010101100001	2258634081

6.3 Wachstum der Folge binärer Palindrome

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

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

Den folgenden Diagrammen kann man für $n = 1 \dots 50$ bzw. $n = \dots 1000$ beispielhaft 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

(65) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_2(n)}{n^2} = \frac{2}{9} \\[8pt] \limsup_{n \rightarrow \infty} \frac{P_2(n)}{n^2} = \frac{1}{4} \end{split} \end{equation*}$

Der Kurvenverlauf der Folge $\displaystyle \frac{P_2(n)}{n^2}$ ist im nachfolgenden Diagramm für $n= 1 \dots 1000$ exemplarisch dargestellt. Der obere und der untere Häufungspunkt, $\limsup = \frac{1}{4}$ und $\liminf = \frac{2}{9}$ , sind entsprechend eingetragen.

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

(66) $\begin{equation*} \begin{split} \Delta {{P}_{2}}\left( {4\cdot {{2}^{m}}-1} \right)&=2 \\[4pt] \Delta {{P}_{2}}\left( {6\cdot {{2}^{m}}-1} \right)&=2 \\[4pt] \Delta {{P}_{2}}\left( {7\cdot {{2}^{m}}-1} \right)&=6 \\[4pt] \Delta {{P}_{2}}\left( {5\cdot {{2}^{m}}-1} \right)&=6,\; \text{für}\; m \ge 1\end{split} \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

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

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

(69) $\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 \\[4pt] 6, &n&=&2^{m}+2^{m-2}-1 \\[4pt] \Delta P_2 (n-2^{m-2}) \text{,} &2^{m}+2^{m-2}\le n&<&2^{m}+2^{m-1}-1 \\[4pt] 2, &n&=&2^m+2^{m-1}-1 \\[4pt] ( 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.

(70) $\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}}} \\[4pt] \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 \\[4pt] \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

(71) $\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 für $0\le k\le {{2}^{{m-1}}}$

(72) $\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) \\[4pt] &=\left( {2-{{{\left( {-1} \right)}}^{k}}} \right)\cdot \Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}-k} \right) \\[4pt] &=\Delta {{P}_{2}}\left( {{{2}^{m}}-1+{{2}^{{m-1}}}+{{2}^{{m-1}}}-k} \right) \\[4pt] &=\Delta {{P}_{2}}\left( {{{2}^{{m+1}}}-1-k} \right) \end{split} \end{equation*}$

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:

(73) $\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 \\[4pt] 2^{m-1}\text{,} &n=2^{m}+2k\text{, } &0\le k<2^{m-2} \\[4pt] 3\cdot 2^{m-2}\text{,} &n=2^{m}-1+(2k+1)2^1\text{, } &0\le k<2^{m-2} \\[4pt] 3\cdot 2^{m-3}\text{,} &n=2^{m}-1+(2k+1)2^2\text{, } &0\le k<2^{m-3} \\[4pt] 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} \\[4pt] 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

(74) $\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 \\[4pt] 2^{m-1}\text{,} &n=2^{m}+2k\text{, } &0\le k<2^{m-2} \\[4pt] 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 \\[4pt] 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

(75) $\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\} \\[4pt] 2^{m-1}\text{,} &n\equiv 0 {\pmod 2} \land n<3\cdot 2^{m-1} \\[4pt] 3\cdot 2^{m-1}\text{,} &n\equiv 0 {\pmod 2} \land n \ge 3\cdot 2^{m-1} \\[4pt] \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

(76) $\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\} \\[4pt] \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*}$

6.5 Alternative Formel für die direkte Berechnung

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

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

(78) $\begin{equation*} \begin{split} \displaystyle {P_2} (n) = &\,2^{2m-2}+1+2\left\lfloor {\frac{{n-{{2}^{m}}}}{{{{2}^{{m-1}}}}}} \right\rfloor \\[4pt] & \,+{{2}^{{m-1}}}\left\lfloor {\frac{1}{2}\min \left( {n+1-{{2}^{m}}{{{,2}}^{{m-1}}}+1} \right)} \right\rfloor \\[4pt] & \,+3\cdot {{2}^{{m-1}}}\left\lfloor {\frac{1}{2}\max \left( {n+1-3\cdot {{2}^{{m-1}}},0} \right)} \right\rfloor \\[4pt] & \,+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*}$

6.6 Ein anschauliches Verfahren zur Bestimmung binärer Palindrome

In Anlehnung an das Vorgehen bezüglicher dezimaler Palindrome ergibt sich auch hier eine anschauliche Möglichkeit zur Bestimmung des einem Index $n$ zugeordneten binären Palindroms. Sei $\left[ \, d_1\; d_2\; d_3 \cdots d_k \, \right]$ das Bitmuster von $n$ mit $k$ Stellen und $\left[ \, p_1\; p_2\; p_3 \cdots p_m \, \right]$ die resultierende Bitfolge des entsprechenden Palindroms $p$ mit einer unbekannten Anzahl von $m$ Stellen. Man erhält das $n$ -te binäre Palindrom $P_{2}(n)$ aus dem Bitmuster von $n$ nach folgender einfacher Berechnungsvorschrift:

(79) $\begin{equation*} P_{2}(n) \Leftrightarrow \begin{cases} \large \left[\,1 \; d_3\; d_4 \cdots d_k \cdots d_4\; d_3\; 1 \,\right], & \text{wenn}\; d_2 = 0 \\[8pt]\large \left[\,1 \; d_3 \; d_4 \cdots d_k\; d_k \cdots d_4\; d_3 \; 1 \, \right], & \text{sonst} \end{cases} \end{equation*}$

Im ersteren Falle der Unterscheidung ist $P$ ein binäres Palindrom mit einer ungeraden Anzahl von Stellen und es ergibt sich $m = 2k - 3$ , im zweiten Falle hat das Palindrom eine gerade Anzahl von Stellen und es gilt $m = 2k - 2$ .

Beispiel 1: $n = 21_{10} = 10101_{2}$ . Es trifft der erste Fall zu mit $d_3 = 1$ , $d_4 = 0$ , $d_5 = 1$ und $k = 5$ . Wir erhalten das Bitmuster von $P_2(21)$ zu ${[\,1 \, d_3 \, d_4 \, d_5 \, d_4 \, d_3 \, 1 \,]}$ , also $P_2(21) = 1101011_2 = 107_{10}$ , und es gilt $m = 7$ .

Beispiel 2: $n = 28_{10} = 11100_{2}$ . Es trifft der zweite Fall zu mit $d_3 = 1$ , $d_4 = 0$ , $d_5 = 0$ und $k = 5$ . Wir erhalten das Bitmuster von $P_2(28)$ zu ${[\,1 \, d_3 \, d_4 \, d_5 \, d_5 \, d_4 \, d_3 \, 1\,]}$ , also $P_2(28) = 11000011_2 = 195_{10}$ , und es gilt $m = 8$ .

6.7 Die Umkehrung der binären Palindromformel

Ist $p$ ein vorgegebenes binäres Palindrom, so stellt sich die Frage, das Wievielte in der geordneten Folge der Palindrome es ist. Die Antwort darauf gibt dieser Abschnitt. Für $p\ge 1$ gilt mit $m=\lfloor {\log}_{2}\left( p \right) \rfloor$ :

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

(81) $\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}}}}} \\[4pt] &\,+\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)$

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

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

Die obige Umkehrungsformel (80) funktioniert, weil der entsprechende Indexparameter $n$ im Bitmuster des resultierenden binären Palindroms enthalten ist. Das hatten wir auch schon bei der Darstellung der anschaulichen Berechnungsvorschrift zur Bestimmung binärer Palindrome gesehen (s. Abschnitt 6.6). Ausgehend davon erkennt man bei genauer Auswertung, dass sich die Umkehrungsformel mit dem komplexen Summenausdruck deutlich vereinfachen lässt. Tatsächlich erhalten wir

(84) $\begin{equation*} n = P_{2}^{-1}(p) = \left\lfloor \frac{ p}{ 2^{\left\lfloor \frac{m+1}{2} \right\rfloor}} \right\rfloor + 2^{ \left\lfloor \frac{m+1}{2} \right\rfloor} \end{equation*}$

Daraus folgt z.B., dass $p = 952599_{10} = 11101000100100010111_{2}$ das 1954-ste binäre Palindrom ist.

6.8 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 in Verbindung mit der Tabelle:

(85) $\begin{align*} \displaystyle \text{floorbP}_2(n) =\left\{ {\begin{array}{{ll}} \text{F}\left( {p,m} \right)\text{, } &\text{wenn } \text{F}\left( {p,m} \right)\le n \\[4pt] \text{F}\left( {p-{{2}^{q}},s} \right) \text{, } &\text{sonst} \end{array}} \right. \end{align*}$

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

(86) $\begin{equation*} \begin{split} \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}} \\[4pt]\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{split} \end{equation*}$

Dabei steht $\displaystyle \text{Reversal} \left( {x} \right)$ für die Umkehrung des Bitmusters von $x$ .

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

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

(88) $\begin{equation*} \begin{split} {{A}_{2}}({{2}^{n}})&=\sum\limits_{{0\le {{P}_{2}}(k)<{{2}^{n}}}}{1} \\[8pt]&=\left\{ \begin{array}{ll} {2\cdot 2^{\frac{n}{2}}-1} \text{, } &n\equiv 0 {\pmod 2} \\[4pt] {3\cdot 2^{\frac{n-1}{2}}-1} \text{, } &n\equiv 1 {\pmod 2} \end{array} \right. \\[8pt] &=\dfrac{{5-{{{\left( {-1} \right)}}^{n}}}}{2}\cdot {{2}^{{\left\lfloor {\frac{n}{2}} \right\rfloor }}}-1 \end{split} \end{equation*}$

6.10 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

(89) $\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)}} \\[8pt] &=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} \\[4pt] 15\cdot \dfrac{8^{\frac{n-1}{2}}-1}{7} \text{, } &n\equiv 1 {\pmod 2} \end{array} \right. \\[8pt]&=\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} \\[4pt] \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

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

(91) $\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\, \\[4pt] &\,+{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

(92) $\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}}}} \\[4pt] &\, +\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

(93) $\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 }}} \\[4pt] {{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

(94) $\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}}} \\[4pt] &\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

(95) $\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}}} \\[4pt] &\,+{{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

(96) $\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) \\[4pt]&\,+\left( {\left\lfloor {p\cdot {{2}^{{-\left\lfloor {\frac{m}{2}} \right\rfloor }}}} \right\rfloor \bmod 2} \right)\cdot p+{{2}^{m}}+1 \\[4pt]&\,+\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

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

7 Palindrome mit beliebigen Basen

Palindrome in beliebigen Basen $b > 1$ können ähnlich wie die diskutierten Fälle von dezimalen, Basis $b = 10$ , und binären, Basis $b = 2$ , Palindromen behandelt werden. Wir präsentieren die betreffenden Formeln ohne auf die nähere Ableitung einzugehen.

Es gelten die Zusammenhänge

(98) $\begin{equation*} \begin{array} {lll} P_{b}(2 \cdot b^q - 1) &= b^{2q} - 1, &\text{für}\; q \ge 0 \\[8pt] P_{b}(2 \cdot b^q) &= b^{2q} + 1, &\text{für}\; q > 0 \\[8pt]P_{b}(b^q + b^{q-1}) &= b^{2q-1} + 1, &\text{für}\; q > 0 \\[8pt]P_{b}(b^q + b^{q-1} - 1) &= b^{2q-1} - 1, &\text{für}\; q > 0 \\[8pt]P_{b}((d+1) \cdot b^q) &= d \cdot b^{2q} +d, &\text{für}\; 0 < d < b, \, q \ge 0 \\[8pt] P_{b}((d+b) \cdot b^{q-1}) &= d \cdot b^{2q-1} + d, &\text{für}\; 0 < d < b, \, q > 0 \end{array} \end{equation*}$

Es gibt einen direkten Zusammenhang zwischen bestimmten Wertebereichen von $n$ und der Stellenanzahl des zugeordneten Basis- $b$ -Palindroms. Diese Stellenanzahl ist von Bedeutung, weil sie den Charakter der Symmetrieeigenschaft des Palindroms unmittelbar beeinflusst. Bei einer ungeraden Anzahl von Ziffern liegt die Symmetrieachse genau auf der mittleren Ziffer, bei einer geraden Anzahl von Stellen dagegen zwischen den beiden mittleren Ziffern.

Grundsätzlich lässt sich die Anzahl der Ziffern des $n$ -ten Basis- $b$ -Palindroms aus der Anzahl der Stellen von $n$ – geschrieben als Basis- $b$ -Zahl – und dem betreffenden Wertebereich bestimmen.

Die nachfolgend für $n>0$ definierten Hilfsfunktionen $\lambda_{b}(n)$ und $\overline{\lambda_{b}}(n)$ erlauben direkt die Bestimmung der gesuchten Stellenanzahl $L\left(P_{b}(n)\right)$ . Mit

(99) $\begin{equation*} \begin{split} \lambda_{b}(n) &:= \left\lfloor \log_{b}\left(\max\left(1,\frac{b}{b+1}\cdot n \right) \right) \right\rfloor \\[8pt] \overline{\lambda_{b}}(n) &:= \left\lfloor \log_{b}\left(\max\left(1,\frac{1}{2} \cdot n\right) \right) \right\rfloor \end{split} \end{equation*}$

ergibt sich

(100) $\begin{equation*} L\left(P_{b}(n)\right) = \begin{cases} 2 \cdot \lambda_{b}(n) +1, &\text{wenn} \; \lambda_{b}(n) = \overline{\lambda_{b}}(n) \\[8pt] 2 \cdot \lambda_{b}(n), &\text{sonst} \end{cases} \end{equation*}$

Da $\overline{\lambda_{b}}(n)$ entweder gleich $\lambda_{b}(n)$ oder um $1$ kleiner ist, wird die Stellenanzahl von $P_{b}(n)$ im Falle der Ungleichheit $\lambda_{b}(n) \ne \overline{\lambda_{b}}(n)$ durch die Summe $2 \cdot \overline{\lambda_{b}}(n) +2$ bestimmt. Man kann daher für die Stellenanzahl von $P_{b}(n)$ auch schreiben

(101) $\begin{equation*} L\left(P_{b}(n)\right) = \lambda_{b}(n) + \overline{\lambda_{b}}(n) + 1\end{equation*}$

Nach dem Vorstehenden ist somit die Stellenanzahl ungerade im ersteren Falle, wenn also $\lambda_{b}(n) = \overline{\lambda_{b}}(n)$ , andernfalls, wenn also $\lambda_{b}(n) \ne \overline{\lambda_{b}}(n)$ , ist sie gerade. Demnach gilt auch

(102) $\begin{equation*} \lambda_{b}(n) = \left\lfloor \frac{L\left(P_{b}(n)\right)}{2} \right\rfloor \end{equation*}$

sowie

(103) $\begin{equation*} \overline{\lambda_{b}}(n) = \left\lfloor \frac{L\left(P_{b}(n)\right) - 1}{2} \right\rfloor \end{equation*}$

7.1 Rekursive Berechnung

Die folgende Beziehung erlaubt für $n > b$ die rekursive Berechnung des $n$ -ten Basis- $b$ -Palindroms.

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

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

(105) $\begin{align*} q &= \lambda_{b}(n) + \overline{\lambda_{b}}(n) \\[8pt]d &= \displaystyle \left(\left\lfloor \frac{n}{b^{ \left\lfloor\frac{q}{2}\right\rfloor}} \right\rfloor -1 + q \bmod 2 \right) \bmod b \end{align*}$

Wegen $q \bmod 2 = \lambda_{b}(n) - \overline{\lambda_{b}}(n)$ kann man dabei auch direkt auf die $\lambda_{b}$ -Funktionen zurückgreifen. Die weiteren Parameter $m$ und $p$ bestimmt man mittels des nachfolgend definierten Hilfsparameters $N$ .

(106) $\begin{equation*} \begin{split} N &= \displaystyle \left(d+1+ (b-1)\cdot \left(q \bmod 2 \right) \right) \cdot b^{ \left\lfloor\frac{q}{2}\right\rfloor} \\[8pt] m &= \begin{cases} 1, &\text{wenn} \; n = N \\[4pt] n - N + b^{\displaystyle \left\lfloor\log_{b}\left(n-N\right) \right\rfloor + q \bmod 2}, &\text{sonst} \end{cases} \\[8pt]p &= \lambda_{b}(n) - \lambda_{b}(m) \end{split} \end{equation*}$

Die Stellenanzahl $L\left(P_{b}(n)\right)$ des Palindroms ist $q + 1$ . Demnach hat das gesuchte Palindrom eine ungerade Anzahl von Stellen, wenn $q$ gerade ist, und eine gerade Anzahl von Stellen, wenn $q$ ungerade ist.

Nehmen wir als Beispiel Palindrome zur Basis $b = 5$ sowie $b = 7$ für $n = 90$ . Die ersten $20$ dieser Palindrome sind:

(107) $\begin{equation*} \begin{array} {lll} P_{5}(n), &1 \le n \le 20: \;\\ &0,1,2,3,4,11,22,33,44,101,111, 121, \\&131, 141, 202, 212, 222, 232, 242, 303, \cdots &\text{(Basis 5)} \\&0,1,2,3,4,6,12,18,24,26,31,36,\\&41,46,52,57,62,67,72,78, \cdots &\text{(dezimal)} \\[8pt]P_{7}(n), &1 \le n \le 20: \;\\ &0,1,2,3,4,5,6,11,22,33,44,55,\\&66,101,111,121,131,141,151,161, \cdots &\text{(Basis 7)} \\&0,1,2,3,4,5,6,8,16,24,32,40,\\&48,50,57,64,71,78,85,92, \cdots &\text{(dezimal)} \end{array} \end{equation*}$

Nun bestimmen wir $P_{5}(90)$ rekursiv und erhalten

(108) $\begin{equation*} \begin{split} q &= \lambda_5(90) + \overline{\lambda_{5}}(90) = 4\) \\ d&= \left(\left\lfloor \frac{90}{5^{ \left\lfloor\frac{4}{2}\right\rfloor}} \right\rfloor - 1 + 4 \bmod 2 \right) \bmod 5 = 2 \\N &= \left(2+1+ 4\cdot \left(4 \bmod 2 \right) \right) \cdot 5^{ \left\lfloor\frac{4}{2}\right\rfloor} = 75 \\n - N &= 90 - 75 = 15 \\m &= 15 + 5^{ \left\lfloor\log_{5}\left(15 \right) \right\rfloor + 4 \bmod 2} = 20 \\p &= \lambda_5(90) - \lambda_5(20) = 1 \end{split} \end{equation*}$

Mit $P_{5}(20) = 78$ bekommen wir

(109) $\begin{equation*} \begin{split} P_{5}(90) &= 2\cdot 5^4 + 2 + 5^1 \cdot P_{5}(20) \\ &= 1252 + 5\cdot 78 \\&= 1642 \\&= 23032_5 \end{split} \end{equation*}$

Völlig analog verläuft die rekursive Berechnung von $P_{7}(90)$

(110) $\begin{equation*} \begin{split} q &= \lambda_7(90) + \overline{\lambda_{7}}(90) = 3\) \\ d&= \left(\left\lfloor \frac{90}{5^{ \left\lfloor\frac{3}{2}\right\rfloor}} \right\rfloor - 1 + 1 \bmod 2 \right) \bmod 7 = 5 \\N &= \left(5+1+ 6\cdot \left(3 \bmod 2 \right) \right) \cdot 7^{ \left\lfloor\frac{3}{2}\right\rfloor} = 84 \\n - N &= 90 - 84 = 6 \\m &= 6 + 7^{ \left\lfloor\log_{7}\left(6 \right) \right\rfloor + 3 \bmod 2} = 13 \\p &= \lambda_7(90) - \lambda_7(13) = 1 \end{split} \end{equation*}$

Unter Berücksichtigung von $P_{7}(13) = 48$ erhalten wir

(111) $\begin{equation*} \begin{split} P_{7}(90) &= 5\cdot 7^3 + 5 + 7^1 \cdot P_{7}(13) \\ &= 1715 + 7\cdot 48 \\&= 2056 \\&= 5665_7 \end{split} \end{equation*}$

7.2 Direkte Berechnung

Das $n$ -te Palindrom in Basis- $b$ kann für $n > b$ auf dem nachfolgend beschriebenen Wege direkt berechnet werden.

Wir setzen $m := \lambda_{b}(n)$ und unterscheiden zwei Fälle.

Fall 1: $\lambda_{b}(n) = \overline{\lambda_{b}}(n)$

(112) $\begin{equation*} \begin{split} P_{b}(n) &=\sum \limits_{k=1}^{m-1} \left(\left\lfloor \frac{n}{b^{m-k}}\right\rfloor \bmod b\right)\left(b^k + b^{2m-k}\right) \; + \\[4pt]& \quad \, \left( \left\lfloor \frac{n}{b^m} \right\rfloor -1 \right) \left(1 + b^{2m}\right) + \left(n \bmod b \right) \cdot b^m \\[10pt]&= \sum \limits_{k=1}^{m-1} \left(\left\lfloor \frac{n}{b^{m-k}}\right\rfloor \bmod b\right) \cdot b^k \;+ \\[4pt] & \quad \, \left(n - b^m\right) \cdot b^m + \left\lfloor \frac{n}{b^m} \right\rfloor -1 \end{split} \end{equation*}$

Fall 2: $\lambda_{b}(n) \ne \overline{\lambda_{b}}(n)$

(113) $\begin{equation*} \begin{split} P_{b}(n) &=\sum \limits_{k=0}^{m-1} \left(\left\lfloor \frac{n}{b^{m-k-1}}\right\rfloor \bmod b\right)\left(b^{k} + b^{2m-k-1}\right) \\[8pt]&= \sum \limits_{k=1}^{m-1} \left(\left\lfloor \frac{n}{b^{m-k}}\right\rfloor \bmod b\right)\cdot b^{k-1} \;+ \\[4pt] & \quad \, \left(n - b^m\right) \cdot b^m + \left( n \bmod b\right) \cdot b^{m-1} \end{split} \end{equation*}$

Betrachten wir auch betreffend der direkten Berechnung zwei Beispiele und nehmen dafür Palindrome zur Basis $b = 6$ sowie $b = 9$ für $n = 400$ . Die ersten $20$ dieser Palindrome sind:

(114) $\begin{equation*} \begin{array} {lll} P_{6}(n), \; &1 \le n \le 20: \\ &0,1,2,3,4,5,11,22,33,44,55,101,\\ &111, 121, 131, 141, 151, 202, 212, 222, \cdots &\text{(Basis 6)} \\&0,1,2,3,4,5,7,14,21,28,35,37,\\ &43,49,55,61,67,74,80,86, \cdots &\text{(dezimal)} \\[8pt]P_{9}(n), \; &1 \le n \le 20: \;\\ &0,1,2,3,4,5,6,7,8,11,22,33,\\&44,55,66,77,88,101,111,121, \cdots &\text{(Basis 9)} \\&0,1,2,3,4,5,6,7,8,10,20,30,\\ &40,50,60,70,80,82,91,100, \cdots &\text{(dezimal)} \end{array} \end{equation*}$

Zunächst das Beispiel $P_{6}(400)$ . Es gilt $\lambda_{6}(400) = 3 \ne 2 = \overline{\lambda_{&}}(400)$ , demnach liegt der Fall 2 mit $m=3$ vor. Die beiden Terme des Summenausdrucks sind $\left(\left\lfloor \frac{400}{6^{3-1}}\right\rfloor \bmod 6\right)\cdot 6^{0} = 5$ und $\left(\left\lfloor \frac{400}{6^{3-2}}\right\rfloor \bmod 6\right)\cdot 6^{1} = 0$ . Die äußeren Summanden ergeben $\left(400 - 6^3\right) \cdot 6^3 = 184 \cdot 6^3 = 39744$ und $\left( 400 \bmod 6\right) \cdot 6^{3-1} = 144$ . Zusammen folgt $(P_{6}(400) = 5 + 0 + 39744 +144 = 39893 = 504405_6$ .

Für das Beispiel $P_{9}(400)$ erhalten wir, $\lambda_{9}(400) = 2 =\overline{\lambda_{9}}(400)$ , demnach liegt der Fall 1 mit $m=2$ vor. Der einzige Term des Summenausdrucks ist $\left(\left\lfloor \frac{400}{9^{2-1}}\right\rfloor \bmod 9\right)\cdot 9^{0} = 8$ . Die äußeren Summanden ergeben $\left(400 - 9^2\right) \cdot 9^2 = 319 \cdot 9^2 = 25839$ und $\left( 400 \bmod 9\right) \cdot 9^{2-1} = 36$ . Zusammen bekommen wir die Summe $P_{9}(400) = 8 + 25839 +36 = 25883 = 38483_9$ .

7.3 Anschauliche Bestimmung

Die anschauliche Bestimmung des $n$ -ten Basis- $b$ -Palindroms verläuft ähnlich, wie im Fall der dezimalen Palindrome. Zunächst muss $n$ im Basis- $b$ -Ziffernsystem dargestellt werden. Mit $n = \(\left[ \, d_1\; d_2\; d_3 \cdots d_k \, \right]_b$ erhält man:

(115) $\begin{equation*} P_{b}(n) \Leftrightarrow \begin{cases} \large \left[ \, d_1-1\; d_2\; d_3 \cdots d_k \cdots d_3\; d_2\; d_1 -1 \,\right]_b, & \text{falls}\; d_1 > 1 \\[4pt]\large \left[ \, b-1\; d_3 \cdots d_k \cdots d_3\; b-1 \, \right]_b, & \text{falls}\; d_1 = 1 \; \text{und} \; d_2 = 0 \\[4pt]\large \left[ \, d_2\; d_3 \cdots d_k\; d_k \cdots d_3\; d_2 \,\right]_b, & \text{falls}\; d_1 = 1 \; \text{und} \; d_2 > 0 \end{cases} \end{equation*}$

Beispiel: $n = 237_8 = 159_{10}$ . 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_{8}(n)$ zu $\left[ \, 1 \; 3 \; 7 \; 3 \; 1 \, \right]_8$ , also $P_{8}(n) = 13731_8 = 6105_{10}$ .

7.4 Umkehrungsformel

Die Frage nach dem betreffenden Indexwert $n$ , für den gilt $P_{b}}(n) = P$ für ein vorgegebenes Basis- $b$ -Palindrom $P > 0$ , ist in Analogie zu den dezimalen Palindromen ebenfalls einfach zu beantworten. Mir der Definition $m := \left\lfloor \log_{b}(P)\right\rfloor$ gilt:

(116) $\begin{equation*} n = P_{b}^{-1}(P) = \left\lfloor \frac{ P}{ b^{\left\lfloor \frac{m+1}{2} \right\rfloor}} \right\rfloor + b^{ \left\lfloor \frac{m+1}{2} \right\rfloor} \end{equation*}$

Nehmen wir $P = 370073_8 = 79157_{10}$ als Beispielpalindrom für Basis $b = 8$ . Wir finden $n = P_8^{-1}(79157) = 666$ .

Ein weiteres Beispiel mit Basis $b = 3$ ist $2120212_3 = 1886_{10}$ . Hierfür ergibt sich $n = P_3^{-1}(1886) = 96$ . Für Basis $b = 9$ folgt bei der formal gleichen Ziffernfolge $2120212_9 = 1135226_{10}$ das Ergebnis $n = P_9^{-1}(1135226) = 2286.$

7.5 Anzahlfunktion

Für Potenzen zur Basis- $b$ folgt direkt die Anzahl der Basis- $b$ -Palindrome zwischen $b^{n-1}$ und $b^{n}$ zu

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

Für die Anzahl der Basis- $b$ -Palindrome $< b^{n}$ , $n \ge 0$ , ergibt sich daher nach Aufaddieren vorgenannter Partialsummen

(118) $\begin{align*} A_{b}\left(b^{n}\right) &= \displaystyle \begin{cases} 2\cdot b^{\frac{n}{2}} - 1, \; &n \bmod 2 = 0 \\[4pt]\displaystyle (b+1)\cdot b^{\frac{n-1}{2}} - 1, \; &n \bmod 2 = 1 \end{cases} \\[8pt]&= \displaystyle \left(2 + (b-1)\cdot n \bmod 2\right) \cdot b^{\left\lfloor\frac{n}{2}\right\rfloor} - 1 \\[8pt] &= \displaystyle \frac{b+3 - (b-1)\cdot (-1)^n}{2} \cdot b^{\left\lfloor\frac{n}{2}\right\rfloor} - 1\end{align*}$

7.6 Wachstum der Folge von Palindromen zur Basis b

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

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

(120) $\begin{equation*} \begin{split} \liminf_{n \rightarrow \infty} \frac{P_b(n)}{n^2} &= \frac{b}{(b+1)^2} \\[4pt] \limsup_{n \rightarrow \infty} \frac{P_b(n)}{n^2} &= \frac{1}{4} \end{split} \end{equation*}$

7.7 Rechenoperationen mit Palindromen

Generell bezeichnen wir die Ziffernfolge einer Basis- $b$ -Zahl $Z = Z_b$ symbolisch mit $[Z]$ bzw. $[Z_b]$ . Die numerische Zahl $Z = 251_7$ entspricht demnach der Ziffernfolge $[Z] = [251_7] = [251]_7$ . Zu einer Ziffer $d$ , $0 \le d < b$ , steht $[\,d\,]^k$ für die Ziffernfolge von $k$ gleichen Ziffern, also etwa $[3]^5 = [33333]$ , entsprechend dem numerischen Wert $33333$ . Wenn die Basis nicht direkt mit notiert ist, dann ergibt sich diese entweder aus dem Kontext, oder es ist die Basis $b = 10$ gemeint. Im Ziffernsystem $b = 7$ notieren wir im vorigen Beispiel $[3_7]^{5}= [3]_{7}^{5} = [33333]_7$ .

Die Anzahl der Ziffern von $Z$ bzw. von $[Z]$ bezeichnen wir symbolisch mit $L_b(Z)$ .

Die Ziffernfolge von $Z$ ohne die erste Ziffer, also nur die Ziffern rechts nach der ersten Ziffer notieren wir als $[Z]^r$ . Analog bedeutet $[Z]^l$ die Ziffernfolge von $Z$ ohne die letzte Ziffer, also nur die Ziffern links vor der letzten Ziffer. Für $[Z] := [\, d_1 \; d_2 \; d_3 \cdots d_{k-1} \; d_{k} \,]$ gilt also $[Z]^r = [\, d_2 \; d_3 \cdots d_{k-1} \; d_{k} \,]$ und $[Z]^l = [\, d_1 \; d_2 \; d_3 \cdots d_{k-1} \,]$ . Dagegen steht $[Z]_j$ für die $j$ -te Ziffer in der Ziffernfolge $[Z]$ , wobei $1 \le j \le L_b(Z)$ . Wenn die Basis angegeben wird, so gilt $[Z]_j =[Z_b]_j$ .

Liegen zwei Basis- $b$ -Zahlen $X$ und $Y$ vor, so bedeutet $[X][Y]$ die Verkettung (Concatenation) der beiden Ziffernfolgen. Der Zahlenwert $Z$ der Verkettung entspricht numerisch der Summe $X\cdot b^{L_b(Y)} + Y$ .

Die stellenweise Addition von $[X]$ und $[Y]$ bezeichnen wir mit $[X] \oplus [Y]$ , also $[52025] \oplus [121] = [52146]$ . Um die Addition nicht rechtsbündig sondern geeignet nach links verschoben durchzuführen, verkettet man $[X]$ oder $[Y]$ entsprechend mit einer Hilfsgröße. Z.B. ist $[52025] \oplus [0][121][0] =[53235]$ . Man erkennt bereits hier, wie solchermaßen Palindrome konstruiert werden können. Analog verfahren wir bei der Subtraktion: $[53635] \ominus [0][121][0] = [52425]$ .

7.7.1 Konstruktion von Palindromen

Sei $a$ eine Basis- $b$ -Zahl, $\overleftarrow{a}$ sei die Zahl mit der in Bezug auf $a$ umgekehrten Ziffernreihenfolge.

7.7.1-(1) $[Q] := [a]^l[\overleftarrow{a}]$ ist ein Basis- $b$ -Palindrom. Numerisch bestimmt sich der Wert mittels $Q = b^{q} \cdot \left\lfloor \frac{a}{b} \right\rfloor + \overleftarrow{a}$ , wobei $q := L_b(a)$ . Die Stellenanzahl von $Q$ ist ungerade und es gilt $L_b(Q) = 2\cdot q - 1$ . Die Verkettung $[a][\overleftarrow{a}]^r$ liefert identisch das Palindrom $[Q]$ . Die numerische Berechnung hierfür lautet $Q = b^{q-1} \cdot a + \overleftarrow{a} \bmod b^{q-1}$ .

7.7.1-(2) $[Q] := [a][\overleftarrow{a}]$ ist ein Basis- $b$ -Palindrom. Numerisch gilt: $Q := b^q \cdot a + \overleftarrow{a}$ , wobei $q := L_b(a)$ . Die Stellenanzahl von $Q$ ist gerade und es gilt $L_b(Q) = 2\cdot q$ .

7.7.1-(3) Wenn $P$ ein Basis- $b$ -Palindrom ist, dann ist auch $[Q] := [a][P][\overleftarrow{a}]$ ein Palindrom. Numerisch gilt: $Q = b^{q + L_b(P)} \cdot a + b^q \cdot P + \overleftarrow{a}$ , wobei $q := L_b(a)$ . Die Stellenanzahl von $Q$ ist $L_{b}(Q) = 2 \cdot q + L_b(P)$ .

Natürlich ist für jede Ziffer $d < b$ bereits jede Verkettung $[a][\,d\,]^k[\overleftarrow{a}]$ , $k>0$ , ein Palindrom, weil auch $[\,d\,]^k$ ein Palindrom ist.

Beispiel 1: $b = 10$ , $[a] = 230$ , $[\overleftarrow{a}] = [032]$ , $[a]^l = [23]$ , $[\overleftarrow{a}]^r = [32]$ , $q := L_b(a) = 3$ . Es folgt $[Q] =[23][032] = [230][32] =[23032]$ . Numerisch erhalten wir $Q = 10^{3} \cdot \left\lfloor \frac{230}{10} \right\rfloor + 32 = 1000*23 + 32 = 23032$ . Ebenso: $Q = 10^{3-1} \cdot 230 + 32 \bmod 10^{3-1} = 100 \cdot 230+32 = 23032$ , jeweils mit der Stellenanzahl $2\cdot 3 -1 =5$

Beispiel 2: $b = 10$ , $[a] = 230$ , $\overleftarrow{a} = [032]$ , $q := L_b(a) = 3$ . Nun ergibt sich $[Q] =[230][032] = [230032]$ sowie $Q = 10^3 \cdot 230 + 32} = 230032$ . Die Stellenanzahl ist $L_{10}(Q) = 2\cdot 3 = 6$ .

Beispiel 3: $b = 10$ , $P = [64746]$ , $a = [230]$ , $\overleftarrow{a} = [032]$ , $q := L_b(a) = 3$ . Zunächst ist $[Q] = [230][64746][032] = [23064746032]$ . Numerisch erhalten wir: $Q = 10^{3 + 5} \cdot 230 + 10^3 \cdot 64746 + 32$ , und somit $Q = 23000000000 + 64746000 + 32 = 23064746032$ .

7.7.2 Summen von Palindromen

7.7.2-(1) Definition. Zwei Basis- $b$ -Palindrome $P$ und $Q$ heißen summenkompatibel oder kurz S-kompatibel, wenn
(i) $L_b(P) \ge L_b(Q)$ und
(ii) $\left( L_b(P) - L_b(Q) \right) \bmod 2 = 0$ und
(iii) Für alle $k, \; 0 \le k < L_b(Q)$ gilt $\left\lfloor\frac{P}{b^{k+d}}\right\rfloor \bmod b + \left\lfloor\frac{Q}{b^{k}}\right\rfloor \bmod b < b$ , wobei $d := \frac{ L_b(P) - L_b(Q)}{2}$ .

7.7.2-(2) Summe. Seien $P$ und $Q$ zwei S-kompatible Basis- $b$ -Palindrome. Dann ist mit $d := \frac{ L_b(P) - L_b(Q)}{2}$ auch die Summe $P + b^d \cdot Q$ ein Basis- $b$ -Palindrom.

Beispiel 1: $b = 10$ , $P = 423324$ , $Q = 1551$ . (i) und (ii) sind erfüllt und wir haben $d = \frac{6 - 4}{2} = 1$ . Für $k = 0,1,2,3$ gilt $\left\lfloor\frac{423324}{10^{k+1}}\right\rfloor \bmod 10 + \left\lfloor\frac{1551}{10^{k}}\right\rfloor \bmod 10 = 3,8,8,3$ , womit die Werte sämtlich $< 10$ sind. Folglich erhalten wir $P + b^d \cdot Q = 423324 + 10^1 \cdot 1551 = 438834$ als das Summenpalindrom.

Wenn in der Situation von 7.7.2-(2) die Stellenanzahl der beiden Palindrome $P$ und $Q$ gleich ist, dann ist bereits die einfache Summe $P + Q$ ein Palindrom.

7.7.2-(3) Seien $n_P$ und $n_Q$ die beiden Nummern, so dass $P = P_b(n_P)$ und $Q = P_b(n_Q)$ .
Mit $d := \frac{ L_b(P) - L_b(Q)}{2}$ gilt sodann $P + b^d \cdot Q = P_b(n)$ ,
wobei $n = n_P + n_Q - b^{\left\lfloor\frac{L_Q}{2}\right\rfloor} = n_P + n_Q - b^{\lambda_b(Q)}$

Beispiel 2: $b = 10$ , $P = 423324$ , $Q = 1551$ , $d = 1$ . Wir haben $n_P = 1423$ und $n_Q = 115$ sowie $n = n_P + n_Q - 10^{\left\lfloor\frac{L_Q}{2}\right\rfloor} = 1423 + 115 - 100 = 1438$ und es gilt $= = \(423324 + 10^1 \cdot 1551 = 438834 = P_{10}(1438)$ .

7.7.2-(4) Summe Modulo b. Seien $P$ und $Q$ zwei Basis- $b$ -Palindrome. Dann ist unter der Voraussetzung 7.7.2-(1) (i) und (ii) auch die ziffernweise Modulo- $b$ -Summe $[P] \oplus [0]^{d}[Q][0]^{d}$ ein Basis- $b$ -Palindrom.

Beispiel 3: $b = 6$ , $P = 41514_6$ , $Q = 434_6$ , $d = 1$ . Es gilt $[P] \oplus [0][Q][0] = [41514] \oplus [0][434][0] = [45254]_6$ , da bei der ziffernweisen Addition $(5+3) \bmod 6 = 2$ ist.

7.7.3 Differenzen von Palindromen

7.7.3-(1) Zwei Basis- $b$ -Palindrome $P$ und $Q$ heißen differenzkompatibel oder kurz D-kompatibel, wenn
(i) $L_b(P) \ge L_b(Q)$ und
(ii) $\left( L_b(P) - L_b(Q) \right) \bmod 2 = 0$ und
(iii) Für alle $k, \; 0 \le k < L_b(Q)$ gilt $\left\lfloor\frac{P}{b^{k+d}}\right\rfloor \bmod b - \left\lfloor\frac{Q}{b^{k}}\right\rfloor \bmod b \ge 0$ , wobei $d := \frac{ L_b(P) - L_b(Q)}{2}$ .

7.7.3-(2) Differenz. Seien $P$ und $Q$ zwei D-kompatible Basis- $b$ -Palindrome. Dann ist mit $d := \frac{ L_b(P) - L_b(Q)}{2}$ auch die Differenz $P - b^d \cdot Q$ ein Basis- $b$ -Palindrom.

Beispiel 1: $b = 10$ , $P = 43834$ , $Q = 343$ . (i) und (ii) sind erfüllt und wir haben $d = \frac{5 - 3}{2} = 1$ . Für $k = 0,1,2$ gilt $\left\lfloor\frac{43834}{10^{k+1}}\right\rfloor \bmod 10 + \left\lfloor\frac{343}{10^{k}}\right\rfloor \bmod 10 = 0,4,0$ , womit die Werte sämtlich $\ge 0$ sind. Folglich erhalten wir $P + b^d \cdot Q = 43834 - 10^1 \cdot 343 = 40404$ als das Differenzpalindrom.

Wenn in der Situation von 7.7.3-(2) die Stellenanzahl der beiden Palindrome $P$ und $Q$ gleich ist, dann ist bereits die einfache Differenz $P - Q$ ein Palindrom.

7.7.3-(3) Seien $n_P$ und $n_Q$ die beiden Nummern, so dass $P = P_b(n_P)$ und $Q = P_b(n_Q)$ .
Mit $d := \frac{ L_b(P) - L_b(Q)}{2}$ gilt sodann $P - b^d \cdot Q = P_b(n)$ ,
wobei $n = n_P - n_Q + b^{\left\lfloor\frac{L_Q}{2}\right\rfloor} = n_P - n_Q + b^{\lambda_b(Q)}$ .

Beispiel 2: $b = 10$ , $P = 43834$ , $Q = 343$ , $d = 1$ . Wir haben $n_P = 538$ und $n_Q = 44$ sowie $n = n_P - n_Q + 10^{\left\lfloor\frac{L_Q}{2}\right\rfloor} = 538 - 44 + 10 = 504$ und es gilt $43834 - 10^1 \cdot 343= 40404 = P_{10}(504)$ .

7.7.3-(4) Differenz Modulo b. Seien $P$ und $Q$ zwei Basis- $b$ -Palindrome. Dann ist unter der Voraussetzung 7.7.3-(1) (i) und (ii) auch die ziffernweise Modulo- $b$ -Differenz $[P] \ominus [0]^{d}[Q][0]^{d}$ ein Basis- $b$ -Palindrom.

Beispiel 3: $b = 6$ , $P = 45254_6$ , $Q = 434_6$ , $d = 1$ . Es gilt $[P] \ominus [0][Q][0] = [42525] \ominus [0][434][0] = [41514]_6$ , da bei der ziffernweisen Subtraktion $(2 - 3) \bmod 6 = 5$ gilt.

7.8 Existenz

7.8.1 Definitionen und einfache Folgerungen

7.8.1-(1) Definition. Jede Zahl $Z$ ist ein Palindrom in allen Basen $b > Z$ . Solche Palindrome nennen wir trivial, da sie nur aus einer Ziffer bestehen.

7.8.1.-(2) Definition. Ein Basis- $b$ -Palindrom $P$ heißt nicht-trivial, wenn $b < P$ . Ein solches Palindrom hat mindestens 2 Ziffern.

7.8.1-(3) Definition. Ein Basis- $b$ -Palindrom $P$ heißt schwach, wenn gilt $b < P < b^2$ . Ein solches Palindrom hat genau 2 Ziffern.

7.8.1-(4) Definition. Ein Basis- $b$ -Palindrom $P$ heißt stark oder echt, wenn gilt $b^2 < P$ . Ein solches Palindrom hat mindestens 3 Ziffern.

Folgerungen:

$0,1$ sind triviale Palindrome in allen Basen $b > 1$ .
$2$ ist ein triviales Palindrom in allen Basen $b > 2$ .

Jede Zahl $Z > 2$ ist ein schwaches Palindrom in Basis $b = Z - 1$ , denn es gilt $Z = b + 1 = 11_b$ .

$3$ ist ein schwaches Palindrom in Basis $b = 2$ , wegen $3 = 11_2$ .
$4$ ist ein schwaches Palindrom in Basis $b = 3$ , wegen $4 = 11_3$ .

$5$ ist ein starkes Palindrom in Basis $b = 2$ , wegen $5 = 101_2$ .
$5$ ist das kleinste starke Palindrom.

$6$ ist ein schwaches Palindrom in Basis $b = 5$ , wegen $6 = 11_5$ .
$7$ ist ein starkes Palindrom in Basis $b = 2$ , wegen $7 = 111_2$ .
$8$ ist ein schwaches Palindrom in Basis $b = 7$ , wegen $8 = 11_7$ , und gleichfalls ein schwaches Palindrom in Basis $b = 3$ , wegen $8 = 22_3$ ,

7.8.2 Existenzsätze – hinreichende Bedingungen

7.8.2-(1) Jede gerade Zahl $Z > 6$ ist ein nicht-triviales Palindrom in Basis $b = \frac{Z}{2} - 1$ .

Beweis: Es gilt $Z = 2\cdot \left(\frac{Z}{2} - 1\right) + 2 = 2\cdot b + 2 = [22]_b$ und $2 < 3 = \frac{6}{2} \le \frac{Z-2}{2} = \frac{Z}{2} - 1 = b$ . $\square$

7.8.2-(2) Jede durch $3$ teilbare Zahl $Z > 12$ ist ein nicht-triviales Palindrom in Basis $b = \frac{Z}{3} - 1$ .

Beweis: Es gilt $Z = 3\cdot \left(\frac{Z}{3} - 1\right) + 3 = 3\cdot b + 3 = [33]_b$ und $3 < 4 = \frac{12}{3} \le \frac{Z-3}{3} = \frac{Z}{3} - 1 = b$ . $\square$

7.8.2-(3) Jede durch $p > 1$ teilbare Zahl $Z > p(p+1)$ ist ein nicht-triviales Palindrom in Basis $b = \frac{Z}{p} - 1$ .

Beweis: Es gilt $Z = p\cdot \left(\frac{Z}{p} - 1\right) + p = p\cdot b + p = [pp]_b$ und $p < p+1 = \frac{p^2 +p}{p} \le \frac{Z-p}{p} = \frac{Z}{p} - 1 = b$ . $\square$

7.8.2-(4) Zu jeder zusammengesetzten Zahl $Z > 6$ gibt es eine Basis $b < \frac{Z}{2}$ , so dass $Z$ ein schwaches oder ein echtes Palindrom in Basis $b$ ist.

Beweis: Nach Wahl von $Z$ gibt es nicht-triviale Teiler $p$ und $q$ , so dass $Z = pq$ . OBdA sei $p \le q$ . Nach Voraussetzung gilt $p \ge 2$ , und $q \ge 3$ . Wenn $p = 2$ , dann $q \ge 4$ , wenn $p > 2$ , dann $q \ge 3$ .

Wir treffen die folgende Fallunterscheidung:

(A) $p < q - 1$ .
Mit $b = q - 1$ ergibt sich $Z = pq = p(q-1) + p = p\cdot b+p = [pp]_b$ , wobei $p < b$ und $b = q - 1 = \frac{z}{p} - 1 < \frac{Z}{p} \le \frac{Z}{2}$ . Demnach ist $Z$ ein schwaches Palindrom.

(B) $p = q - 1$ .
Dann ist $p > 2$ und $Z$ gerade. Wir setzen $b = \frac{pq}{2} - 1$ . Es ergibt sich $Z = pq = 2\cdot \left(\frac{pq}{2} - 1\right) + 2 = [22]_b$ mit $2 < b$ und $b = \frac{pq}{2} - 1 = \frac{Z}{2} - 1 < \frac{Z}{2}$ . Daher ist $Z$ ein schwaches Palindrom.

(C) $p = q$ . $Z$ ist eine Quadratzahl $\ge 9$ , also $Z = p^2$ mit $p \ge 3$ . Für $Z = 9$ haben wir mit $b = 2$ , $Z = b^3 + 1$ , also $Z = [1001]_2$ . $Z$ ist ein echtes Palindrom mit $b < \frac{Z}{3} < \frac{Z}{2}$ . Für $Z > 9$ , also $p > 3$ , setzen wir $b = p - 1$ und bekommen $Z = (p - 1 + 1)^2 = (p - 1)^2 + 2(p -1) + 1 = 1\cdot b^2 + 2\cdot b + 1 \cdot b^0$ , also $Z = 121_b$ mit $2 < p - 1 = b$ . Demzufolge ist $Z$ ist ein echtes Palindrom mit $b = p - 1 < p < \frac{p\cdot p}{3} < \frac{Z}{2}$ . $\square$

Folgerung:

Alle Nicht-Primzahlen $Z > 6$ sind schwache oder echte Palindrome mit einer Basis $b < \frac{Z}{2}$ .

7.8.2-(5) Jede Potenzzahl $Z = p^k$ , $k \ge 2$ , $p > 2$ , ist ein schwaches Palindrom in Basis $b = p^{\left\lfloor \frac{k+2}{2} \right\rfloor} - 1$ .

Beweis: Wir unterscheiden die beiden Fälle $k \bmod 2 = 0$ und $k \bmod 2 = 1$ .

(A) $k \bmod 2 = 0$ .
Wir haben $b = p^{\frac{k+2}{2}} - 1$ und setzen $d = p^{\frac{k-2}{2}}$ . Damit erhalten wir $Z = d\cdot b + d$ , wobei $d = p^{\frac{k}{2} -1} = \frac{b+1}{p^2} < \frac{b+1}{4}$ . Somit gilt $d = b - \left(b - \frac{b+1}{4}\right) = b - \frac{3b -1}{4} < b$ , und folglich $Z = [dd]_b$ .

(B) $k \bmod 2 = 1$ .
Hier setzen wir $b = p^{\frac{k+1}{2}} - 1$ und $d = p^{\frac{k-1}{2}}$ . Damit bekommen wir $Z = d\cdot b + d$ , wobei $d = p^{\frac{k -1}{2}} = \frac{b+1}{p} < \frac{b+1}{2}$ . Somit gilt $d = b - \left(b - \frac{b+1}{2}\right) = b - \frac{b -1}{2} < b$ , und folglich $Z = [dd]_b$ . $\square$

7.8.2-(6) Jede Quadratzahl $Z = p^2$ , $p > 3$ , ist ein echtes Palindrom in Basis $b = p - 1$ mit $3$ Ziffern.

Beweis: $Z = (p - 1 + 1)^2 = (p - 1)^2 + 2(p -1) + 1$ , mithin $Z = 1\cdot b^2 + 2\cdot b + 1\cdot b^0$ , also $Z = 121_b$ mit $2 < p - 1 = b$ . $\square$

7.8.2-(7) Jede Kubikzahl $Z = p^3$ , $p > 4$ , ist ein echtes Palindrom in Basis $b = p - 1$ mit $4$ Ziffern.

Beweis: $Z = (p - 1 + 1)^3 = (p - 1)^3 + 3(p -1)^2 + 3(p -1) + 1$ , daher $Z = 1\cdot b^3 + 3\cdot b^2 + 3\cdot b^1 + 1\cdot b^0$ , also $Z = 1331_b$ mit $3 < p - 1 = b$ . $\square$

Die vorgenannte Feststellung gilt ganz allgemein für alle Potenzzahlen.

7.8.2-(8) Jede Potenzzahl $Z = p^k$ , $k$ gerade, $p > 1 + 2^k \cdot \frac{\Gamma\left(\frac{k+1}{2}\right)}{\sqrt{\pi} \cdot \Gamma\left(\frac{k+2}{2}\right)}$ , ist ein echtes Palindrom in Basis $b = p - 1$ mit $k+1$ Ziffern.

Beweis: $Z = (p-1+1)^k = \sum \limits_{j=0}^{k} \binom{k}{j}\cdot (p-1)^{k-j}$ , also $z = \sum \limits_{j=0}^{k} \binom{k}{j}\cdot b^{k-j}$ .

Der größte Term $d_j := \binom{k}{j}$ in der Summe ist der Wert für $j = \frac{k}{2}$ und beläuft sich auf $\binom{k}{\frac{k}{2}} = \frac{k\cdot (k-1)\cdots (k-\frac{k}{2}+1)}{(\frac{k}{2})!} = 2^k \cdot \frac{\Gamma\left(\frac{k+1}{2}\right)}{\sqrt{\pi} \cdot \Gamma\left(\frac{k+2}{2}\right)}$ . Dieser Wert ist nach Voraussetzung $< p - 1$ . $\square$

Demnach erhalten wir die Darstellung im Basis- $b$ -Ziffernsystem zu $Z = [\, d_0 \; d_1 \; d_2 \cdots d_k \,]_b$ . Aufgrund der Symmetrie der Binomialfaktoren, also $\binom{k}{j} = \binom{k}{k-j}$ , für $0 \le j \le k$ , ist folglich $Z$ ein Palindrom in Basis $b$ . $\square$

7.8.2-(9) Jede Potenzzahl $Z = p^k$ , $k$ ungerade, $p > 1 + 2^k \cdot \frac{\Gamma\left(\frac{k+2}{2}\right)}{\sqrt{\pi} \cdot \Gamma\left(\frac{k+3}{2}\right)}$ , ist ein echtes Palindrom in Basis $b = p - 1$ mit $k+1$ Ziffern. Die beiden zentralen Ziffern des Palindroms sind gleich.

Beweis: $Z = (p-1+1)^k = \sum \limits_{j=0}^{k} \binom{k}{j}\cdot (p-1)^{k-j}$ , also $z = \sum \limits_{j=0}^{k} \binom{k}{j}\cdot b^{k-j}$ .

Der größte Term $d_j := \binom{k}{j}$ in der Summe ist der Wert für $j = \frac{k \pm 1}{2}$ und beläuft sich auf $\binom{k}{\frac{k+1}{2}} = \frac{k\cdot (k-1)\cdots (k-\frac{k+1}{2}+1)}{(\frac{k+1}{2})!} = 2^k \cdot \frac{\Gamma\left(\frac{k+2}{2}\right)}{\sqrt{\pi} \cdot \Gamma\left(\frac{k+3}{2}\right)}$ . Dieser Wert ist nach Voraussetzung $< p - 1$ .

Anmerkung: Die vorstehend definierten Potenzzahl-Palindrome nennen wir Pascal’sche Palindrome, da sich die Ziffern ihrer Basis- $b$ -Darstellung in offensichtlicher Weise in Analogie zum Pascal’schen Dreieck ableiten lassen.

Beispiel: k = 4. Nach Voraussetzung muss $p > \binom{4}{2} + 1 = 7$ sein.
Sei $p=8$ , somit $b = 7$ . Wir erhalten $z = 8^4 = 4096$ , und weiter $Z = 1\cdot 7^4 + 4\cdot 7^3 + 6 \cdot 7^2 + 4\cdot 7^1 +1 \cdot 7^0$ , mithin $z = [14641]_7$ .
Sei $p=10$ , somit $b = 9$ . Nun ist $Z = 10^4 = 10000$ , sowie $Z = 1\cdot 9^4 + 4\cdot 9^3 + 6\dot 9^2 + 4\cdot 9^1 + 1\cdot 9^0$ , mithin $Z = [14641]_9$ .

k = 5. Nach Voraussetzung muss $p > \binom{5}{2} + 1 = 11$ sein.
Sei $p=12$ , somit $b = 11$ . Wir erhalten $Z = 12^5 = 248832$ und folglich $Z = 1\cdot 12^5 + 5\cdot 12^4 + 10 \cdot 12^3+ 10 \cdot 12^2 + 5\cdot 12^1 +1 \cdot 12^0$ , somit $Z = [15AA51]_{11}$ . Dabei haben wir anstelle von $10$ die „Ziffer“ $A$ gesetzt.
Sei $p=16$ , somit $b = 15$ . Wir erhalten $Z = 16^5 = 1048576$ und folglich $Z= 1\cdot 15^5 + 5\cdot 15^4 + 10 \cdot 15^3+ 10 \cdot 15^2 + 5\cdot 15^1 +1 \cdot 15^0$ , also $Z = [15AA51]_{15}$ . Auch hier haben wir die Ersetzung $10 \equiv A$ zugrunde gelegt,, wie im Hexadezimalsystem üblich.

7.8.2-(10) Jede Potenzzahl $Z = p^{2k}$ , $k \ge 1$ , $p > 3$ , ist ein echtes Palindrom in Basis $b = p^k- 1$ mit $3$ Ziffern.

Beweis: $Z = (p^k - 1 + 1)^2 = (p^k - 1)^2 + 2(p^k -1) + 1$ , mithin $Z = 1\cdot b^2 + 2\cdot b + 1\cdot b^0$ , also $z = 121_b$ mit $2 < p - 1 \le p^k - 1 = b$ . $\square$

7.8.2-(11) Jede Potenzzahl $Z = p^{2k+1}$ , $k > 1$ , $p > 3$ , ist ein echtes Palindrom in Basis $b = p^k- 1$ mit $3$ Ziffern.

Beweis: $Z = p\cdot (p^k - 1 + 1)^2 = p \cdot (p^k - 1)^2 + 2p\cdot (p^k -1) + p$ , mithin $Z = p\cdot b^2 + 2p \cdot b + p\cdot b^0$ , also $Z = [\,p\,(2p)\,p\,]_b$ mit $2p < (p-1)p \le p^2 - p \le p^k - p < p^k - 1 = b$ . $\square$

7.8.2-(12) Wenn für eine Zahl $Z$ gilt, $\frac{Z}{p}$ ist eine Potenzzahl $+ 1$ , also etwa $\frac{Z}{p} = q^k + 1$ , für ein $k > 0$ , und $p < q$ , dann ist $Z$ ein nicht-triviales Palindrom, und für $k > 1$ ein echtes Palindrom in Basis $b = q$ mit $k+1$ Stellen.

Beweis: Es gilt $Z = p\cdot q^k + p$ mit $p < q$ , und folglich $Z = [p_b][0]^{k-1}[p_b]$ . $\square$

Beispiel: $Z = 104,$ , $p = 4$ , $b = q = 5$ , $k = 2$ . Wir haben $\frac{Z}{4} = 5^2 + 1 = 26$ . und somit $Z = 4\cdot 5^2 + 4 = [404]_5$ .

7.8.2-(13) Wenn für eine Zahl $Z$ gilt, $Z$ ist eine Potenzzahl $\pm 1$ , also etwa $Z = q^k \pm 1$ , für ein $k > 0$ , dann ist $Z$ ein nicht-triviales Palindrom, und für $k > 1$ (im Falle des Pluszeichens) bzw. für $k > 2$ (im Falle des Minuszeichens) ein echtes Palindrom in Basis $b = q$ mit $k+1$ bzw. mit $k$ Stellen.

Beweis: Es gilt $Z = b^k \pm 1$ . Mithin haben wir $Z = [1][0]^{k-1}[1]$ mit $k+1$ Stellen im Falle des Pluszeichens sowie $Z = [(b-1)]^{k}$ mit $k$ Stellen im Falle des Minuszeichens. $\square$

Beispiele: $Z = 37$ , $b = q = 6$ , $k = 2$ . Wir haben $Z = 6^2 + 1 = [101]_6$ .
$Z = 35$ , $b = q = 6$ , $k = 2$ . Es gilt $Z =5\cdot 6^1 + 5 = [55]_6$ .
$Z = 80$ , $b = q = 3$ , $k = 4$ . Hier folgt $Z = 3^4 - 1 = 2\cdot 3^3 + 2\cdot 3^2 + 2\cdot 3^1 + 2\cdot 3^0 = [2222]_3$ .

7.8.3 Existenzsätze – notwendige Bedingungen

Ein notwendiges Existenzkriterium kann folgendermaßen formuliert werden:

7.8.3-(1) Wenn $Z$ ein Basis- $b$ -Palindrom ist, dann gilt mit $m =\log_b(Z)$
$(z + 1)^{\frac{1}{m+1}} \le b \le (z - 1)^{\frac{1}{m}}$ .

7.8.3-(2) Wenn mit $m =\log_b(Z)$
$(Z + 1)^{\frac{1}{m+1}} > b$ oder
$(Z - 1)^{\frac{1}{m}} < b$ ,
dann ist $Z$ kein Basis- $b$ -Palindrom mit $m+1$ Stellen.

Beispiel: $Z = 100$ , $b = 10$ , $m = 2$ .
Es gilt $(100 + 1)^{\frac{1}{2+1}} = 4,657 < 10$ , aber
$(100 - 1)^{\frac{1}{2}} = 9,9499 < 10$ , also ist 100 kein Dezimalpalindrom mit 3 Stellen.
$Z = 101$ , $b = 10$ , $m = 2$ .
$101 = 1\cdot 10^2 +0\cdot 10^1 + 1\cdot 10^0$ , also ist $Z$ ein Dezimalpalindrom. Demnach gilt $(101 + 1)^{\frac{1}{2+1}} = 4,672 \le 10 = (101 - 1)^{\frac{1}{2}}$ .

7.8.4 Exaktes Kriterium

7.8.4-(1) $Z$ ist ein Palindrom vom Grade $m+1$ genau dann, wenn es eine Basis $b$ ,
(i) $Z^{\frac{1}{m+1}} < b < Z^{\frac{1}{m}}$ gibt, so dass mit
(ii) $m = \left \lfloor \log_b(Z) \right \rfloor$ und
(iii) $n := \left \lfloor \frac{Z}{ b^{\left\lfloor \frac{m+1}{2} \right\rfloor}} \right\rfloor + b^{ \left\lfloor \frac{m+1}{2} \right\rfloor}$
$P_b(n) = Z$ gilt.

Beweis: Sei $Z$ ein Palindrom vom Grade $2 \cdot j = m+1$ . Dann gibt es $d_1, d_2, \cdots d_j$ , so dass $Z = d_1 \cdot b^{2j-1}+ \cdots + d_{j-1} \cdot b^{j+1} + d^j \cdot b^j + d_j \cdot b^{j-1} + \cdots + d_2 \cdot b^1 + d_1 \cdot b^0$ .

Nun ist $Z^{\frac{1}{2j}} < b$ sowie $Z^{\frac{1}{2j-1}} > b$ , ferner $n = \left \lfloor \frac{z}{b^j} \right \rfloor + b^j$ . Wenn wir hier $Z$ einsetzen, dann erhalten wir $n = d_1 \cdot b^{j-1}+ \cdots + d_{j-1} \cdot b^1 + d^j \cdot b^0 + b^j$ und somit $n = b^j + d_1 \cdot b^{j-1}+ \cdots + d_{j-1} \cdot b^1 + d^j \cdot b^0$ . Nach 7.3 gilt daher $P_b(n) = [\, d_1 \; d_2 \cdots d_j \; d_j \; \cdots d_2 \; d_1\, ]$ .

Im nächsten Schritt betrachten wir den Fall von Palindromen vom Grade $2 \cdot j -1 = m+1$ . Dann gibt es $d_1, d_2, \cdots d_j$ , so dass $Z = d_1 \cdot b^{2j-2}+ \cdots + d_{j-1} \cdot b^{j} + d^j \cdot b^{j-1} + \cdots + d_2 \cdot b^1 + d_1 \cdot b^0$ .

Es ergibt sich $Z^{\frac{1}{2j-1}} < b$ sowie $Z^{\frac{1}{2j-2}} > b$ , ferner $n = \left \lfloor \frac{z}{b^{j-1}} \right \rfloor + b^{j-1}$ . Wenn wir hier $Z$ einsetzen, dann erhalten wir $n = d_1 \cdot b^{j-1}+ \cdots + d_{j-1} \cdot b^1 + d^j \cdot b^0 + b^{j-1}$ und somit $n = (d_1 + 1) \cdot b^{j-1}+ \cdots + d_{j-1} \cdot b^1 + d^j \cdot b^0$ . Nach 7.3 gilt daher $P_b(n) = [\, d_1 \; d_2 \cdots d_j \; \cdots d_2 \; d_1\, ]$ . $\square$

7.8.4-(2) $Z$ ist ein Palindrom vom Grade $k+1 \ge m+1$ genau dann, wenn
(i) $k \le \left \lfloor \log_2(Z) \right \rfloor$ und eine Basis $b$ ,
(ii) $Z^{\frac{1}{k+1}} < b < Z^{\frac{1}{k}}$ existiert, so dass mit
(iii) $k = \left \lfloor \log_b(Z) \right \rfloor$ und
(iv) $n := \left \lfloor \frac{Z}{ b^{\left\lfloor \frac{k+1}{2} \right\rfloor}} \right\rfloor + b^{ \left\lfloor \frac{k+1}{2} \right\rfloor}$
$P_b(n) = Z$ gilt.

Beweis: Der Beweis läuft analog wir im Falle von 7.8.4-(1). Im Unterschied dazu müssen wir allerdings sukzessive alle Grade mit $k le _2(Z)$ betrachten. $\square$

7.9 Floor und Ceiling

Es geht hier um die Bestimmung des nächstgrößeren und des nächstkleineren Basis- $b$ -Palindroms zu einer gegebenen Zahl $Z$ . Wir definieren
(i) $m := \log_b(Z)$ und
(ii) $n := \left \lfloor \frac{Z}{ b^{\left\lfloor \frac{m+1}{2} \right\rfloor}} \right\rfloor + b^{ \left\lfloor \frac{m+1}{2} \right\rfloor}$ .

7.9-(1) Wenn $P_b(n) = Z$ , dann ist $Z$ ein Basis- $b$ -Palindrom.

7.9-(2) Wenn $P_b(n) < Z$ , dann ist $P_b(n)$ das größte Basis- $b$ -Palindrom $< Z$ und
$P_b(n+1)$ das kleinste Basis- $b$ -Palindrom $> Z$ .

7.9-(3) Wenn $P_b(n) > Z$ , dann ist $P_b(n)$ das kleinste Basis- $b$ -Palindrom $> Z$ und
$P_b(n-1)$ das größte Basis- $b$ -Palindrom $< Z$ .

Beispiele: $Z = 123456789$ hat im Dezimalsystem $9$ Ziffern. Wir erhalten folgerichtig $m = 8$ und
$n = \left \lfloor \frac{123456789}{10^{\left\lfloor \frac{8+1}{2} \right\rfloor}} \right\rfloor + 10^{ \left\lfloor \frac{8+1}{2} \right\rfloor}$ , also $n = 22345$ .
Damit ergibt sich $P_{10}(n) = 123454321_{10} < Z$ , also ist $Z$ kein Basis- $10$ -Palindrom. Ferner ist $123454321_{10}$ das größte Basis- $10$ -Palindrom $< Z$ und $P_{10}(n+1) = 123464321_{10}$ das kleinste Basis- $10$ -Palindrom $> Z$ .

$Z = 1234567890$ hat im Dezimalsystem $10$ Ziffern. Wir bekommen folgerichtig $m = 9$ und
$n = \left \lfloor \frac{1234567890}{10^{\left\lfloor \frac{9+1}{2} \right\rfloor}} \right\rfloor + 10^{ \left\lfloor \frac{9+1}{2} \right\rfloor}$ , also $n = 112345$ .
Daraus folgt $P_{10}(n) = 1234554321_{10} < Z$ , also ist $Z$ kein Basis- $10$ -Palindrom. Ferner ist $1234554321_{10}$ das größte Basis- $10$ -Palindrom $< Z$ und $P_{10}(n+1) = 1234664321_{10}$ das kleinste Basis- $10$ -Palindrom $> Z$ .

$Z = 1234553321$ hat im Dezimalsystem $10$ Ziffern. Wir erhalten $m = 9$ und
$n = \left \lfloor \frac{1234553321}{10^{\left\lfloor \frac{9+1}{2} \right\rfloor}} \right\rfloor + 10^{ \left\lfloor \frac{9+1}{2} \right\rfloor}$ , also $n = 112345$ .
Somit $P_{10}(n) = 1234554321_{10} > Z$ , also ist $Z$ kein Basis- $10$ -Palindrom. Ferner ist $1234554321_{10}$ das kleinste Basis- $10$ -Palindrom $> Z$ und $P_{10}(n-1) = 1234444321_{10}$ das größte Basis- $10$ -Palindrom $< Z$ .

7.10 Multiple Palindrome

Wir fragen: Wenn $P$ ein nicht-triviales Basis- $b$ -Palindrom ist, gibt es dann eine Basis $b'$ , so dass $P$ ein nicht-triviales Basis- $b'$ -Palindrom ist?

Im Allgemeinen ist das sicher nicht der Fall, z.B. ist $6$ ein nicht-triviales Basis- $5$ -Palindrom, aber für alle Basen $<5$ ist $6$ kein Palindrom. Es gibt aber auch positive Beispiele. Dazu der nächste Satz:

7.10-(1) Wenn $P$ drei Teiler hat, die nicht alle gleich sind, dann gibt es mindestens zwei unterschiedliche Basen $b_1$ und $b_2$ , so dass $P$ ein $b_1$ -Palindrom und zugleich ein $b_2$ -Palindrom ist.

Beweis: Sei $P = q_1 \cdot q_2 \cdot q_3$ mit $q_1 \le q_2 \le q_3$ . Wenn $q_1 \ne q_2$ , dann setzt man $b_1 = q_2 \cdot q_3 - 1$ sowie $b_2 = q_1 \cdot q_3 - 1$ und erhält $P = q_1 \cdot (q_2 \cdot q_3 - 1) + q_1$ , also $P = q_1 \cdot b_1 + q_1 = [(q_1)(q_1)]_b_1$ sowie $P = q_2 \cdot (q_1 \cdot q_3 - 1) + q_2$ , also $P = q_2 \cdot b_2 + q_2 = [(q_2)(q_2)]_b_2$ .

Wenn $q_2 \ne q_3$ , dann setzt man $b_3 = q_1 \cdot q_2 - 1$ sowie $b_2 = q_1 \cdot q_3 - 1$ und erhält $P = q_3 \cdot (q_1 \cdot q_2 - 1) + q_3$ , also $P = q_3 \cdot b_3 + q_3 = [(q_3)(q_3)]_b_3$ sowie $P = q_2 \cdot (q_1 \cdot q_3 - 1) + q_2$ , also $P = q_2 \cdot b_2 + q_2 = [(q_2)(q_2)]_b_2$ . $\square$

Beispiel: $P = 18 = 2 \cdot 3 \cdot 3$ , $b_1 = 3 \cdot 3 - 1= 8$ , $b_2 = 2 \cdot 3 - 1 = 5$ . Wir haben folglich $P = 2 \cdot 8 + 2 = [22]_8$ sowie $P = 3 \cdot 5 + 3 = [33]_5$ .

Wir können noch eine allgemeinere Feststellung treffen:

7.10-(2) Nach Satz 7.8.2-(4) gibt es zu jeder zusammengesetzten Zahl $Z > 6$ eine Basis $b_1 < \frac{Z}{2}$ , so dass $Z$ ein nicht-triviales Basis- $b_1$ -Palindrom ist. Auf der anderen Seite ist indessen jede Zahl $Z > 2$ ein schwaches Palindrom zur Basis $b_2 = Z - 1$ .

Beweis: Wir müssen nur zeigen, dass für $Z > 6$ stets $b_1 \ne b_2$ gilt. Tatsächlich erhalten wir mit $Z > 6$ unmittelbar $- \frac{Z}{2} < -3$ , und damit weiter $b_1 < \frac{Z}{2} = z - \frac{Z}{2} < Z - 3 = Z - 1 - 2 < Z - 1 = b_2$ . Demnach erweist sich $Z$ für alle zusammengesetzten $Z > 6$ als palindromisch zu zwei unterschiedlichen Basen. $\square$

7.11 Minimale Basen

Wir haben gesehen, dass mit geeigneter Wahl der Basis b jede Zahl ein Palindrom ist. Zahlen <= 2 sind stets triviale Palindrome, alle anderen sind mindestens schwache Palindrome, also Palindrome vom Grade >= 2.

In der nachfolgenden Tabelle sind für die ersten 32 Zahlen die minimalen Basen und die resultierenden Palindromgrade aufgelistet.

$Z$	Minimale Basis	Grad des Palindroms
0	2	1
1	2	1
2	3	1
3	2	2
4	3	2
5	2	3
6	5	2
7	2	3
8	3	2
9	2	4
10	3	3
11	10	2
12	5	2
13	3	3
14	6	2
15	2	4
16	3	3
17	2	5
18	5	2
19	18	2
20	3	3
21	2	5
22	10	2
23	3	3
24	5	2
25	4	3
26	3	3
27	2	5
28	3	4
29	4	3
30	9	2
31	2	5
32	7	2

Nun fragen wir nach der kleinsten Basis $b$ , so dass ein vorgegebenes $Z$ ein Palindrom ist.

Die nachfolgende Auflistung zeigt die Folge der zu den Zahlen $0,1,2,3, \cdots 140$ gehörenden minimalen Basen $b$ :

(121) $\begin{equation*} \begin{split} &2,2,3,2,3,2,5,2,3,2,3,10,5,3,6,2,3,2,5,18,3,\\&2,10,3,5,4,3,2,3,4,9,2,7,2,4,6,5,6,4,12,3,\\&5,4,6,10,2,4,46,7,6,7,2,3,52,8,4,3,5,28,4,9,\\&6,5,2,7,2,10,5,3,22,9,7,5,2,6,14,18,10,5,78,3,\\&8,3,5,11,2,6,28,5,8,14,3,6,2,46,18,11,8,5,2,3,\\&10,16,102,5,4,52,2,11,5,21,6,3,8,5,22,28,6,9,2,11,\\&3,11,6,5,4,5,2,7,2,3,10,21,11,66,6,9,136,7,138,13,\cdots \end{split} \end{equation*}$

Für viele der hier aufgelisten minimalen Basen ist das resultierende Palindrom nur schwach, hat also in der Basis- $b$ -Darstellung nur zwei Ziffern bzw. ist nur vom Grade 2. Die Frage nach der minimalen Basis mit der Eigenschaft Grad $> 2$ liegt daher nahe. Das ist zugleich die Frage nach der minimalen Basis, so dass das entsprechende Palindrom echt ist, also aus mindestens $3$ Ziffern besteht.

Wir listen für die ersten $140$ Zahlen die Folge der zugehörigen Basen mit Grad $> 2$ auf und notieren $0$ , falls es eine solche Basis nicht gibt.

(122) $\begin{equation*} \begin{split} &0,0,0,0,0,2,0,2,0,2,3,0,0,3,0,2,3,2,0,3,\\&2,0,3,0,4,3,2,3,4,0,2,0,2,4,0,5,6,4,0,3,\\&5,4,6,0,2,4,0,0,6,7,2,3,0,0,4,3,5,0,4,0,\\&6,5,2,7,2,0,5,3,0,0,7,5,2,6,0,0,0,5,0,3,8,\\&3,5,0,2,6,0,5,8,0,3,6,2,0,0,0,8,5,2,3,10,\\&0,0,5,4,0,2,0,5,0,6,3,8,5,0,0,6,9,2,0,3,\\&11,6,5,4,5,2,7,2,3,10,0,11,0,6,9,0,8,0,0,\cdots \end{split} \end{equation*}$

Schließlich ist noch die Folge der kleinsten Zahlen, die keine echten Palindrome sind von Interesse. Die ersten davon sind:

(123) $\begin{equation*} \begin{split} &0,1,2,3,4,6,8,11,12,14,18,19,22,24,30,32,35,39,44,47,48,\\&53,54,58,66,69,70,75,76,77,79,84,87,90,94,95,96,\\&102,103,106,108,110,115,116,120,132,137,139,140, \cdots \end{split} \end{equation*}$

Für diese Zahlen Z existieren somit keine Basen $b$ , so dass $Z$ als ein echtes Palindrom, also als ein Palindrom mit mindestens $3$ Ziffern darstellbar ist.

$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

1 Einführung

2 Dezimale Palindrome

2.1 Die rekursive Berechnung

2.2 Die direkte Berechnung

2.3 Ein einfacher Algorithmus zur Bestimmung von dezimalen Palindromen

2.4 Die Umkehrung der Palindromformel

2.5 Die Anzahlfunktion für dezimale Palindrome

2.6 Das Wachstum der Folge dezimaler Palindrome

3 Dezimale Palindrome mit einer ungeraden Anzahl von Stellen

3.1 Die rekursive Bestimmung

3.2 Die direkte Bestimmung

3.3 Die Umkehrfunktion

3.4 Die Anzahlfunktion

3.5 Das Wachstum der Folge

4 Dezimale Palindrome mit einer geraden Anzahl von Stellen

4.1 Die rekursive Berechnung

4.2 Die direkte Bestimmung

4.3 Die Umkehrfunktion

4.4 Die Anzahlfunktion

4.5 Das Wachstum der Folge

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

6 Binäre Palindrome

6.1 Rekursive Berechnung

6.2 Direkte Berechnung

6.3 Wachstum der Folge binärer Palindrome

6.4 Differenzen von binären Palindromen

6.5 Alternative Formel für die direkte Berechnung

6.6 Ein anschauliches Verfahren zur Bestimmung binärer Palindrome

6.7 Die Umkehrung der binären Palindromformel

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

6.9 Die Anzahl binärer Palindrome

6.10 Die Summe binärer Palindrome

7 Palindrome mit beliebigen Basen

7.1 Rekursive Berechnung

7.2 Direkte Berechnung

7.3 Anschauliche Bestimmung

7.4 Umkehrungsformel

7.5 Anzahlfunktion

7.6 Wachstum der Folge von Palindromen zur Basis b

7.7 Rechenoperationen mit Palindromen

7.7.1 Konstruktion von Palindromen

7.7.2 Summen von Palindromen

7.7.3 Differenzen von Palindromen

7.8 Existenz

7.8.1 Definitionen und einfache Folgerungen

7.8.2 Existenzsätze – hinreichende Bedingungen

7.8.3 Existenzsätze – notwendige Bedingungen

7.8.4 Exaktes Kriterium

7.9 Floor und Ceiling

7.10 Multiple Palindrome

7.11 Minimale Basen

Schreibe einen Kommentar Antwort abbrechen