Z góry przepraszam, że bede pisać sporo słownie, słabo piszę w LaTeX. Aby ułatwić zapis zdefinujmy \(\displaystyle{ f(n)}\) jako:
\(\displaystyle{ f(n) = p_{1}^{ a_{1} }p_{2}^{ a_{2} }...p_{n}^{ a_{k} }}\) gdzie \(\displaystyle{ p_{n}}\) jest n-tą liczbą pierwszą, \(\displaystyle{ a _{1}, a _{2}...a_{k}}\) będa dowolnymi dadatnimi liczbami całkowitymi. Niech \(\displaystyle{ q_{n}}\) będzie dowolną liczbą naturalną względnie pierwszą z \(\displaystyle{ f(n)}\).
Twierdzenie: Jeśli \(\displaystyle{ f(n)\pm\ q _{n}< (p _{n}+2)^2}\) to \(\displaystyle{ f(n)\pm\ q _{n}}\) jest liczbą pierwszą. Każdą liczbę pierwszą można tak znaleść.
Czy to jest oczywiste? Mi się wydaje, że tak, trochę tłumaczy dlaczego liczby pierwsze są rozmieszczone tak gęsto.
Pytanie trudniejsze jest czy można przedstawić każda liczbą pierwszą jako \(\displaystyle{ f(n)\pm\ q _{n}}\) jeśli \(\displaystyle{ q_{n}}\) ma być względnie pierwsze z \(\displaystyle{ f(n)}\) i w rozkładzie na czynniki pierwsze może mieć tylko liczby pierwsze mniejsze niż \(\displaystyle{ (p _{n-1}+2)^2}\) (bo te liczby pierwsze już znaleźliśmy). To jest o tyle ciekawa hipoteza, bo gdyby tak było, to ta metoda daje algorytm (na swój sposób wzór rekurencyjny) które generuje wszystkie, liczby pierwsze.
Co myślicie?
Liczby pierwsze - czy to oczywiste?
Liczby pierwsze - czy to oczywiste?
Ostatnio zmieniony 13 lip 2012, o 09:34 przez mmmmm, łącznie zmieniany 1 raz.
Liczby pierwsze - czy to oczywiste?
Dlaczego? Miałeś na myśli też tą pierwszą część:
Zarys dowodu
\(\displaystyle{ f(n)}\) jest względnie pierwsze z \(\displaystyle{ q _{n}}\) więc \(\displaystyle{ f(n)}\) jest względnie pierwsze z \(\displaystyle{ f(n)-q _{n}}\) (Piszę -, a nie plus minus bo oczywiście dla \(\displaystyle{ n>3}\) to będzie minus). Innymi słowami wyrażenie \(\displaystyle{ f(n)-q _{n}}\) nie dzieli się na żaden z czynników \(\displaystyle{ f(n) = p_{1}^{ a_{1} }p_{2}^{ a_{2} }...p_{n}^{ a_{k} }}\). Najmniejsza liczba złożona która nie zawiera tych czynników to kolejna liczba pierwsza podniesiona do kwadratu. Czyli w najgorszym przypadku: \(\displaystyle{ p _{n}+2}\). Dlatego szukamy \(\displaystyle{ f(n)\pm\ q _{n}< (p _{n}+2)^2}\).
?Twierdzenie: Jeśli \(\displaystyle{ f(n)\pm\ q _{n}< (p _{n}+2)^2}\) to \(\displaystyle{ f(n)\pm\ q _{n}}\) jest liczbą pierwszą. Każdą liczbę pierwszą można tak znaleść.
Zarys dowodu
\(\displaystyle{ f(n)}\) jest względnie pierwsze z \(\displaystyle{ q _{n}}\) więc \(\displaystyle{ f(n)}\) jest względnie pierwsze z \(\displaystyle{ f(n)-q _{n}}\) (Piszę -, a nie plus minus bo oczywiście dla \(\displaystyle{ n>3}\) to będzie minus). Innymi słowami wyrażenie \(\displaystyle{ f(n)-q _{n}}\) nie dzieli się na żaden z czynników \(\displaystyle{ f(n) = p_{1}^{ a_{1} }p_{2}^{ a_{2} }...p_{n}^{ a_{k} }}\). Najmniejsza liczba złożona która nie zawiera tych czynników to kolejna liczba pierwsza podniesiona do kwadratu. Czyli w najgorszym przypadku: \(\displaystyle{ p _{n}+2}\). Dlatego szukamy \(\displaystyle{ f(n)\pm\ q _{n}< (p _{n}+2)^2}\).
- Sylwek
- Użytkownik
- Posty: 2716
- Rejestracja: 21 maja 2007, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 160 razy
- Pomógł: 657 razy
Liczby pierwsze - czy to oczywiste?
Twoje spostrzeżenie jest oczywiście prawdziwe (po drobnym uściśleniu treści i założeń twierdzenia), ale wymaga skromnego dowodu, jak np. to, co napisałeś powyżej jest w porządku.
O drugiej części się nie wypowiem, wspomnę tylko, że istnieją wzory typu \(\displaystyle{ g(n)=p_n}\), jednak ich złożoność jest tak duża, że nie są one żadną pomocą w wyznaczaniu kolejnych liczb pierwszych. Spójrz tutaj:
51402.htm
79460.htm
159928.htm
Obawiam się, że Twój rekurencyjny pomysł napotkałby na te same problemy, nawet jeśli te twierdzenia byłyby prawdziwe.
O drugiej części się nie wypowiem, wspomnę tylko, że istnieją wzory typu \(\displaystyle{ g(n)=p_n}\), jednak ich złożoność jest tak duża, że nie są one żadną pomocą w wyznaczaniu kolejnych liczb pierwszych. Spójrz tutaj:
51402.htm
79460.htm
159928.htm
Obawiam się, że Twój rekurencyjny pomysł napotkałby na te same problemy, nawet jeśli te twierdzenia byłyby prawdziwe.
Liczby pierwsze - czy to oczywiste?
Dzięki Sylwek za wytłumaczenie. Też mi się wydaje, że algorytm był by bardzo mało efektywny, bo to moje \(\displaystyle{ f(n)}\) rośnie bardzo szybko. To co wydało mi się atrakcyjne jest to, że to twierdzenie wciąż było by prawdziwe, bez tych potęg \(\displaystyle{ a_{1}, a _{2}, a _{k}}\) a wtedy liczb względnie pierwszych mniejszych od \(\displaystyle{ f(n) = p_{1}p_{2}...p_{n}}\) jest \(\displaystyle{ (p_{1}-1)(p_{2}-1)...(p_{n}-1)}\). Co daje od razu jakąś tam nierówność: liczb pierwszych mniejszych niż \(\displaystyle{ f(n) = p_{1}p_{2}...p_{n}}\) jest napewno mniej niż \(\displaystyle{ (p_{1}-1)(p_{2}-1)...(p_{n}-1)}\). Ale zapewne ta nierówność jest śmiesznie słaba porównując do znanych nierówności. Douczę się z funkcji Eulera, bo mi to wciąż wygląda ciekawie.