Böse Zahl – Wikipedia
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)2, von rechts nach links gelesen also (11101)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). 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-...).
In der Zahlentheorie ist eine böse Zahl (englisch evil number) eine nichtnegative ganze Zahl, die im Dualsystem eine gerade Zahl von Einsen hat.[1] Nichtnegative ganze Zahlen, die nicht böse sind, werden abscheuliche Zahlen (englisch odious 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 evil numbers haben eine even, also gerade Anzahl an Einsen, die odious numbers eine odd, also ungerade Anzahl an Einsen.
Beispiele
[Bearbeiten | Quelltext bearbeiten]- Die Binärdarstellung (also die Darstellung im Dualsystem) von lautet:
- Diese Binärdarstellung besteht aus 4 Einsen. 4 ist eine gerade Zahl und somit ist eine böse Zahl.
- Die Binärdarstellung von lautet:
- Diese Binärdarstellung besteht aus 3 Einsen. 3 ist eine ungerade Zahl und somit ist keine böse Zahl, sondern eine abscheuliche Zahl.
- Die ersten bösen Zahlen, die kleiner als 100 sind, lauten:
Eigenschaften
[Bearbeiten | Quelltext bearbeiten]- Sei . Dann gelten die folgenden beiden Aussagen:[3]
- 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 gibt magische Quadrate, die nur aus bösen Zahlen bestehen. Das magische Quadrat mit den kleinsten bösen Zahlen ist das folgende:[3]
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, ...[1]
- Böse Zahlen geben die Positionen der Nullwerte in der Thue-Morse-Folge an und werden daher auch Thue-Morse-Menge genannt.[4]
- Beispiel:
- Die Morse-Folge lautet:
- 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.
- Beispiel:
- Es sind Zahlen bekannt, die der Summe ihrer bösen Teiler entsprechen. Diese lauten:[5]
- Man könnte obige Zahlen böse-perfekte Zahlen nennen.[5]
- Beispiel:
- Die Binärdarstellung der bösen Zahl lautet:
- Die Zahl hat die folgenden Teiler: . Die Teiler , und haben in ihrer Binärdarstellung eine gerade Zahl von Einsen, sind also böse Zahlen und es gilt: . Somit ist die Summe ihrer bösen Teiler.
- Die Binärdarstellung der bösen Zahl lautet:
- Beispiel:
- 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.[6]
- Die Aufteilung der Zahlen von bis für alle natürlichen Zahlen in böse und abscheuliche Zahlen bietet eine Lösung für das Prouhet-Tarry-Escott-Problem, Zahlenmengen zu finden, deren Potenzsummen bis zur -ten Potenz gleich sind.[7]
- 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
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]- Eric W. Weisstein: Evil Number. In: MathWorld (englisch).
- evil numbers auf Numbers Aplenty
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ a b 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
- ↑ a b Winning Ways for Your Mathematical Plays, Volume 1, S. 110 (PDF; 18 MB)
- ↑ a b evil numbers auf Numbers Aplenty
- ↑ É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 5. April 2024.
- ↑ a b Neil Sloane: Sequenz A230587: Number n such that the sum of its proper evil divisors (A001969) equals n., 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 5. April 2024.
- ↑ E. M. Wright: Prouhet's 1851 solution of the Tarry-Escott problem of 1910. American Mathematical Monthly 66 (3), 1959, S. 199–201, abgerufen am 5. April 2024.