Hipotezy o liczbach pierwszych

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Re: Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

Cześć. Ja mam kolejną hipotezę, którą staram się udowodnić i zapraszam również innych do sprawdzenia czy to prawda czy fałsz.

Otóż zrobiłem rozkład liczb pierwszych na spirali Fibonacciego (założyłem tu wątek poświęcony temu zagadnieniu, ale nikt się nie udziela).
Z tego rozkładu wynika następująca dość nietrywialna sprawa, o której nie wiedziałem.

\(\displaystyle{ Slp = \frac12 \Phi \\
Slp = \frac{\frac{lp_1 +lp_2 +... + lp_n}{ Ilp}}{ Wlf}}\)


Przy założeniu, że :

\(\displaystyle{ Mlf <Lp_n \le Wlf}\), gdzie

\(\displaystyle{ Lp}\) - liczba pierwsza

\(\displaystyle{ Slp}\) - suma liczb pierwszych

\(\displaystyle{ Mlf}\) - mniejsza liczba fibo

\(\displaystyle{ Wlf}\) - wieksza liczba fibo

\(\displaystyle{ Ilp}\) - ilośc liczb pierwszych w przedziale

\(\displaystyle{ \Phi}\) - złota liczba \(\displaystyle{ 1,618...}\)

- Postarałem się to zapisać te wzory w Latexie...
Jeśli to poniżej jest dzięki temu bardziej zrozumiałe to może wróćmy do tematu i zacznijmy od tego, czy ktoś wie jak rozkładają się Liczby pierwsze w przedziałach wyznaczonych liczbami Fibonacciego?

\(\displaystyle{ Slp = \frac{\frac{lp_1 +lp_2 +... + lp_n}{ Ilp}}{ Wlf}}\)

Przekładając na polski język.
Każdy podzbiór liczb pierwszych, dla liczb \(\displaystyle{ > 5}\), rozdzielony wartościami liczb ciągu Fibonacciego ma związek ze Złotą Liczbą \(\displaystyle{ \Phi}\).
Suma liczb pierwszych w danym podzbiorze podzielona przez ilość liczb pierwszych i następnie podzielona przez liczbę Fibonacciego (zamykającą podzbiór) da przybliżenie \(\displaystyle{ \frac12 \cdot 1,618...}\)

P.S. Nie jestem matematykiem i poprawiłem jedynie wzory obejmując je znacznikami \(\displaystyle{ jeśli to nie wystarczy to już nie wiem co zrobić lepiej. Prosiłbym tylko o wyrozumiałość.}\)
Ostatnio zmieniony 3 lip 2019, o 18:49 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Brombal »

Niezbytnio
Napisałem maluśki programik
wyniki suma liczb pierwszych z przedziału dzielona przez ilość liczb pierwszych dzielone przez górną granicę przedziału są takie
Ukryta treść:    
-- 3 lip 2019, o 18:28 --

Wbrew pozorom dąży to do \(\displaystyle{ 0,5}\)-- 3 lip 2019, o 18:29 --albo coś około
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Re: Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

Fajna próba kolego @Brombal.

Nie wiem jaki szybki masz komputer ale skoro doliczyłeś do 44 wyrazu ciągu Fibonacciego to musi byś potężny procek w środku.
Podam Ci niżej fragment mojej kalkulacji - wynik z kosoli okna programu, które też jest programikiem napisanym w czystm C.
Otóż obliczyć każdą sumę liczb pierwszych w zadanym podzbiorze to zajmuje całe godziny dla wartości powyżej 30 wyrazu Ciągu Fibonacciego.
Ponadto nie jestem pewien, czy użyłeś odpowiedniego typu zmiennych w aplikacji, aby nie zaokraglać niepotrzebnie wartości niewymiernych.

Zobacz wynik działania mojego programiku, ustawiłem tylko żeby kalkulowało sumę liczb pierwszych i średnią, a nie listowało wszystkich liczb pierwszych w zbiorze.

Ukryta treść:    

Doliczenie wszystkiego do wartości 514229 która jest 29 wyrazem ciągu F zajmuje mojemu komputerowi prawie godzinę. Jeśli chcesz to mogę Ci wrzucić kod źródłowy i sam obejrzysz.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Brombal »

Niezbyt rozumiem
Obliczenia trwały ok. 34 s
Procek to zwykły i5 w laptopie
Program napisałem w Javie
pierwsza klasa
Ukryta treść:    
druga klasa to mój program do generowania pierwszych
Ukryta treść:    

ok 15 s z całej operacji to obliczenie wyrazów Fibonacciego reszta to sumowanie ok. 15 s a wygenerowanie tablicy booleanowej liczb pierwszych do fib(44) ok. 1,5 s-- 3 lip 2019, o 20:27 --Znalazłem błąd w programie
Ukryta treść:    


Wyniki są nieco inne
Ukryta treść:    
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

Nie znam dobrze Javy, ale składnia podobna do C.

W załączonym kodzie trudno mi się połapać, bo sporo też zmiennych.

Wydaje mi się, że bierzesz w funkcji main zbyt mały zakres liczb naturalnych.

Pętla

Kod: Zaznacz cały

for (int i = 6; i <= 43; i++) { ... }
... to jakby wyznacznik zakresu twojego programu. Dlatego tak szybko się kończy... ;)

Zobacz to co mam napisane w C i sobie porównaj. Program bierze dwa argumenty przy uruchomieniu, które są zakresem liczbowym, w którym operuje. Znajduje liczby Fibonacciego i Pierwsze i sumuje Pierwsze i wyciąga z nich .... Złotą Liczbę.

Ukryta treść:    
Czas działania aplikacji może być spory... zalecam nie wpisywać na początku wartości większych od 500000.

Przykład kolejnych danych z programu, który sobie działał w tle przez jakieś 1.5 godziny:
514229 is a Fibonacci and a Prime Number, let's start to calculate next primes subset
23704 Quantity of Primes in last subset
3052170812 Sum of Primes in last subset
672336.000000 Average value in last subset of Primes
0.808057 Approximation to the half of Golden number Phi/2 is result of Average number of Primes / Fibonacci number
1.616115 Approximation to the Golden number Phi
832040 is a Fibonacci Number, let's start to calculate next primes subset
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Brombal »

Kod: Zaznacz cały

for (int i = 6; i <= 43; i++) { ... }
To zakres kolejnych wyrazów ciągu Fibonacciego
Mam wrażenie, że masz zwyczajnie siłowy sposób generowania liczb pierwszych i w tym jest problem. Wygeneruj liczby pierwsze jako tablice booleanową do wartości fib(44) (np. zwyczajnym Eratostenesem dla C jest tego kupa Zajmie to jakieś 20 s dla tej metody).
Następnie leć po tablicy booleanowej od fib(n) do fib( n+1) sumując adresy true i ilość true. myślę, że działanie do fib(44) nie zajmie Ci więcej niż minutę w C.
Poniżej więcej wyników
Ukryta treść:    
Ostatnio zmieniony 3 lip 2019, o 21:47 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Re: Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

Brombal to jest zaskakujące dla mnie.
Skoro tak szybko działa to u Ciebie to świetnie. Widać prawidłowość, której się spodziewałem.
Potwierdzasz, że szukana wartość wedle założenia dąży do \(\displaystyle{ \frac12 \cdot 1,618...}\) ?
Oczywiście, że masz rację iż moja procedura znajdywania liczb pierwszych nie jest optymalna, ale nie spodziwałem się, że aż tak źle z nią jest.
Przeanalizuje twój generator liczb pierwszych i może czegoś się z niego nauczę.
Dzięki za dyskusję, ale muszę kończyć.-- 5 lip 2019, o 12:43 --@Brombal twoje rady są bezcenee.
Zrobiłem jak sugerowałeś. Zastosowałem sito Erastotenesa, bo twojego algorytmu MMSieve jeszcze nie rozgryzłem.
Czas obliczenia znacznie, ale to znacznie się skrócił.

Zobacz moje wyniki:
Ukryta treść:    
Jest jeden podzbiór liczb pierwszych więcej obliczony, czyli do Fib(44), w czasie 46 sekund, a nie kilku godzin jak poprzednio do rzędu mniejszych wartości. Uwaga! Wyniki mogą się różnić dla zbiorów gdzie granicą jest Licza Fibo, która też jest liczbą pierwszą.

Jednak powyżej 44 argumentu ciągu Fibonacciego zaczynają się już schody.
Problem wynika najprawdopodobniej z alokacji pamięci przez program dla danego przedziału liczb pierwszych pomiędzy wyższymi niż 44 -ty wyrazami ciągu Fibo.

Myślę, że delikatna optymalizacja jeszcze jest możliwa, aby alokować pamięć dla tablicy liczb pierwszych sekwencyjnie, czy tez dynamicznie.
Dla przykładu tablica liczb pierwszych pomiędzy Fib(46) : 1836311903 a Fib(47): 2971215073 to jest Fib(45), co daje 1134903170 x ilośc bajtów dla typu zmiennej integer. Wykorzystuje typ long więc w tym przypadku to 8 bajtów. To daje potrzebę alokacji pamięci dla tablicy o wielkości 9079225360 bajtów, a to jest 9 GB, a ja mam w komputerze tylko 8GB.
Więc twoje sugerowane rozwiązanie ze zrobieniem tablicy (bool-true) może jest lepsze, ale też ma ograniczenia i na moim kompie nie pójdziemy z obliczeniami dalej.
Tak więc jeśli rozumiesz, a pewnie tak jest, to proszę o przybliżenie jakiejś innej metody wyznaczania liczb pierwszych.
Nie wiem jak działa ten algorytm MMSieve, w twoim kodzie Java? To jest twój algorytm? Mógłbyś przybliżyć jego zasadę działania?
Będę wdzieczy chociaż za podpowiedź, jak alokuje on pamięć i czy wogóle robi w sposób podobny do Sita Erasto tworząc tablicę z liczbami. Pozdrawiam.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Brombal »

Ograniczeniem jest tablica booleanowa może posiadać jedynie tyle pól co max int stąd ograniczenie. Mam pewien algorytm w javie, który wygenerowuje nieco większe liczby pierwsze nieco wolniej ograniczeniem jest pojemność dysku twardego 1TB liczb pierwszych (2 exp13) musiałem generować 6h.
Odnośnie Twojej hipotezy sądzę, że może wyglądać zupełnie inaczej.
dla \(\displaystyle{ k \ge 1,k \in \RR}\) oraz \(\displaystyle{ n}\) naturalnego
średnia arytmetyczna \(\displaystyle{ X}\) zbioru liczb pierwszych z przedziału od \(\displaystyle{ \left\langle n, kn\right\rangle}\)
\(\displaystyle{ \lim_{n \to \infty } \left( \frac{X}{nk} \right) \rightarrow \frac{k+1}{2k}}\)
podstaw do swojego Fibonacciego

Spróbuj co da Ci taki kod.
Kod na wektorowe obliczanie w C++
Powinieneś łatwo przekonwertować.
Ukryta treść:    
Ostatnio zmieniony 5 lip 2019, o 14:16 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Re: Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

@Brombal - dzięki za wsparcie. Jestem pozytywnie zaskoczony, w jakim kierunku poszła nasza dyskusja. Dałeś mi teraz orzech do zgryzienia. Muszę przemyśleć sprawę, ale najpierw ją zrozumieć. Czasem działam bez większego zastanowienia, dlatego teraz wezmę się po prostu za eksperyment i twój kod zacznę wdrażać do działania.
Efekty może mi coś rozświetlą i wtedy mam nadzieję bedę miał powód się do Ciebie odezwać.
Najciekawsze jest to, że przypomnienie sobie znaczenia matematycznych symboli sprawia mi ciut trudności... ale mam nadzieję, że dam radę. Ciekawa formuła... jednak jeszcze zbyt tajemnicza.
Tymczasem na razie kończę i pozdrawiam.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Jan Kraszewski »

Brombal pisze:średnia arytmetyczna \(\displaystyle{ X}\) zbioru liczb pierwszych z przedziału od \(\displaystyle{ \left\langle n, kn\right\rangle}\)
\(\displaystyle{ \lim_{n \to \infty } \left( \frac{X}{nk} \right) \rightarrow \frac{k+1}{2k}}\)
No to nie wygląda dobrze. Pewnie chciałeś napisać

\(\displaystyle{ \lim_{n \to \infty } \left( \frac{X}{nk} \right) \red=\black \frac{k+1}{2k}.}\)

JK
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Brombal »

@JK Faktycznie tak chciałem napisać . Ale mnie coś podkusiło....
@Sylvi91 Podstaw złoty podział pod \(\displaystyle{ k}\) do wzoru \(\displaystyle{ \frac{k+1}{2k}}\) i zobacz co wyjdzie
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Re: Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

@Brombal Nie wiem czy Cię dobrze zrozumiałem.

Podstawienie wartości ciągu Fibonacciego do tego proponowanego przez Ciebie wzoru daje przybiżenie oscylujące wokół wartości \(\displaystyle{ 0.5}\).
Ale to nie jest żadna średnia liczb pierwszych zadanego zbioru, bo średnia atytmetyczna to z definicji suma tych liczb podzielona przez ich liczbę.
Czy to się odnosi jakoś do liczb pierwszych z zadanego przedziału tego mi nie wiadomo.
Nie wiem co miałeś dokładnie na myśli układając ten wzór. Gdyby pomożyć wynik przez Złotą liczbę to może było by to tożsame z tym co ja proponuję i formuły można by porównać.
No ale ja nie jestem w tej dziedzinie na tyle biegły, aby o liczbach pierwszych wiedzieć takie rzeczy.


\(\displaystyle{ Slp = \frac12 \Phi \\ Slp = \frac{\frac{lp_1 +lp_2 +... + lp_n}{ Ilp}}{ Wlf}}\)

Pytam tylko, czy taka zależność w zbiorze liczb pierwszych była by prawdopodobna.
\(\displaystyle{ Slp = \frac12 \Phi = \lim_{n \to \infty } \left( \frac{X}{nk} \right) \Phi \red=\black \frac{k+1}{2k} \Phi .}\) ?????

Wielka dla mnie niewiadoma.

Jeśli to są jakieś farmazony, to z góry przepraszam, ale ja tego nie potrafię sprawdzić.

Wracam do kalkulacji na podzbiorach liczb pierwszych, których granicami są liczby Fibo.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Hipotezy o liczbach pierwszych

Post autor: Brombal »

Napisałeś że:
\(\displaystyle{ Slp = \frac12 \Phi = \lim_{n \to \infty } \left( \frac{X}{nk} \right) \Phi \red=\black \frac{k+1}{2k} \Phi}\)
Ja sądzę, że jest hipotetycznie tak:
\(\displaystyle{ \lim_{n \to \infty } \left( \frac{X}{nk} \right)=\frac{k+1}{2k}}\)
gdzie kolejne wyrazy ciągu geometrycznego mają właściwość :
\(\displaystyle{ a_{n+1}=k*a_n}\)
Zauważ, że ciąg Fibonacciego mocno przypomina ciąg geometryczny gdzie \(\displaystyle{ k=\Phi}\)
czyli dla ciągu geometrycznego
\(\displaystyle{ a_{n+1}=\Phi*a_n}\)


\(\displaystyle{ \frac{\Phi+1}{2\Phi} =0,8090169943844764921779050141161... \approx \frac{\Phi }{2} =0,80901699435}\)

Podrzucam Ci program w C++ do pierwszych 4-5 razy szybszy od algorytmu liniowego i ok 20 razy od Eratostenesa
Ukryta treść:    
-- 10 lip 2019, o 11:57 --Pomyłka
\(\displaystyle{ \frac{\Phi+1}{2\Phi} =0,8090169943... = \frac{\Phi }{2} =0,8090169943...}\)
sylvi91
Użytkownik
Użytkownik
Posty: 64
Rejestracja: 10 paź 2017, o 04:40
Płeć: Mężczyzna
wiek: 47
Lokalizacja: Łódź
Podziękował: 6 razy

Hipotezy o liczbach pierwszych

Post autor: sylvi91 »

Brombal pisze: Ja sądzę, że jest hipotetycznie tak:
\(\displaystyle{ \lim_{n \to \infty } \left( \frac{X}{nk} \right)=\frac{k+1}{2k}}\)
Tego zapisu dalej nie rozumiem. Czym jest tutaj \(\displaystyle{ k}\), czym \(\displaystyle{ k+1}\), a czym \(\displaystyle{ 2*k}\)?
Najlepiej gdybyś podstawił mi jakieś konkretne liczby. Przypuszczam tylko, że \(\displaystyle{ k}\) to jakaś liczba pierwsza, a \(\displaystyle{ k+1}\) to kolejna liczba pierwsza, albo ewentualnie liczba wieksza od pierwszej o \(\displaystyle{ 1}\).

Brombal pisze: Zauważ, że ciąg Fibonacciego mocno przypomina ciąg geometryczny gdzie \(\displaystyle{ k=\Phi}\)
czyli dla ciągu geometrycznego
\(\displaystyle{ a_{n+1}=\Phi*a_n}\)
Chyba rozumiem. Jeśli \(\displaystyle{ a}\) oznacza tutaj funkcję opisującą ciąg to faktycznie taka zależność występuje. Teraz jeśli średnią arytmetyczną liczb pierwszych adekwatnie do tego równania podstawimy, to wyjdzie trochę zamieszania.
Dla zbiorów liczb naturalnych z tej zależności wyliczyć można, że średnia arytmetyczna wynosi minus \(\displaystyle{ 0.5}\).
Natomiast dla liczb pierwszych jest to trochę bardziej skomplikowane. Błąd w obliczeniach nie jest względnie dużym błędem, jednak jako wartość absolutna robi zamieszanie, bo dąży do nieskończoności zapewne.

Fragment wyniku z programu:
Gdzie:
SUM - suma zbioru liczb pierwszych.
REAL AVG i R AVG to rzeczywista średnia arytmetyczna zbioru liczb pierwszych.
AVG - szacowana średnia zbioru liczb pierwszych.
Absolute Error - błąd bezwzględny.
Relative Error - błąd względny procentowy.
Ukryta treść:    
Jeśli w mojej zastosowanej metodologii nie ma pomyłki, to taka skala błędu względnego raczej dobrze świadczy o poprawności obliczeń.
Brombal pisze: Podrzucam Ci program w C++ do pierwszych 4-5 razy szybszy od algorytmu liniowego i ok 20 razy od Eratostenesa
Dzięki. Jakoś nie miałem kiedy rozpracować tego kodu. Ale nie jest duży problem z szybkością Sita Erasto, bo zrobiłem parę optymalizacji. W głównej mierze barierą do dalszych obliczeń jest dostępna pamięć operacyjna.
Na 8 GB RAM z użyciem Sita doliczyłem do \(\displaystyle{ Fib(54)}\). Przy użyciu 8 bitów na liczbę pierwszą.
Przy użyciu 1 bita na każdą liczbę naturalną dało się policzyć jeszcze mniej, bo zbiór liczb pierwszych robi się coraz rzadszy. Gęstość spada znacznie.

Tak wygląda wynik programu po wyłuskaniu tych podstawowych wartości.
Ukryta treść:    
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: Hipotezy o liczbach pierwszych

Post autor: Brombal »

\(\displaystyle{ a_n}\) nie jest funkcją, to wyrazy ciągu geometrycznego. Podobnie jak \(\displaystyle{ fib \left( i \right)}\) jest wyrazem ciągu Fibonacciego.
\(\displaystyle{ a_{n+1}=k \cdot a_n}\) jest to przedstawienie ciągu geometrycznego - gdzie \(\displaystyle{ k}\) oznacza proporcję pomiędzy kolejnymi wyrazami ciągu \(\displaystyle{ k= \frac{a_{n+1}}{a_n}}\).
Zauważ, że
\(\displaystyle{ \lim_{ n\to \infty } \left( \frac{fib \left( n+1 \right) }{fib \left( n \right) } \right) =\Phi}\)
Czyli ciąg Fibonacciego jest nieco podobny do geometrycznego.
a jednocześnie
\(\displaystyle{ \frac{\Phi+1}{2\Phi} = \frac{\Phi }{2}}\)
Ostatnio zmieniony 19 lip 2019, o 11:27 przez AiDi, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
ODPOWIEDZ