Abscheuliche Zahl

In der linken Grafik sind die ersten 16 abscheulichen Zahlen und in der rechten Grafik die ersten 16 bösen Zahlen im Little-Endian-Binärformat abgebildet. Weiße Felder bedeuten 0, rote Felder 1. Die Zahlen werden von rechts nach links gelesen (zum Beispiel ist in der linken Grafik in der 12. Zeile die Darstellung für die 12. abscheuliche Zahl, nämlich 22=(10110)₂, von rechts nach links gelesen also (01101)₂). Beide Grafiken unterscheiden sich nur in den niedrigstwertigen Bits, also nur in der 1. Spalte (die restlichen Spalten 2 bis 5 sind in beiden Grafiken exakt gleich).

In der Zahlentheorie ist eine abscheuliche Zahl (englisch odious number) eine nichtnegative ganze Zahl, die im Dualsystem eine ungerade Zahl von Einsen hat.^[1] Nichtnegative ganze Zahlen, die nicht abscheulich sind, werden böse Zahlen (englisch evil numbers) genannt.

Der Mathematiker John Conway hat 1982 in seinem Buch Winning Ways for Your Mathematical Plays^[2] die Namen aufgrund eines Wortspiels etabliert. Die odious numbers haben eine odd, also ungerade Anzahl an Einsen, die evil numbers eine even, also gerade Anzahl an Einsen.

Beispiele

• Die Binärdarstellung (also die Darstellung im Dualsystem) von ${\displaystyle k=22}$ lautet:

${\displaystyle 22=16+0+4+2+0=1\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+0\cdot 2^{0}=(10110)_{2}}$

Diese Binärdarstellung besteht aus 3 Einsen. 3 ist eine ungerade Zahl und somit ist ${\displaystyle k=22}$ eine abscheuliche Zahl.

• Die Binärdarstellung von ${\displaystyle k=27}$ lautet:

${\displaystyle 27=16+8+0+2+1=1\cdot 2^{4}+1\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}=(11011)_{2}}$

Diese Binärdarstellung besteht aus 4 Einsen. 4 ist eine gerade Zahl und somit ist ${\displaystyle k=27}$ keine abscheuliche Zahl, sondern eine böse Zahl.

• Die ersten abscheulichen Zahlen, die kleiner als 100 sind, lauten:

1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 64, 67, 69, 70, 73, 74, 76, 79, 81, 82, 84, 87, 88, 91, 93, 94, 97, 98, … (Folge A000069 in OEIS)

Eigenschaften

• Sei ${\displaystyle a(n)}$ die ${\displaystyle n}$-te abscheuliche Zahl (mit ${\displaystyle a(0)=1}$).

Dann gilt:^[3]

${\displaystyle a(a(n))=2\cdot a(n)}$ für alle ${\displaystyle n}$

Beispiel:

Sei ${\displaystyle n=10}$. Obiger Zahlenfolge kann man entnehmen, dass ${\displaystyle a(n)=a(10)=21}$ ist. Weiters ist ${\displaystyle a(a(n))=a(a(10))=a(21)=42}$. Tatsächlich ist ${\displaystyle a(a(n))=42=2\cdot 21=2\cdot a(n)}$.

• Sei ${\displaystyle n}$ eine positive ganze Zahl. Dann gilt:^[4]

• Es gibt ein Vielfaches von ${\displaystyle n}$, die abscheulich und höchstens ${\displaystyle n\cdot (n+4)}$ ist.
• Zahlen, für die diese obere Grenze eng ist, sind genau die Mersenne-Zahlen mit geraden Exponenten, also Zahlen der Form ${\displaystyle 2^{2k}-1=4^{k}-1}$ (also 3, 15, 63, 255, … (Folge A024036 in OEIS)). Für diese Zahlen ist das kleinste abscheuliche Vielfache genau ${\displaystyle n\cdot (n+4)}$.

Beispiel:

Sei ${\displaystyle n=10}$. Dann kann man der obigen Zahlenfolge entnehmen, dass unter den Vielfachen von ${\displaystyle 10}$ erstmals die Zahl ${\displaystyle 70}$ abscheulich ist. Tatsächlich ist ${\displaystyle 70<10\cdot (10+4)=140}$.

Sei weiters ${\displaystyle n=15}$, also eine Mersenne-Zahl mit geradem Exponenenten (${\displaystyle n=15=2^{2\cdot 2}-1=2^{4}-1}$). Die kleinste abscheuliche Vielfache dieser Zahl ist ${\displaystyle 285}$. Tatsächlich ist ${\displaystyle 285=15\cdot (15+4)=15\cdot 19}$.

• Abscheuliche Zahlen geben die Positionen der Einser-Werte in der Thue-Morse-Folge an.^[5]

Beispiel:

Die Morse-Folge lautet:

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, … (Folge A010060 in OEIS)

Tatsächlich hat diese Folge, wenn man mit 0 zu zählen beginnt, an der 1., der 2., der 4., der 7., der 8., der 11. usw. Stelle eine Eins. Die abscheulichen Zahlen geben also die Stellen an, an denen die Morse-Folge eine Eins hat.

• Jede Zahl ${\displaystyle n}$ der Form ${\displaystyle n=2^{k}}$, also jede Zweierpotenz, ist eine abscheuliche Zahl.

Beweis:

Die Binärdarstellung einer Zweierpotenz hat nur eine einzige Stelle ungleich Null, nämlich an der Stelle ganz links. ${\displaystyle \Box }$

Beispiel:

Für die Binärdarstellung von ${\displaystyle n=2^{6}=64}$ gilt: ${\displaystyle n=64=1\cdot 2^{6}+0\cdot 2^{5}+0\cdot 2^{4}+0\cdot 2^{3}+0\cdot 2^{2}+0\cdot 2^{1}+0\cdot 2^{0}=(1000000)_{2}}$. Sie hat eine ungerade Anzahl an Einsen (weil in der Binärdarstellung eben nur ein einziger Einser vorhanden ist), also ist die Zahl eine abscheuliche Zahl.

• Jede Primzahl ${\displaystyle p\not =3}$ der Form ${\displaystyle p=2^{k}-1}$, also jede Mersenne-Primzahl, ist eine abscheuliche Zahl.

Beweis:

Die Binärdarstellung der Zahl ${\displaystyle p=2^{k}-1}$ besteht aus ${\displaystyle k}$ Einsen. Der Exponent ${\displaystyle k}$ einer Mersenne-Primzahl ist immer selbst eine Primzahl (siehe hier). Weil Primzahlen, abgesehen von ${\displaystyle k=2}$, immer ungerade sind, muss auch die Zahl ${\displaystyle k}$ ungerade sein. Somit besteht die Binärdarstellung der Zahl ${\displaystyle p=2^{k}-1}$ aus ${\displaystyle k}$, also aus einer ungeraden Anzahl von Einsen. Somit ist die Zahl ${\displaystyle p}$ eine abscheuliche Zahl.

Der Spezialfall mit ${\displaystyle k=2}$ ergibt die Mersenne-Primzahl ${\displaystyle p=2^{2}-1=3}$ und für die Binärdarstellung von ${\displaystyle p=3}$ gilt: ${\displaystyle p=3=2+1=1\cdot 2^{1}+1\cdot 2^{0}=(11)_{2}}$. Sie besteht aus 2 Einsen, die Zahl ${\displaystyle p=3}$ ist somit eine böse Zahl und wird deswegen von dieser Aussage ausgeschlossen. ${\displaystyle \Box }$

Beispiel:

Für die Binärdarstellung der 4. Mersenne-Primzahl ${\displaystyle n=127=2^{7}-1}$ gilt:

${\displaystyle n=127=64+32+16+8+4+2+1=1\cdot 2^{6}+1\cdot 2^{5}+1\cdot 2^{4}+1\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}=(1111111)_{2}}$.

Sie hat 7, also eine ungerade Anzahl an Einsen (weil in der Binärdarstellung eben nur Einsen vorhanden sind), also ist die Zahl eine abscheuliche Zahl.

• Sei ${\displaystyle d>2}$. Dann gelten die folgenden beiden Aussagen:^[6]

• Es gibt gleich viele böse wie abscheuliche Zahlen, deren Darstellung im Dualsystem jeweils ${\displaystyle d}$ Stellen haben.
• Die Menge der bösen Zahlen mit ${\displaystyle d}$ Stellen im Dualsystem und die Menge der abscheulichen Zahlen mit ${\displaystyle d}$ Stellen im Dualsystem haben dieselbe Summe, nämlich

${\displaystyle 3\cdot 2^{2d-4}-2^{d-3}}$

Beispiel:

Sei ${\displaystyle d=5}$.

Dann gibt es exakt 8 böse Zahlen, deren Binärdarstellung nur 5 Stellen hat, nämlich die folgenden:

17=(10001)₂, 18=(10010)₂, 20=(10100)₂, 23=(10111)₂, 24=(11000)₂, 27=(11011)₂, 29=(11101)₂ und 30=(11110)₂

Außerdem gibt es exakt 8 abscheuliche Zahlen, deren Binärdarstellung nur 5 Stellen hat, nämlich die folgenden:

16=(10000)₂, 19=(10011)₂, 21=(10101)₂, 22=(10110)₂, 25=(11001)₂, 26=(11010)₂, 28=(11100)₂ und 31=(11111)₂

Es gibt offensichtlich gleich viele böse wie abscheuliche Zahlen, deren Binärdarstellung nur 5 Stellen hat, nämlich 8, was die erste Aussage des obigen Satzes verlangt.

Weiters ist ${\displaystyle 3\cdot 2^{2d-4}-2^{d-3}=3\cdot 2^{2\cdot 5-4}-2^{5-3}=3\cdot 2^{6}-2^{2}=3\cdot {64}-4=192-4=188}$.

Tatsächlich gilt für die Summe der 8 bösen Zahlen, deren Binärdarstellung nur 5 Stellen hat:

${\displaystyle 17+18+20+23+24+27+29+30=188}$

Für die Summe der 8 abscheulichen Zahlen, deren Binärdarstellung nur 5 Stellen hat, gilt:

${\displaystyle 16+19+21+22+25+26+28+31=188}$

Die Summe ist gleich, wie im obigen Satz angegeben.

• Sei die Nim-Addition, ${\displaystyle \oplus }$, wie folgt definiert:

Für jedes Paar ganzzahliger, nichtnegativer Zahlen ${\displaystyle a,b\in \mathbb {N} }$ gilt: ${\displaystyle (a)_{10}\oplus (b)_{10}=(a)_{2}+(b)_{2}}$ mit ${\displaystyle 0+0=0}$, ${\displaystyle 0+1=1+0}$, ${\displaystyle 1+1=0}$ (im letzten Fall aber ohne Übertrag auf die nächsthöhere Stelle).

Dann gilt:^[2]

Die bösen und abscheulichen Zahlen verhalten sich unter „Nim-Addition“, ${\displaystyle \oplus }$, wie die geraden und ungeraden Zahlen unter „normaler“ Addition. Also gilt:

• böse ${\displaystyle \oplus }$ böse = böse
• abscheulich ${\displaystyle \oplus }$ abscheulich = böse
• böse ${\displaystyle \oplus }$ abscheulich = abscheulich ${\displaystyle \oplus }$ böse = abscheulich

Beispiel 1:

Weiter oben wurde gezeigt, dass ${\displaystyle 27=(11011)_{2}}$ eine böse Zahl ist, weiters ist auch ${\displaystyle 51=(110011)_{2}}$ eine böse Zahl:

${\displaystyle 27_{10}\oplus 51_{10}=(11011)_{2}+(110011)_{2}=(101000)_{2}}$

Das Ergebnis hat eine gerade Anzahl an Einsen, ist also eine böse Zahl.

Beispiel 2:

Weiter oben wurde gezeigt, dass ${\displaystyle 22=(10110)_{2}}$ eine abscheuliche Zahl ist, weiters ist auch ${\displaystyle 52=(110100)_{2}}$ eine abscheuliche Zahl:

${\displaystyle 22_{10}\oplus 52_{10}=(10110)_{2}+(110100)_{2}=(100010)_{2}}$

Das Ergebnis hat eine gerade Anzahl an Einsen, ist also eine böse Zahl.

Beispiel 3:

Weiter oben wurde gezeigt, dass 51 eine böse und 52 eine abscheuliche Zahl ist:

${\displaystyle 51_{10}\oplus 52_{10}=(110011)_{2}+(110100)_{2}=(000111)_{2}}$

Das Ergebnis hat eine ungerade Anzahl an Einsen, ist also eine abscheuliche Zahl.

• Es sind ein paar Zahlen bekannt, die der Summe ihrer abscheulichen Teiler entsprechen. Diese lauten:^[6]

28, 496, 8128, 415800, 2096128, 33550336, 8589869056 (Folge A212302 in OEIS)

Bis auf 415800 und 2096128 sind alle diese Zahlen perfekte Zahlen. Man könnte obige Zahlen abscheulich-perfekte Zahlen nennen.^[7]

Beispiel:

Die Binärdarstellung der abscheulichen Zahl ${\displaystyle n=28}$ lautet:

${\displaystyle n=28=16+8+4+0+0=1\cdot 2^{4}+1\cdot 2^{3}+1\cdot 2^{2}+0\cdot 2^{1}+0\cdot 2^{0}=(11100)_{2}}$

Die Zahl ${\displaystyle n=28}$ hat die folgenden Teiler: ${\displaystyle d_{1}=1=(1)_{2},d_{2}=2=(10)_{2},d_{3}=4=(100)_{2},d_{4}=7=(111)_{2},d_{5}=14=(1110)_{2}}$. Alle Teiler haben in ihrer Binärdarstellung eine ungerade Zahl von Einsen, somit sind alle Teiler abscheuliche Zahlen. Also hat die abscheuliche Zahl ${\displaystyle n=28}$ nur abscheuliche Teiler, die in Summe selbst ${\displaystyle 28}$ ergeben.

• Lässt man die letzte Stelle (also das letzte Bit) der Binärdarstellung der abscheulichen Zahlen weg, so erhält man die Menge der natürlichen Zahlen, also 0, 1, 2, 3, ...^[8]

• Die Menge der nichtnegativen ganzen Zahlen kann in die Menge der bösen Zahlen und in die Menge der abscheulichen Zahlen eindeutig aufgeteilt werden. Diese haben gleiche Multimengen von paarweisen Summen.^[9]

• In der Informatik haben abscheuliche Zahlen eine ungerade Parität.

Literatur

• Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Winning Ways for Your Mathematical Plays, Volume 1. 2. Auflage. A K Peters, Wellesley, Massachusetts 2001, ISBN 1-56881-130-6, S. 276. 

Weblinks

• Eric W. Weisstein: Odious Number. In: MathWorld (englisch).
• odious numbers auf Numbers Aplenty

Einzelnachweise

1. Neil Sloane: Sequenz A000069: Odious numbers: numbers with an odd number of 1's in their binary expansion, auf On-Line Encyclopedia of Integer Sequences
2. Winning Ways for Your Mathematical Plays, Volume 1, S. 110 (PDF; 18 MB)
3. Jean-Paul Allouche, Benoit Cloitre, V. Shevelev: Beyond odious and evil. Aequationes Mathematicae 90, 2015, S. 341–353, abgerufen am 13. April 2024. 
4. Johannes F. Morgenbesser, Jeffrey Shallit, Thomas Stoll: Thue–Morse at multiples of an integer. Journal of Number Theory 131 (8), 2011, S. 1498–1512, abgerufen am 13. April 2024. 
5. Émilie Charlier, Célia Cisternino, Adeline Massuir: State Complexity of the Multiples of the Thue-Morse Set. Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification, Electron. Proc. Theor. Comput. Sci. (EPTCS), 2019, S. 34–49, abgerufen am 13. April 2024. 
6. odious numbers auf Numbers Aplenty
7. Neil Sloane: A212302: Numbers k whose sum of proper odious divisors (A000069) equals k., auf On-Line Encyclopedia of Integer Sequences
8. Neil Sloane: Sequenz A001969: Evil numbers: nonnegative integers with an even number of 1's in their binary expansion, auf On-Line Encyclopedia of Integer Sequences
9. Joachim Lambek, Leo Moser: On some two way classifications of integers. Canadian Mathematical Bulletin 2 (2), 1959, S. 85–89, abgerufen am 13. April 2024.