Böse Zahl

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

In der linken Grafik sind die ersten 16 bösen Zahlen und in der rechten Grafik die ersten 16 abscheulichen 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. böse Zahl, nämlich 23=(10111)₂, von rechts nach links gelesen also (11101)₂). 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). Von oben nach unten gelesen ergibt die 1. Spalte die Morse-Folge (von oben nach unten gelesen 0-1-1-0-1-0-0-1-1-0-0-1-...).

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

Beispiele

• Die Binärdarstellung (also die Darstellung im Dualsystem) von $k=23$ lautet:

$23=16+0+4+2+1=1\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}=(10111)_{2}$

Diese Binärdarstellung besteht aus 4 Einsen. 4 ist eine gerade Zahl und somit ist $k=23$ eine böse Zahl.

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

$25=16+8+0+0+1=1\cdot 2^{4}+1\cdot 2^{3}+0\cdot 2^{2}+0\cdot 2^{1}+1\cdot 2^{0}=(11001)_{2}$

Diese Binärdarstellung besteht aus 3 Einsen. 3 ist eine ungerade Zahl und somit ist $k=25$ keine böse Zahl, sondern eine abscheuliche Zahl.

• Die ersten bösen Zahlen, die kleiner als 100 sind, lauten:

0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 95, 96, 99, … (Folge A001969 in OEIS)

Eigenschaften

• 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 $23=(10111)_{2}$ eine böse Zahl ist, weiters ist auch $51=(110011)_{2}$ eine böse Zahl:

$23_{10}\oplus 51_{10}=(10111)_{2}+(110011)_{2}=(100100)_{2}$

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

Beispiel 2:

Weiter oben wurde gezeigt, dass $25=(11001)_{2}$ eine abscheuliche Zahl ist, weiters ist auch $52=(110100)_{2}$ eine abscheuliche Zahl:

$25_{10}\oplus 52_{10}=(11001)_{2}+(110100)_{2}=(101101)_{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 gibt magische Quadrate, die nur aus bösen Zahlen bestehen. Das magische Quadrat mit den kleinsten bösen Zahlen ist das folgende:

18	45	9
15	24	33
39	3	30

• Lässt man die letzte Stelle (also das letzte Bit) der Binärdarstellung der bösen Zahlen weg, so erhält man die Menge der natürlichen Zahlen, also 0, 1, 2, 3, ...

• Böse Zahlen geben die Positionen der Nullwerte in der Thue-Morse-Folge an und werden daher auch Thue-Morse-Menge genannt.

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 0., der 3., der 5., der 6., der 9., der 10. usw. Stelle eine Null. Die bösen Zahlen geben also die Stellen an, an denen die Morse-Folge eine Null hat.

• Es sind Zahlen bekannt, die der Summe ihrer bösen Teiler entsprechen. Diese lauten:

18, 476, 1484, 1988, 2324, 3164, 4172, 4564, 5516, 7196, 7364, 7532, 8036, 8876, 9716, 9772, 10052, 10444, 10892, 11956, 12572, 13076, 13412, 14084, 16604, 16772, 18004, 19866, 20692, 21328, 21364, 21644, 22316, 22988, 23492, 23884, 23996, 24164, 24668, 24836, … (Folge A230587 in OEIS)

Man könnte obige Zahlen böse-perfekte Zahlen nennen.

Beispiel:

Die Binärdarstellung der bösen Zahl $n=18$ lautet:

$n=18=16+0+0+2+0=1\cdot 2^{4}+0\cdot 2^{3}+0\cdot 2^{2}+1\cdot 2^{1}+0\cdot 2^{0}=(10010)_{2}$

Die Zahl $n=18$ hat die folgenden Teiler: $d_{1}=1=(1)_{2},d_{2}=2=(10)_{2},d_{3}=3=(11)_{2},d_{4}=6=(110)_{2},d_{5}=9=(1001)_{2}$. Die Teiler $3$, $6$ und $9$ haben in ihrer Binärdarstellung eine gerade Zahl von Einsen, sind also böse Zahlen und es gilt: $3+6+9=18$. Somit ist $18$ die Summe ihrer bösen Teiler.

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

• Die Aufteilung der Zahlen von $0$ bis $2^{k}-1$ für alle natürlichen Zahlen $k\in \mathbb {N}$ in böse und abscheuliche Zahlen bietet eine Lösung für das Prouhet-Tarry-Escott-Problem, Zahlenmengen zu finden, deren Potenzsummen bis zur $k$-ten Potenz gleich sind.

Diese Aussage wurde vom französischen Mathematiker Eugène Prouhet im 19. Jahrhundert bewiesen.

• In der Informatik haben böse Zahlen eine gerade 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: Evil Number. In: MathWorld (englisch).
• evil numbers auf Numbers Aplenty