PALINDROME

1. Wörter und Wortgebilde

Ein Wort, das von vorn wie von hinten gelesen gleich ist, nennt man "Palindrom", im Plural "Palindrome".

Beispiele für Palindrome (ohne Anspruch auf Vollständigkeit):

A, B, C, D, …, X, Y, Z	Jeder Buchstabe für sich genommen ist ein Palindrom.
A	„a“ im Sinne von „zu“, z.B. „das Kilo a 30 Euro“ (eigentlich mit Gravis-Akzent „à“ (den wir uns hier schenken). ODER: Abkürzung für anno (das Jahr) ODER: Abkürzung für am (bei Ortsangaben)
S	„s“ Abkürzung für „siehe“ (bei Verweisen in Texten)
AA	Kfz-Kennzeichen von Aalen. ODER: Abkürzung für ad acta
DD	Kfz-Kennzeichen von Dresden.
HH	Kfz-Kennzeichen von Hamburg.
NUN
ABBA	Die schwedische Musikgruppe.
ANNA
OTTO
EBBE
ELLE
NEBEN
ROTOR
RADAR
KAJAK
RETTER
RENNER
RENTNER
REITTIER
RELIEFPFEILER
RETSINAKANISTER

Etwas gekünstelt (findet man nicht im Duden), aber durchaus sinnhaft:

TONNOT	Ein Problem, was Sänger und Musiker gelegentlich, alle anderen fast immer haben. ODER: Wenn man keinen Ton mehr hat, aber welchen braucht(z.B. zum Brennen von Tonziegeln)
NOTTON	Die simpelste Form eines Hilferufs. ODER: Die Menge an Ton, die man sich in guten Zeiten aufbewahrt hat (z.B. zum Brennen von Tonziegeln)
REGALLAGER	Spricht für sich selbst.
LAGERREGAL	Spricht für sich selbst.
NEBELLEBEN	Was man eben so tut im Nebel.
NENNERRENNEN	Vielleicht ein Wettkampf im Bruchrechnen?

Einige wenige Beispiele aus anderen Sprachen:

REINIER	Niederländischer Vorname
EXE	Kurzform für ein ausführbares Programm (executable)
E	lat. für „seit“, ital. für „ist“
ESSE	Herd, Feuerstelle etc., lat. für „sein“
ERRARRE	lat. für „sich irren“! Ist doch gar kein Palindrom, weil falsch geschrieben. Es darf trotzdem als solches gelten, denn: Errare humanum est.
OVO	lat. für das Ei (genauer, [vom] Ei [Ablativ])
SUMMUS	lat. für das Höchste, das Absolute
SUMYMUS	Der Name dieser Website

Meines Wissens das längste Palindrom im deutscher Sprache: RETSINAKANISTER (von den unten aufgelisteten einmal abgesehen).

Sofern man nicht den Anspruch auf Sinnhaftigkeit und Originalität legt, kann man neue Palindrome auch aus bekannten Palindromen konstruieren (unter gewissen Bedingungen) und bekommt so Wörter größerer Länge:

Ist P ein Palindrom, so ist auch PP (PPP, PPPP, usw.) ein Palindrom (trivial, OTTO, OTTO è OTTOOTTO).

Sind P und Q Palindrome, so sind auch PQP und QPQ Palindrome usw.

Beispiele hierfür (inhaltlich Nonsens, aber syntaktisch korrekt):

P=ROTOR

Q=OTTO

PQP=ROTOROTTOROTOR

QPQ=OTTOROTOROTTO

P=REITTIER

Q=RADAR

PQP=REITTIERRADARREITIER

QPQ=RADARREITTIERRADAR

P= RETTER

Q=RETSINAKANISTER

PQP= RETTERRETSINAKANISTERRETTER

QPQ=RETSINAKANISTERRETTERRETSINAKANISTER

(im letzten Falle das Palindrom mit 36 Buchstaben etwa dafür Verwendung finden, „die Belohnung des Retters der Retsinakanister, nämlich ein Retsinakanister“, in einem Wort zu beschrieben)-

Ist W ein Wort, und W' das umgedrehte - von hinten gelesene - Wort, so sind WW' und W'W jeweils Palindrome (z.B. ROT, TOR ==> ROTTOR, TORROT).

Beispiele hierfür (nicht immer sinnhaft):

W=LAGER	W‘=REGAL	WW‘=LAGERREGAL W‘W=REGALLAGER
W=TON	W‘=NOT	WW‘=TONNOT W‘W=NOTTON
W=REGEN	W‘=NEGER	WW‘=REGENNEGER W’W=NEGERREGEN
W=NEBEL	W‘=LEBEN	WW‘=NEBELLEBEN W’W=LEBENNEBEL
W=REIT	W‘=TIER	WW‘=REITTIER W’W=TIERREIT (z.B. als Präfix wie in TIERREITANSTALT)
W=NENNER	W‘=RENNEN	WW‘=NENNERRENNEN W’W=RENNENNENNER (z.B. der gemeinsame Nenner mehrerer Rennen)
W=REBE	W‘=EBER	WW‘=REBEEBER W’W=EBERREBE (so könnte eine Rebensorte heißen)

Anmerkung: Das Wort NEGER in obigem Falle gilt heutzutage als politisch nicht korrekt. Es wird hier nicht als Bezeichnung für einen Menschen schwarzer Hautfarbe verwendet, sondern ist nur zu verstehen als ein syntaktisch richtiges Wort der deutschen Sprache (wie es im Duden steht).

Ferner sind für ein Palindrom P auch WPW' und W'PW Palindrome (z.B. ROT, OTTO, TOR à ROTOTTOTOR, TOROTTOROT)

Beispiele für zusammengesetzte Palindrome (inhaltlich meist Nonsens, aber syntaktisch korrekt):

W=NEBEL	P=RADAR	W‘=LEBEN	WPW‘=NEBELRADARLEBEN W’PW=LEBENRADARNEBEL
W= ROT	P=REGALLAGER	W‘=TOR	WPW‘=ROTREGALLAGERTOR W‘PW=TORREGALLAGERROT
W= REGEN	P=RADAR	W‘=NEGER	WPW‘=REGENRADARNEGER W‘PW=NEGERRADARREGEN
W= LAGER	P=ROTOR	W‘=REGAL	WPW‘=LAGERROTORREGAL W‘PW=REGALROTORLAGER
W= LAGER	P=NEBEN	W‘=REGAL	WPW‘=LAGERNEBENREGAL W‘PW=REGALNEBENLAGER
W=TON	P=REITTIER	W‘=NOT	WPW‘=TONREITTIERNOT W‘PW=NOTREITTIERTON
W= LAGER	P=RELIEFPFEILER	W‘=REGAL	WPW‘=LAGERRELIEFPFEILERREGAL W‘PW=REGALRELIEFPFEILERLAGER
W=TON	P=LAGERREGAL	W‘=NOT	WPW‘=TONLAGERREGALNOT W’PW=NOTLAGERREGALTON
W=NEBEL	P=REGALRELIEFPFEILERLAGER	W‘=LEBEN	WPW‘=NEBELREGALRELIEFPFEILERLAGERLEBEN W’PW=LEBENREGALRELIEFPFEILERLAGERNEBEL

Die Liste kann nach Belieben fortgesetzt werden.

Von Wörtern zu Sätzen: Einige Beispiele für Palindrom-Sätze:

Ein Neger mit Gazelle, zagt im Regen nie	Hier gilt das oben Gesagte
Die Liebe ist Sieger, stets rege ist sie bei Leid
Nie solo sein.	Der Wahlspruch aller Singles

Hier noch ein Beispiel für einen englischen Palindrom-Satz:

A MAN A PLAN A CANAL PANAMA	Die moderne amerikanische Form von Cäsars: Veni, vidi, vici

2. Zahlen

Eine Zahl, die bei Umkehrung der Ziffernfolge unverändert bleibt, nennt man Palindrom. Eine andere Bezeichnung dafür ist einfach „symmetrische Zahl“.

Beispiele: 11, 121, 1221, 44544, 92329, 7125217, usw.

Ob eine bestimmte Zahl Palindrom ist oder nicht, hängt natürlich ab vom verwendeten Ziffernsystem. In der folgenden Tabelle sind einige Zahlen in verschiedenen Ziffernsystemen aufgelistet. Die Palindrome sind farbig hervorgehoben.

Basis 10 (Dezimal )	Basis 2 (Binär)	Basis 3	Basis 5	Basis 8 (Oktal)	Basis 16 (Hexadezimal)
0	0	0	0	0	0
1	1	1	1	1	1
2	10	2	2	2	2
3	11	10	3	3	3
4	100	11	4	4	4
5	101	12	10	5	5
6	110	20	11	6	6
7	111	21	12	7	7
8	1000	22	13	10	8
9	1001	100	14	11	9
10	1010	101	20	12	A
11	1011	102	21	13	B
12	1100	110	22	14	C
13	1101	111	23	15	D
14	1110	112	24	16	E
15	1111	120	30	17	F
16	10000	121	31	20	10
17	10001	122	32	21	11
18	10010	200	33	22	12
19	10011	201	34	23	13
20	10100	202	40	24	14
21	10101	210	41	25	15
22	10110	211	42	26	16
23	10111	212	43	27	17
24	11000	220	44	30	18
25	11001	221	100	31	19
26	11010	222	101	32	1A
27	11011	1000	102	33	1B
28	11100	1001	103	34	1C
29	11101	1002	104	35	1D
30	11110	1010	110	36	1E
31	11111	1011	111	37	1F
32	100000	1012	112	40	20
33	100001	1020	113	41	21
34	100010	1021	114	42	22
55	110111	2001	210	67	37
99	1100011	10200	344	143	63
100	1100100	10201	400	144	64
101	1100101	10202	401	145	65
200	11001000	21102	1300	310	C8
499	111110011	200111	3444	763	1F3
500	111110100	200112	4000	764	1F4
501	111110101	200120	4001	765	1F5
502	111110110	200121	4002	766	1F6
503	111110111	200122	4003	767	1F7
504	111111000	200200	4004	770	1F8
511	111111111	200221	4021	777	1FF
512	1000000000	200222	4022	1000	200
513	1000000001	201000	4023	1001	201
514	1000000010	201001	4024	1002	202
524	1000001100	201102	4044	1014	20C

Im einfachsten Falle betrachtet man die Zahlen im Binärsystem (nur die Ziffern 0 und 1). Nichtsdestotrotz schreibt man die Zahlen dezimal, so sind wir es gewohnt. Z.B. ist die Nummer 16 in dieser Folge die Zahl 73=1001001. Die ersten aufeinanderfolgenden binären Palindrome sind: 0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63,65, 73, 85, 93, 99, … (s. The On-Line Encyclopedia of Integer Sequences, Link: http://oeis.org/A006995 [Numbers whose binary expansion is palindromic] für weitere Zahlen).

Man kann das n-te binäre Palindrom bestimmen, ohne alle in Frage kommenden Zahlen im Einzelnen betrachten zu müssen. Z.B. ist das 1000ste binäre Palindrom die Zahl 249903=111101000000101111₍₂₎, 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 schreiben es im Folgenden kurz – gibt es nicht, doch kann man in speziellen Fällen das n-te binäre Palindrom leicht berechnen, z.B. gilt

Demnach ist also =262657 das 1025ste binäre Palindrom. Die unmittelbar vorhergehenden 1024sten und 1023sten Palindrome sind 262145 und 262143.

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

wobei und die Parameter folgendermaßen bestimmt werden:

:
:
:
:

Eine weitere Möglichkeit zur direkten Bestimmung des n-ten binären Palindroms ist diese (für

wobei und oder, was das gleiche bedeutet, der Parameter nach folgender Fallunterscheidung eingesetzt wird:

Hiermit berechnete größere binäre Palindrome sind in der nachfolgenden Tabelle aufgelistet.

Nr.	Palindrom
1	0
2	1
3	3
4	5
5	7
6	9
7	15
8	17
9	21
10	27
100	2313
1 000	`249903`
10 000	`24183069`
100 000	`2258634081`
1 000 000	`249410097687`
10 000 000	`24350854001805`
100 000 000	`2229543293296319`
1 000 000 000	`248640535848971067`
10 000 000 000	`24502928886295666773`

Die Differenzen aufeinander folgender Palindrome bilden eine interessante Folge: 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, … (s. The On-Line Encyclopedia of Integer Sequences, Link: http://oeis.org/A164126). Die 2 und die 6 treten dabei unendlich oft als Folgenglieder auf. Bezeichnen wir die Glieder mit so gilt ab m

und ab m

Die allgemeine Formel für lässt sich aus der obigen Formel für ableiten. Mit und ergibt sich

sofern oder . In den beiden Sonderfällen und ist .

Die Folge lässt sich auch rekursiv berechnen (wie stets, gesetzt)

Die Rekursionsbeziehung gilt ab , die Bezugswerte für sind 1, 2, 2, 2. Der folgenden Umschreibung kann man unmittelbar entnehmen, wie sich nachfolgende Glieder aus den vorhergehenden bestimmen lassen.

, für

Wenn man ab einer Stelle jeweils die nächsten Folgenglieder nebeneinander schreibt, so sieht man, dass ein symmetrisches Muster entsteht. Für 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 palindromische Muster. Tatsächlich gilt allgemein

, für

Wegen für oder sowie für , 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 direkt aus den Gliedern mit bestimmt werden, ergibt sich gleichfalls

für .

Demnach bilden auch die Zahlen ab mit den folgenden Gliedern symmetrische Muster von Elementen, begrenzt mit je einer 2 und die 6 in der Mitte. Das entsprechende symmetrische Tupel für lautet (2, 24, 12, 24, 6, 24, 12, 24, 2).

Wenn man die Folge nach den symmetrischen Mustern ordnet und untereinanderschreibt, erkennt man, dass das n-te Folgenglied auch einfacher berechnet werden kann.

m	Folgenglieder
m	Folgenglieder
0	-
0	1
1	2
1	2
2	2 2
2	6 2
3	4 6 4 2
3	12 6 12 2
4	8 12 8 6 8 12 8 2
4	24 12 24 6 24 12 24 2
5	16 24 16 12 16 24 16 6 16 24 16 12 16 24 16 2
5	48 24 48 12 48 24 48 6 48 24 48 12 48 24 48 2

Es ergibt sich die folgende Darstellung:

Kompakter geschrieben folgt daraus

Das kann man weiter vereinfachen zu

Dabei steht für die Funktion, die den größten gemeinsamen Teiler von a und b berechnet.

Eine noch etwas kompaktere Form ist die Folgende

Kehren wir zurück zur Folge der Palindrome. Für die obige Formel zur Berechnung es n-ten binären Palindroms bekommen wir wegen

nun eine Alternative auf Basis der Differenzenfolge. Man erhält mit

Ist p ein vorgegebenes binäres Palindrom, so stellt sich die Frage, das Wievielte in der geordneten Folge der Palindrome es ist. Auch darauf gibt es eine Antwort. Für gilt mit :

Das kann man wegen für umformen zu

Zwei andere Schreibweisen ergeben sich mittels der Ersetzung

Daraus folgt z.B., dass p=1011951=11010010110100011₂ das 2012-te binäre Palindrom ist. Eine weitere Frage, die sich hier unmittelbar anschließt: Wenn eine beliebige natürliche Zahl n vorgegeben ist, wie bestimmt sich dann das größte binäre Palindrom kleiner oder gleich n? Die Antwort gibt die folgende Formel:

wobei

Wie man sieht, gilt für die hier definierte Funktion F

bzw.

Dabei steht Reversal(x) für die Umkehrung des Bitmusters von x.

Weiter kann man nun fragen, wie viele Palindrome <2ⁿ es gibt und wie groß die Summe dieser Palindrome ist. Die Anzahl der Palindrome zwischen 2^n-1 und 2ⁿ kann man leicht bestimmen. Es gilt (für

Damit berechnet man die Anzahl der Palindrome <2ⁿ zu für

Die Summe der Palindrome zwischen 2^n-1 und 2ⁿ ergibt sich ferner für zu

Und schließlich erhalten wir damit die Summe der Palindrome <2ⁿ für zu

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

wobei

Die beiden in obiger Formel stehenden Summen kann man auswerten und findet

Damit wird der Ausdruck zu

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

so muss man zunächst berechnen und kann dann die vorstehende Formel anwenden.