Die Folge der der ersten n-Primzahlen teilt welche fortlaufende Zahlenfolge?

Question

!

Die Folge der Primzahlen ist, sagen wir mal P(n)=(2,3,5...n-te Primzahl).

Gesucht wird das kleinste b aus der Folge A(n)=(b,b+1,b+2...b+n-1) für das gilt:

 P(n) | A(n)

z.B.:

A(3)={8,9,10} da 2 | 8 ∧ 3 | 9 ∧ 5 | 10 mit  b=8+5#·k
 
A(5)={788,789,790,791,792} da 2 | 788 ∧ 3 | 789 ∧ 5 | 790 ∧ 7 | 791 ∧ 11 | 792  mit b=788+11#·k

für alle k ∈ ℕ⁰

Durch ausprobieren kann man vielleicht so bis A(10) oder A(12) kommen.
Viel weiter aber nicht.

Es ist doch anzunehmen, dass es für jedes n ∈ ℕ⁺ auch ein kleinstes b gibt.
Mich interessiert daher ob wir auch A(1000) oder sogar A(10⁶) lösen können.
Gibt es es eine Methode das effektiv zu berechnen?
 

 

Answer 1

b lässt sich in etwa so bestimmen:
b genügt dem Gleichungssystem
b=0 mod 2
b=-1 mod 3
b= -2 mod 5
...
b=1-n mod p_n,
wenn p_n die n-te Primzahl bezeichne. Da die Primzahlen 2,3,5, ..., p_n teilerfremd sind, ist obiges System nach dem Chinesischem Restsatz eindeutig lösbar modulo 2*3*5*...*p_n. Wähle dann einfach b als die kleinste positive ganze Zahl, die den durch den Chinesischen Restsatz bestimmten Rest modulo 2*3*5*...*p_n hat.
(mehr zu dem Chinesichen Restsatz steht bei Wikipedia)

Anmerkung: effektiv ist diese Methode natürlich nicht, aber eine bessere fällt mir nicht ein

Comments

Danke ih169 !Das klingt sehr interessant...
...der Chinesische Restsatz stammt vermutlich aus dem 3. Jahrhundert n. Chr. (!!!) und behandelt ein ein System von linearen Kongruenzen ...

Bin schon mal darüber gestolpert in einem englischen Forum: CRT -  Chinese Remainder Theorem
aber hab es noch nie angewendet.

Das kann ein Lösungsansatz sein.
Wie bist du darauf gekommen?