Abscheuliche Zahl

Vorlage:Mehrere Bilder In der Zahlentheorie ist eine abscheuliche Zahl (englisch odious number) eine nichtnegative ganze Zahl, die im Dualsystem eine ungerade Zahl von Einsen hat. 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 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 $k=22$ lautet:

$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 $k=22$ eine abscheuliche Zahl.

• Die Binärdarstellung von $k=27$ lautet:

$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 $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, … (Vorlage:OEIS)

Eigenschaften

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

Dann gilt:

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

Beispiel:

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

• Sei $n$ eine positive ganze Zahl. Dann gilt:

• Es gibt ein Vielfaches von $n$, die abscheulich und höchstens $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 $2^{2k}-1=4^k-1$ (also 3, 15, 63, 255, … (Vorlage:OEIS)). Für diese Zahlen ist das kleinste abscheuliche Vielfache genau $n\cdot (n+4)$.

Beispiel:

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

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

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

Beispiel:

Die Morse-Folge lautet:

0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, … (Vorlage: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 $n$ der Form $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. $◻$

Beispiel:

Für die Binärdarstellung von $n=2^6=64$ gilt: $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 $p=3$ der Form $p=2^k-1$, also jede Mersenne-Primzahl, ist eine abscheuliche Zahl.

Beweis:

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

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

Beispiel:

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

$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 $d>2$. Dann gelten die folgenden beiden Aussagen:

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

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

Beispiel:

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

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

$16+19+21+22+25+26+28+31=188$

Die Summe ist gleich, wie im obigen Satz angegeben.

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

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

Dann gilt:

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

• böse $\oplus$ böse = böse
• abscheulich $\oplus$ abscheulich = böse
• böse $\oplus$ abscheulich = abscheulich $\oplus$ böse = abscheulich

Beispiel 1:

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

$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 $22=(10110{)}_2$ eine abscheuliche Zahl ist, weiters ist auch $52=(110100{)}_2$ eine abscheuliche Zahl:

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

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

28, 496, 8128, 415800, 2096128, 33550336, 8589869056 (Vorlage:OEIS)

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

Beispiel:

Die Binärdarstellung der abscheulichen Zahl $n=28$ lautet:

$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 $n=28$ hat die folgenden Teiler: $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 $n=28$ nur abscheuliche Teiler, die in Summe selbst $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, ...

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

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

Literatur

• Vorlage:Literatur

Weblinks

• Vorlage:MathWorld
• odious numbers auf Numbers Aplenty