[Teoria liczb] Ograniczony ciąg liczb pierwszych

[Swistak]

Początek taki sam, jak w zadaniu 51-3-3, czyli:
1. Określmy następująco ciąg liczb \(\displaystyle{ p_i}\):
- \(\displaystyle{ p_1, \ p_2}\) są liczbami pierwszymi
- \(\displaystyle{ p_n}\) jest największym dzielnikiem pierwszym liczby \(\displaystyle{ p_{n-1}+p_{n-2}+2000}\)
Udowodnij, że istnieje takie M, że dla każdego n zachodzi \(\displaystyle{ p_n \le M}\)

2. I teraz mały challenge ode mnie. Postaraj się znaleźć jak najmniejsze M o takiej własności :>. (Choć tutaj trzeba założyć, że \(\displaystyle{ p_1}\) i \(\displaystyle{ p_2}\) nie będą na tyle duże, aby przeszkadzało nam to w dowodzie).

[marcin7Cd]

63. Zadanie z nierozwiązanych
Udowodnię podpunkt 1.

Ukryta treść:    

Oznaczmy przez \(\displaystyle{ gpf(x)}\) największy dzielnik pierwszy liczby x. Rozważmy w ogólności ciąg \(\displaystyle{ p_i}\) określony tak, że \(\displaystyle{ p_1,p_2}\) są liczbami pierwszymi, a \(\displaystyle{ p_n=gpf(p_{n-1}+p_{n-2}+2a)}\), gdzie \(\displaystyle{ a\in \ZZ_+}\) , \(\displaystyle{ n=2,3,4,5,...}\).
Niech \(\displaystyle{ p}\) będzie taką nieparzystą liczbą pierwszą, że \(\displaystyle{ p+2i}\) jest złożone dla \(\displaystyle{ i=1,2,3,...,a+1}\).Weźmy \(\displaystyle{ K_p=\left\{ r|r\in \PP \ \hbox{i} \ r \le p \right\}}\) Lemat: jeśli \(\displaystyle{ x,y\in K_p \Rightarrow gpf(x+y+2a)\in K_p}\). Jeśli \(\displaystyle{ 2\nmid x}\) i \(\displaystyle{ 2\nmid y}\) , to \(\displaystyle{ 2|x+y+2a}\). Z uwagi na to, że \(\displaystyle{ x+y+2a>2}\) mam \(\displaystyle{ gpf(x+y+2a) \le \frac{x+y+2a}{2} \le \frac{p+p+2a}{2}=p+a}\) jednak \(\displaystyle{ gpf(x+y+2a)}\) jest liczbą pierwszą, a liczby \(\displaystyle{ p+1,p+2,...p+a}\) są złożone, więc \(\displaystyle{ gpf(x+y+2a) \le p}\).Teraz weźmy drugi przypadek. Bez straty ogólność \(\displaystyle{ 2|x \Rightarrow x=2 \Rightarrow gpf(x+y+2a)=gpf(y+2(a+1)) \le p+2(a+1)}\) Korzystając z tego, że \(\displaystyle{ p+1,p+2,...,p+2(a+1)}\) są liczbami złożonymi mam \(\displaystyle{ gpf(x+y+2a)=gpf(y+2(a+1)) \le p}\). Co kończy dowód lematu.
Niech \(\displaystyle{ q_0,q_1,...,q_a}\) będą kolejnymi nieparzystymi liczbami pierwszymi różnymi od \(\displaystyle{ p_0,p_1}\). Wśród liczb \(\displaystyle{ max(p_0,p_1)+2,max(p_0,p_1)+4,....,max(p_0,p_1)+2q_0q_1q_2,...q_a}\) jest poszukiwana przez nas liczba \(\displaystyle{ p}\)(o własnościach takich jak wyżej).Z chińskiego twierdzenia o resztach jestem w stanie dobrać takie, \(\displaystyle{ x<q_0q_1q_2...q_a}\),że \(\displaystyle{ q_0|x+2 , q_1|x+4 ,...q_a|x+2a+2}\), a powyższy ciąg liczb generuje wszystkie liczby \(\displaystyle{ \pmod{q_0q_1...q_a}}\), więc istnieje \(\displaystyle{ l\in \left\{ 1,2,..,q_0q_1...q_a\right\}}\), że \(\displaystyle{ max(p_0,p_1)+2l \equiv x \pmod{q_0q_1...q_a}}\). spośród liczb \(\displaystyle{ max(p_0,p_1)+2,max(p_0,p_1)+4,...,max(p_0,p_1)+2l}\) wybieram największą liczbę pierwszą i ona jest poszukiwaną przez nas liczbą pierwszą \(\displaystyle{ p}\). Pozostaje zauważyć, że \(\displaystyle{ p_0,p_1 \in K_p}\), więc \(\displaystyle{ p_j\in K_p \Rightarrow p_j \le p}\).

wzorowałem się na tym dowodzie:
Przy okazji sprawdzając za pomocą komputera, ciąg z zadania można oszacować przez \(\displaystyle{ M= max(p_1,p_2)+4810}\) dla \(\displaystyle{ p_0,p_1 \le 10000}\). Można również sprawdzić, że dla \(\displaystyle{ p_1,p_2 \le 100000}\) ciąg w końcu trafi na jeden z dwóch cyklów o długościach \(\displaystyle{ 67}\) i \(\displaystyle{ 27}\).

[Medea 2]

Przy okazji sprawdzając za pomocą komputera, ciąg z zadania można oszacować przez \(\displaystyle{ M= max(p_1,p_2)+4810}\) dla \(\displaystyle{ p_0,p_1 \le 10000}\). Można również sprawdzić, że dla \(\displaystyle{ p_1,p_2 \le 100000}\) ciąg w końcu trafi na jeden z dwóch cyklów o długościach \(\displaystyle{ 67}\) i \(\displaystyle{ 27}\).

Liczb pierwszych od \(\displaystyle{ 2}\) do \(\displaystyle{ 99991}\) jest \(\displaystyle{ 9592}\), co daje niemalże czterdzieści sześć milionów par \(\displaystyle{ (p_1, p_2)}\) do sprawdzenia - jak sensownie tego dokonać?

[marcin7Cd]

Trzeba napisać program Ja napisałem w c++ i pozwoliłem programowi działać przez 20-25 minut. Po prostu zaczynałem od każdej pary liczby pierwszych i liczyłem kolejne wyrazu ciągu aż trafiłem na początek cyklu albo powtórzyłem jakąś parę liczb pierwszych. Mogą udostępnić kod jak ktoś jest ciekaw. I tak nie robiłem najbardziej efektywnego rozwiązania, czyli zaznaczaniu, jakie pary liczb pierwszych napotkałem podczas liczenia ciągu(i nie rozpatrzeniu ich ponownie).