Abscheuliche Zahl
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/53/First_16_odious_numbers_in_little-endian_binary.svg/120px-First_16_odious_numbers_in_little-endian_binary.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b1/First_16_evil_numbers_in_little-endian_binary.svg/120px-First_16_evil_numbers_in_little-endian_binary.svg.png)
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)2, von rechts nach links gelesen also (01101)2). 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 lautet:
- Diese Binärdarstellung besteht aus 3 Einsen. 3 ist eine ungerade Zahl und somit ist eine abscheuliche Zahl.
- Die Binärdarstellung von lautet:
- Diese Binärdarstellung besteht aus 4 Einsen. 4 ist eine gerade Zahl und somit ist 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 die -te abscheuliche Zahl (mit ).
- Dann gilt:[3]
- für alle
- Beispiel:
- Sei . Obiger Zahlenfolge kann man entnehmen, dass ist. Weiters ist . Tatsächlich ist .
- Beispiel:
- für alle
- Sei eine positive ganze Zahl. Dann gilt:[4]
- Es gibt ein Vielfaches von , die abscheulich und höchstens ist.
- Zahlen, für die diese obere Grenze eng ist, sind genau die Mersenne-Zahlen mit geraden Exponenten, also Zahlen der Form (also 3, 15, 63, 255, … (Folge A024036 in OEIS)). Für diese Zahlen ist das kleinste abscheuliche Vielfache genau .
- Beispiel:
- Sei . Dann kann man der obigen Zahlenfolge entnehmen, dass unter den Vielfachen von erstmals die Zahl abscheulich ist. Tatsächlich ist .
- Sei weiters , also eine Mersenne-Zahl mit geradem Exponenenten (). Die kleinste abscheuliche Vielfache dieser Zahl ist . Tatsächlich ist .
- Beispiel:
- 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.
- Die Morse-Folge lautet:
- Beispiel:
- Jede Zahl der Form , 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 gilt: . 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.
- Beweis:
- Jede Primzahl der Form , also jede Mersenne-Primzahl, ist eine abscheuliche Zahl.
- Beweis:
- Die Binärdarstellung der Zahl besteht aus Einsen. Der Exponent einer Mersenne-Primzahl ist immer selbst eine Primzahl (siehe hier). Weil Primzahlen, abgesehen von , immer ungerade sind, muss auch die Zahl ungerade sein. Somit besteht die Binärdarstellung der Zahl aus , also aus einer ungeraden Anzahl von Einsen. Somit ist die Zahl eine abscheuliche Zahl.
- Der Spezialfall mit ergibt die Mersenne-Primzahl und für die Binärdarstellung von gilt: . Sie besteht aus 2 Einsen, die Zahl ist somit eine böse Zahl und wird deswegen von dieser Aussage ausgeschlossen.
- Beispiel:
- Für die Binärdarstellung der 4. Mersenne-Primzahl gilt:
- .
- 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.
- Für die Binärdarstellung der 4. Mersenne-Primzahl gilt:
- Beweis:
- Sei . Dann gelten die folgenden beiden Aussagen:[6]
- Es gibt gleich viele böse wie abscheuliche Zahlen, deren Darstellung im Dualsystem jeweils Stellen haben.
- Die Menge der bösen Zahlen mit Stellen im Dualsystem und die Menge der abscheulichen Zahlen mit Stellen im Dualsystem haben dieselbe Summe, nämlich
-
- Beispiel:
- Sei .
- Dann gibt es exakt 8 böse Zahlen, deren Binärdarstellung nur 5 Stellen hat, nämlich die folgenden:
- 17=(10001)2, 18=(10010)2, 20=(10100)2, 23=(10111)2, 24=(11000)2, 27=(11011)2, 29=(11101)2 und 30=(11110)2
- Außerdem gibt es exakt 8 abscheuliche Zahlen, deren Binärdarstellung nur 5 Stellen hat, nämlich die folgenden:
- 16=(10000)2, 19=(10011)2, 21=(10101)2, 22=(10110)2, 25=(11001)2, 26=(11010)2, 28=(11100)2 und 31=(11111)2
- 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 .
- Tatsächlich gilt für die Summe der 8 bösen Zahlen, deren Binärdarstellung nur 5 Stellen hat:
- Für die Summe der 8 abscheulichen Zahlen, deren Binärdarstellung nur 5 Stellen hat, gilt:
- Die Summe ist gleich, wie im obigen Satz angegeben.
- Beispiel:
-
- Sei die Nim-Addition, , wie folgt definiert:
- Für jedes Paar ganzzahliger, nichtnegativer Zahlen gilt: mit , , (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“, , wie die geraden und ungeraden Zahlen unter „normaler“ Addition. Also gilt:
- böse böse = böse
- abscheulich abscheulich = böse
- böse abscheulich = abscheulich böse = abscheulich
- Beispiel 1:
- Weiter oben wurde gezeigt, dass eine böse Zahl ist, weiters ist auch eine böse Zahl:
- Das Ergebnis hat eine gerade Anzahl an Einsen, ist also eine böse Zahl.
- Weiter oben wurde gezeigt, dass eine böse Zahl ist, weiters ist auch eine böse Zahl:
- Beispiel 2:
- Weiter oben wurde gezeigt, dass eine abscheuliche Zahl ist, weiters ist auch eine abscheuliche Zahl:
- Das Ergebnis hat eine gerade Anzahl an Einsen, ist also eine böse Zahl.
- Weiter oben wurde gezeigt, dass eine abscheuliche Zahl ist, weiters ist auch eine abscheuliche Zahl:
- Beispiel 3:
- Weiter oben wurde gezeigt, dass 51 eine böse und 52 eine abscheuliche Zahl ist:
- Das Ergebnis hat eine ungerade Anzahl an Einsen, ist also eine abscheuliche Zahl.
- Weiter oben wurde gezeigt, dass 51 eine böse und 52 eine abscheuliche Zahl ist:
- Beispiel 1:
- Die bösen und abscheulichen Zahlen verhalten sich unter „Nim-Addition“, , wie die geraden und ungeraden Zahlen unter „normaler“ Addition. Also gilt:
- 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 lautet:
- Die Zahl hat die folgenden Teiler: . Alle Teiler haben in ihrer Binärdarstellung eine ungerade Zahl von Einsen, somit sind alle Teiler abscheuliche Zahlen. Also hat die abscheuliche Zahl nur abscheuliche Teiler, die in Summe selbst ergeben.
- Die Binärdarstellung der abscheulichen Zahl lautet:
- Beispiel:
- 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
- ↑ 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
- ↑ a b Winning Ways for Your Mathematical Plays, Volume 1, S. 110 (PDF; 18 MB)
- ↑ Jean-Paul Allouche, Benoit Cloitre, V. Shevelev: Beyond odious and evil. Aequationes Mathematicae 90, 2015, S. 341–353, abgerufen am 13. April 2024.
- ↑ 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.
- ↑ É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.
- ↑ a b odious numbers auf Numbers Aplenty
- ↑ Neil Sloane: A212302: Numbers k whose sum of proper odious divisors (A000069) equals k., auf On-Line Encyclopedia of Integer Sequences
- ↑ 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
- ↑ 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.