Warum ist  1000001000001₂₂₆₄  keine Primzahl ?


Die Antwort lautet in Kurzform :  Weil die Anzahl der Nullen zwischen den Einsen ungerade ist. ( 2264  ist dabei die Basis der Zahldarstellung und vollkommen willkürlich gewählt).

Ausführlich lautet die Behauptung :
y₁ = 1 ,  y_n+1 =  y_n + b^k·n  definiert eine Zahlenfolge  y_n , die in Basis  b  geschrieben aus  n  Einsen besteht, zwischen denen Gruppen aus  k - 1  Nullen stehen. (Also ist z.B. für  b = 3  und  k = 2: y₄ = 1010101₃ .) Dann lässt sich zeigen: Für  n > 2  ist  y_n  in allen Basen  b  keine Primzahl, falls  k > 1  gerade ist.

Die Faktorisierung lässt sich konstruktiv angeben. Wie sieht sie in Basis  b  aus ?

Problem 51 stellte einen Spezialfall dieses Problems dar. Den dortigen Lösungsansatz kann man auch hier verwenden, um  y_n  in geschlossener Form darzustellen. Analog zu Problem 51 kann man eine andere (äquivalente) rekursive Definition angeben :

y₁ = 1 ,  y_n+1 = y_n·b^k + 1

Für ungerade  k  gilt die Primzahl-Behauptung nicht. Primzahlen unter den  y_n  sind dann zwar sehr dünn gesät, aber Sie können welche finden. Eine notwendige, aber nicht hinreichende Bedingung ist:  y_n  prim   →   n  prim  (warum?).



Lösung

Publiziert 2010-03-01          Stand 2009-07-19

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem

Manfred Börgens   |    zur Leitseite