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.

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

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

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

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

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  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. a b 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. a b 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.