Czy to najdłuższy ciąg liczb pierwszych?

pytanie zadane 14 września 2019 w Matematyka, fizyka, logika przez skar15 Początkujący (330 p.)

Ponad rok temu udało mi się napisać program do obliczania ciągów liczb pierwszych ( dzięki lekcjom Pana Mirka- programowanie C++)

Ciąg rozpoczyna liczba pierwsza 41 a kolejne powstają przez sumę kolejnych liczb parzystych od liczby 2.

Napotkałem informację że najdłuższy znany ciąg liczb pierwszych składa się z 29 wyrazów...super byłoby wyliczyć nowy dłuższy ciąg...

Moja wiedza matematyczna oraz programistyczna jest niewielka ale sprawdzanie zależności występowania liczb pierwszych buduje wyobraźnię..chętnie się podzielę spostrzeżeniami co do występowania liczb pierwszych i sposobu obliczenia ciągu...Liczby pierwsze występują chaotycznie jak wiadomo wśród kolejnych liczb naturalnych i nigdy nie można przewidzieć kiedy będzie następna i po jakim czasie obliczeniowym...czy gdyby działanie np. gry uzależnić od obliczania liczb pierwszych...i przyporządkować pewne wydarzenia , zachowania bohaterów gry ...czy gracz miałby wrażenie że gra jest niepowtarzalna i nieprzewidywalna ? Czy miałby wrażenie że ma do czynienie z inteligencją i wolna wolą bohaterów...nie dało by się przecież przewidzieć użytkownikowi gry kiedy i co wykona np. przeciwnik . Wznowienie gry od początku nie łączyłoby się z obliczeniami liczb pierwszych od początku lecz kontynuowaniu obliczeń dla kolejnych ( wyliczona liczba pierwsza i np skok do podprogramu).. ...analogia do upływającego bezlitośnie czasu ..a .może ten sposób się już wykorzystuje?

Poniżej ciąg liczb pierwszych składający się z 40 wyrazów..może rekordowy?

41,43,47,53,61,71,83,97,113,131,151,173,197,223,251,281,313,347,383,421,
461,503,547,593,641,691,743,797,853,911,971,1033,1097,1163,1231,1301,1373,1447
1523,1601

Pozdrawiam czytających i proszę o uwagi ...

Wiesław

2 odpowiedzi

odpowiedź 15 września 2019 przez reaktywny Nałogowiec (41,090 p.)

Temat dość ciekawy.

Tutaj pierwsze 50 milionów liczb:

https://primes.utm.edu/lists/small/millions/

Największa obecnie znana liczba to: 2^82,589,933 − 1, a number which has 24,862,048 digits when written in base 10

Jak widać składa się prawie z 25 milionów cyfr. To uniemożliwia zabawę na komputerze, chyba żaden język programowania nie wspiera tak dużych liczb, trzeba by napisać własną bibliotekę.

---

A co to jest za ciąg? Bo ani nie jest to ciąg arytmetyczny, ani geometryczny. Zauważyłem, że każdy wyraz jest większy o 2*n (chociaż sprawdzałem pobieżnie).

komentarz 15 września 2019 przez DragonCoder Nałogowiec (36,500 p.)

I warto dodac, ze na komputerze domowym sie nie da tego zrobic. Nie da sie obliczyc liczby pierwszej, bo nie ma stałego wzoru, czy rozmieszczenia ich miedzy soba, o tym mowi chyba zagadka Riemanna. Nie bez przyczyny ktos chce zaplacic 1 mln dolarow, jesli komus udaloby sie stworzyc owa zaleznosc. Sa algorytmy, zeby okreslic, czy dana liczba jest liczba pierwsza, czy nie. Ale latwo chyba sobie wyobrazić jaks moc obliczeniowa musi posiadac komputer, zeby dojsc do tak ogromnych liczb

komentarz 15 września 2019 przez reaktywny Nałogowiec (41,090 p.)

Mocy obliczeniowj nie trzeba tak bardzo wiele, dzisiejsze komputery podołają zadaniu. Liczy się tutaj RAM + Problem ze znalezieniem biblioteki do mnożenia / dzielenia bardzo dużych liczb całkowitych. I tyle.

Znalazłem biblioteki do kilkuset cyfr, a tu potrzeba conajmniej kilkadziesiąt milionów cyfr.

komentarz 15 września 2019 przez skar15 Początkujący (330 p.)

Zdaje sobie sprawę z ogromu trudności w obliczaniu bardzo wielkich liczb pierwszych....i że jest to technicznie dzisiaj niewykonalne by w nieskończoność i szybko obliczać kolejne liczby pierwsze ( gra musiałaby" umrzeć" jeśli wyczerpałyby się liczby pierwsze..ale gdyby była taka technologia to czy zaprogramowany świat gier mógłby sprawiać wrażenie że żyje swoim życiem, że jest inteligentny..nieprzewidywalny, podejmuje decyzje sam w nieoczekiwanym momencie - zależnie np. od wyliczonej sumy cyfr liczby pierwszej ..... parzysta czy nieparzysta ..wybór drogi w lewo - wybór drogi w prawo ( to taka decyzja jakby porównać że coś za nas decyduje..podświadomość) lub też wybór drogi na podstawie danych logicznych...

komentarz 15 września 2019 przez reaktywny Nałogowiec (41,090 p.)

Myślałem, że chodzi o samo obliczanie liczb :) Jeśli chodzi o wykorzystanie tego w grze to inna para kaloszy :)

Wtedy chyba szybciej byłoby sięgnąć po już obliczone LP (zapisane na dysku).

NIeprzewidywalność - tak. Ale prawde mówiąc osobiście nie widzę zastosowania LP w grach, ale może mam słabą wyobraźnię.

komentarz 15 września 2019 przez mokrowski Mędrzec (155,460 p.)

25 mln cyfr, to zakładając nawet bardzo rozrzutne gospodarowanie 1bajt na cyfrę, 23 GB RAM. Z całą pewnością da się więc policzyć na większym PC. Problem leży raczej w czasie trwania tych obliczeń i doborze algorytmu.

Do takich zabaw nadaje się biblioteka GMP

komentarz 15 września 2019 przez reaktywny Nałogowiec (41,090 p.)

Wg mnie każdy milion cyfr to około 1 MB, a nie 1 GB :) 25 MB to nie jest dużo, dziś programy operują na zdjęciach które mają kilkaset MB, a czasem ponad 1 GB.

komentarz 15 września 2019 przez mokrowski Mędrzec (155,460 p.)
edycja 15 września 2019 przez mokrowski

Racja... "niedzielna pomroczność jasna". Tym bardziej się zmieści :)

PS:

Proste obliczenie (bez testu czy liczba jest pierwsza), to ~ 5 sec. na średniej maszynie (wraz z wyświetleniem):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

int main(void) {
    mpz_t pow_result;
    mpz_t result;
    mpz_t base;

    mpz_init(base);
    mpz_init(result);

    mpz_set_ui(base, 2);
    mpz_pow_ui(pow_result, base, 82589933);
    mpz_sub_ui(result, pow_result, 1);

    gmp_printf("Liczba ((2^82589933) - 1) to %Zd\n", result);

    return EXIT_SUCCESS;
}

komentarz 15 września 2019 przez reaktywny Nałogowiec (41,090 p.)

Fajnie, że wkleiłeś kod. Nie jest skomplikowany, ale jak zajrzałem do tej biblioteki to trochę przytłoczyła mnie liczba metod / funkcji.

komentarz 15 września 2019 przez DragonCoder Nałogowiec (36,500 p.)

Czy ta biblioteka opiera sie na operacji na stringach?

komentarz 15 września 2019 przez mokrowski Mędrzec (155,460 p.)

Czy ta biblioteka opiera sie na operacji na stringach?

Oj :) Z całą pewnością nie. Oczywiście ma funkcje konwertujące ze string'a na typ numeryczny. Ma także i odwrotne konwersje oraz definicję klas do łatwiejszego użycia w C++. Siłę pokazuje przez zoptymalizowane operacje w asemblerze dla platform x86, ARM, PowerPC, ... i wielu innych. Jest dość szybka.

komentarz 15 września 2019 przez reaktywny Nałogowiec (41,090 p.)

@DragonCoder,
Wykorzystując stringi można właściwie zrobić tylko dodawanie i odejmowanie. A to trochę mało. Wtedy kod jest krótki i szybko można coś takiego wykonać. Ale użuyteczność jest niewielka.

komentarz 16 września 2019 przez DragonCoder Nałogowiec (36,500 p.)

Czemu tylko dodawanie i odejmowanie. Mozna zasymulowac pisemne mnozenie, jesli lazdy element tablica bede ze soba mnozyl i uzyje zmiennej do przechowywania czesci dziesietnych. Anomogicznie mozemy mnozyc, jedynie operacje opierajace sie na dzieleniu nie moga zostac wykorzystane.

odpowiedź 15 września 2019 przez J0ker Pasjonat (15,400 p.)

To czy liczby pierwsze występują chaotycznie nie jest wiadome w tej chwili - jeśli Hipoteza Riemanna okaże się prawdziwa, to można mówić o pewnym porządku.

Nie sądzę, żeby Pana ciąg był rekordowy pod jakimś względem - zawsze można napisać taki sam program który wypisze jedną liczbę więcej :)

Pozdrawiam i zachęcam do dalszej nauki oczywiście.

komentarz 15 września 2019 przez skar15 Początkujący (330 p.)

Witam..własnie ten chaos występowania liczb pierwszych jest ciekawy i nie ma wzoru na wskazanie występowania liczb pierwszych wśród kolejnych liczb naturalnych...dlatego sądziłem że ten ciąg który zwiększa się o 2n (czyli kolejne liczby parzyste aż do n=40) jest interesujący (bez jakiegoś praktycznego znaczenia ale wskazuje na mikro porządeczek w kilkudziesięciu liczbach)..spotkałem się i informacją że rekordowy jest ciąg liczb pierwszych o długości n=26 cc..

.i dziękuje za komentarz..pozdrawiam...

komentarz 15 września 2019 przez DragonCoder Nałogowiec (36,500 p.)

Hipoteza riemanna nie zostala obalona, ani potwierdzona, ale moim zdaniem wystepowanie te jest losowe lub jego rozwiązanie, czyt. wzor jest tak skomplikowany, ze nawet na podstawie tak duzych liczb pierwszych nie udalo sie go jeszcze znalezc.

Niby sa rozwiazania, ktore wskszuja w prawidlowa strone, ale nie sa one ogolne, tylko dla pewnych danych/przypadkow. Szczerze zastanawiam sie, co by sie stalo, gdyby ktos znalazl owy wzor, większość zabezpieczeń bszuje na duzych liczbach losowych, dlatego tak ciezko je zlamac