Primzahlenproblem

07/06/2011 - 14:08 von Albrecht | Report spam
Hallo allerseits,

weiss hier einer ob folgendes Problem schon geloest ist?

Sei p eine Primzahl und a, b, c, ... natuerliche Zahlen die die
Abstaende zu der naechsten, uebernaechsten, ueberuebernaechsten, ...
groesseren Primzahl angeben. (Ich nenne eine Folge a, b, c, ... von n
Abstaenden eine Abstandskette A_n.)

Also zB p=3, dann ist deren Abstandskette zu den folgenden Primzahlen
5, 7, 11, 13, 17, 19:
A_6(3): a=2, b=4, c=8, d, e, f, etc.

Nun die Aufgabe: Fuer eine (allgemeine) Primzahl p, wieviel Abstaende
a, b, c, ... zu den darauf folgenden Primzahlen muessen mindestens
angegeben werden, damit p eindeutig bestimmt ist? Also, wie lange muss
eine Abstandskette mindestens sein, damit durch sie in jedem Falle
eine Primzahl eindeutig definiert ist?

Der Abstand zur naechsten Primzahl (Abstandskettenlaenge 1) genuegt
sicher nicht, wegen den Primzahlzwillingen. Es gibt sehr viele,
vielleicht sogar unendlich viele Primzahlen mit A_1(p): a=2.
Abstandskettenlaenge 2 genuegt nicht, da schon zB p=3 und p beide
a= 2 und b= 4 haben., also A_2(3)=A_2(11)

Ich vermute aber trotzdem, dass es eine Mindestanzahl von Abstaenden
gibt (eine Mindestlaenge der Abstandskette) um jede Primzahl eindeutig
zu bestimmen, da ja die Abstaende zwischen den Primzahlen mit der
Groesse der Primzahlen tendenziell zunimmt.

Vielleicht interessiert sich ja hier jemand fuer diese Fragestellung
oder kennt zufaellig eine Literaturstelle dazu.

Gruss
Albrecht
 

Lesen sie die antworten

#1 Jan Fricke
07/06/2011 - 14:49 | Warnen spam
On 06/07/2011 02:08 PM, Albrecht wrote:
Hallo allerseits,

weiss hier einer ob folgendes Problem schon geloest ist?

Sei p eine Primzahl und a, b, c, ... natuerliche Zahlen die die
Abstaende zu der naechsten, uebernaechsten, ueberuebernaechsten, ...
groesseren Primzahl angeben. (Ich nenne eine Folge a, b, c, ... von n
Abstaenden eine Abstandskette A_n.)

Also zB p=3, dann ist deren Abstandskette zu den folgenden Primzahlen
5, 7, 11, 13, 17, 19:
A_6(3): a=2, b=4, c=8, d, e, f, etc.

Nun die Aufgabe: Fuer eine (allgemeine) Primzahl p, wieviel Abstaende
a, b, c, ... zu den darauf folgenden Primzahlen muessen mindestens
angegeben werden, damit p eindeutig bestimmt ist? Also, wie lange muss
eine Abstandskette mindestens sein, damit durch sie in jedem Falle
eine Primzahl eindeutig definiert ist?



Das wird in etwa in der Größenordnung p*ln(p) liegen.


Beweis:
Die (unendliche) Abstandskette von p ist dadurch gekennzeichnet, dass
kein durch p teilbarer Wert darin vorkommt, jedoch jeder andere
Divisionsrest von p (das ist der Satz von Dirichlet). Wenn wir also die
Folge abbrechen, nachdem jeder dieser anderen Reste einmal aufgetaucht
ist, dann beschreibt diese Abstandskette eindeutig die Primzahl p, denn
für jede andere Primzahl q gibt es einen Wert a in der Folge, so dass
q+a durch p teilbar ist, was aber nur für q<p möglich ist; von dieser
Sorte gibt es aber nur endlich viele, eventuell müsste man dafür noch
die Folge verlàngern? [Darüber denke ich noch mal nach, werde eventuell
noch etwas dazu posten.]

Die Reste modulo p sind aber "halbwegs zufàllig", d.h. man hat es im
Wesentlichen mit dem Sammlerproblem für (p-1) Objekte zu tun. Für n
Objekte liegt der Erwartungswert in der Größenordnung n*ln(n), also wird
man eine Folgenlànge von p*ln(p) erwarten.


Viele Grüße Jan

Ähnliche fragen