Nichtkototient

Der Kototient einer Zahl ist definiert als . Dabei ist die eulersche Phi-Funktion (auch Totient von genannt), welche angibt, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind. Der Wert gibt somit die Anzahl der natürlichen Zahlen an, welche mindestens einen Primfaktor mit gemeinsam haben.

In der Zahlentheorie ist ein Nichtkototient (vom englischen Noncototient) eine natürliche Zahl , welche kein Kototient ist, wenn also die Gleichung

keine Lösung für hat. Mit anderen Worten: ist ein Nichtkototient, wenn keine natürliche Zahl existiert, zu welcher es exakt Zahlen gibt, die mindestens einen Primfaktor mit gemeinsam haben und kleiner oder gleich sind.

Beispiele

  • Die Kototienten , also die Anzahl der natürlichen Zahlen , welche mindestens einen Primfaktor mit gemeinsam haben, lauten (für ):
0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, 1, 38, 35, 40, 17, 54, 1, 48, 27, … (Folge A051953 in OEIS)
  • Die Zahl ist ein Nichtkototient, weil es keine natürliche Zahl gibt, für welche exakt Zahlen existieren, die mindestens einen Primfaktor mit gemeinsam haben und kleiner oder gleich sind.
  • Die Zahl ist kein Nichtkototient:
Die Zahl ist zu den sechs Zahlen teilerfremd, mit allen anderen 12 Zahlen, welche kleiner oder gleich sind, hat sie einen Primfaktor gemeinsam. Somit ist . Der Kototient der Zahl ist somit gleich . Also ist kein Nichtkototient. Weitere muss man nicht suchen (obwohl auch und den Kototienten hätten).
  • Die folgenden Zahlen sind die kleinsten Nichtkototienten:
10, 26, 34, 50, 52, 58, 86, 100, 116, 122, 130, 134, 146, 154, 170, 172, 186, 202, 206, 218, 222, 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, 518, 520, … (Folge A005278 in OEIS)
  • Die nächste Liste gibt die kleinsten an, deren Kototient ist (für aufsteigende ; falls es keine Zahl mit Kototient gibt, so wird die Zahl 0 angegeben):
1, 2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0, 235, 0, 329, 78, 159, 98, 105, 0, 371, 84, 177, 122, 135, 96, 305, 90, 427, … (Folge A063507 in OEIS)
Taucht in obiger Liste an der -ten Stelle eine auf (wobei man mit zu zählen beginnen muss), so ist ein Nichtkototient, weil es offenbar kein gibt, deren Kototient ist (wie zum Beispiel an der 10., 26., 34., 50., 52. und 58. Stelle, welche allesamt Nichtkototienten sind).
  • Die nächste Liste gibt die größten an, deren Kototient ist (für aufsteigende ; falls es keine Zahl mit Kototient gibt, so wird die Zahl 0 angegeben; der Wert für ist ∞, da alle Primzahlen den Kototienten haben und es somit keine größte Zahl gibt, deren Kototient ist):
1, ∞, 4, 9, 8, 25, 10, 49, 16, 27, 0, 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0, 187, 52, 841, 58, 961, 64, 253, 0, 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0, 667, 0, 2809, 106, 703, 104, 697, 0, 3481, 118, 3721, 122, … (Folge A063748 in OEIS)
Taucht in obiger Liste an der -ten Stelle eine auf, so ist wie in der vorigen Liste ein Nichtkototient (man muss mit zu zählen beginnen).
  • Die nächste Liste gibt die Anzahl der an, deren Kototient ist (für aufsteigende ):
1, ∞, 1, 1, 2, 1, 1, 2, 3, 2, 0, 2, 3, 2, 1, 2, 3, 3, 1, 3, 1, 3, 1, 4, 4, 3, 0, 4, 1, 4, 3, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, 5, 1, 7, 1, 8, 1, 5, 2, 6, 1, 9, 2, 6, 0, 4, 2, 10, 2, 4, 2, 5, 2, 7, 5, 4, 1, 8, 0, 9, 1, 6, 1, 7, … (Folge A063740 in OEIS)
Beispiel:
An der 26. Stelle obiger Liste (man muss mit mit dem Zählen beginnen) steht die Zahl . Das bedeutet, dass es Zahlen gibt, deren Kototient gleich ist. Somit ist ein Nichtkototient.
  • Es folgt eine Tabelle, von der man etwas leichter die Nichtkototienten ablesen kann. In der ersten Spalte sind die aufsteigenden , in der zweiten Spalte stehen diejenigen Zahlen, deren Kototient ist und in der dritten Spalte kann man die Anzahl der Zahlen ablesen, die in der zweiten Spalte stehen. Jedes Mal, wenn in dieser dritten Spalte eine Null steht, wenn es also keine Zahlen gibt, welche als Kototient haben, handelt es sich bei um einen Nichtkototienten (welcher gelb eingefärbt wird):

Eigenschaften

  • Es gibt unendlich viele Nichtkototienten.
Die Frage auf diese Antwort wurde im Jahr 1959 von Wacław Sierpiński[1] und im Jahr 1973 von Paul Erdős[2] aufgeworfen[3] und von Jerzy Browkin und Andrzej Schinzel im Jahr 1995 beantwortet, welche zeigen konnten, dass alle Zahlen der Form mit natürlichen Nichtkototienten sind.[4] Im Jahr 2000 konnten Achim Flammenkamp und Florian Luca noch weitere unendliche Familien hinzufügen, die allesamt Nichtkototienten sind:[5]
Sei eine natürliche Zahl. Dann sind alle Zahlen der Form mit Nichtkototienten (die Zahlen in der Mengenklammer sind allesamt Riesel-Zahlen).

Vermutungen

  • Es wird vermutet, dass alle Nichtkototienten gerade Zahlen sind. Das würde nämlich wie folgt aus der starken goldbachschen Vermutung folgen: Ist ungerade, so wäre nach der goldbachschen Vermutung für zwei Primzahlen und . Dann wäre weiter ein Kototient. Die goldbachsche Vermutung hat also zur Konsequenz, dass alle ungeraden Zahlen Kototienten wären, das heißt umgekehrt müssten alle Nichtkototienten gerade sein.

Siehe auch

Einzelnachweise

  1. Wacław Sierpiński: Number Theory, Part II, Warszawa, 1959 (polnisch)
  2. Paul Erdős: Über die Zahlen der Form und , Elem. Math. (1973), 83–86
  3. Achim Flammenkamp, Florian Luca: Infinite families of noncototients. Einleitung. Colloquium Mathematicum 86 (1), 2000, S. 37–41, abgerufen am 29. Februar 2020.
  4. Jerzy Browkin, Andrzej Schinzel: On integers not of the form n-φ(n). Theorem. Colloquium Mathematicum 68 (1), 1995, S. 55–58, abgerufen am 29. Februar 2020.
  5. Achim Flammenkamp, Florian Luca: Infinite families of noncototients. Theorem. Colloquium Mathematicum 86 (1), 2000, S. 37–41, abgerufen am 29. Februar 2020.