Algorytm poszukiwania liczb pierwszych Mersenne'a

[omnia_...@interia.pl]

Przedstawiam Wam tu jeszcze jeden test na pierwszość liczb Mersenne'a. Raczej jeszcze nie znany. No i niestety pewnie niepraktyczny, ponieważ wymaga wykonywania obliczeń na liczbach jeszcze większych, niż liczby testowane. Nie podaję twierdzeń, ani dowodów twierdzeń na których jest oparty (nie wszystkie mam gotowe, a popracowałbym nad nimi w wypadku, gdyby algorytm rzeczywiście miał szanse na jakąś "karierę").

Opis algorytmu zamieszczam pod tym linkiem:

http://www.matematyka.pl/329187.htm#p5069801

ponieważ odczytanie go w składni liniowej na pewno byłoby kłopotliwe. Co myślicie o tym algorytmie?

[bartekltg]

W dniu 2013-02-24 18:31, omnia_...@interia.pl pisze:

> Przedstawiam Wam tu jeszcze jeden test na pierwszość liczb
> Mersenne'a. Raczej jeszcze nie znany. No i niestety pewnie
> niepraktyczny, ponieważ wymaga wykonywania obliczeń na liczbach
> jeszcze większych, niż liczby testowane. Nie podaję twierdzeń, ani
> dowodów twierdzeń na których jest oparty (nie wszystkie mam gotowe, a
> popracowałbym nad nimi w wypadku, gdyby algorytm rzeczywiście miał
> szanse na jakąś "karierę").

Na boku sprawy algorytmu.
Rozumiem, że możesz nie podawać od razu dowodów,
by np nie zaciemniać wypowiedzi, ale twierdzenie
(tzn założenia i teza) jednak wypadałoby. Tylko
tak ktokolwiek jest w stanie się do tego odnieść.
To bardzo ułatwie czytania, ponieważ umożliwia
uporządkowanie toku myślenia.
Matematyk czytając taki opis, gdy trafia na stwierdzenie,
że coś jest jakośtam, zastanawia się, czy rozumie dlaczego.
Jeśli tak mimochodem wrzucasz stwierdzenie, które traktujesz
jako twierdzenie, jest dowód jest skomplikowany
a nie dokończony, to "zawieszasz" na chwilę matematyka.
Trzeba mu dać informację, że ta myśl jest szczególna.

Przydało by się też przy takim twierdzeniu powiedzieć,
czy to jest powszechnie znane, nieznane, ale sam znasz
dowód, czy wreszcie, że jest to problem otwarty
(przynajmniej wg Twojej wiedzy).


pzdr
bartekltg

[omnia_...@interia.pl]

> Na boku sprawy algorytmu.
>
> Rozumiem, że możesz nie podawać od razu dowodów,
>
> by np nie zaciemniać wypowiedzi, ale twierdzenie
>
> (tzn założenia i teza) jednak wypadałoby. Tylko
>
> tak ktokolwiek jest w stanie się do tego odnieść.
>
> To bardzo ułatwie czytania, ponieważ umożliwia
>
> uporządkowanie toku myślenia.
>
> Matematyk czytając taki opis, gdy trafia na stwierdzenie,
>
> że coś jest jakośtam, zastanawia się, czy rozumie dlaczego.
>
> Jeśli tak mimochodem wrzucasz stwierdzenie, które traktujesz
>
> jako twierdzenie, jest dowód jest skomplikowany
>
> a nie dokończony, to "zawieszasz" na chwilę matematyka.
>
> Trzeba mu dać informację, że ta myśl jest szczególna.
>
>
>
> Przydało by się też przy takim twierdzeniu powiedzieć,
>
> czy to jest powszechnie znane, nieznane, ale sam znasz
>
> dowód, czy wreszcie, że jest to problem otwarty
>
> (przynajmniej wg Twojej wiedzy).

Nie śledzę publikacji matematycznych (tylko niektóre), więc nie wiem na pewno, czy nikt nigdy nie sformułował podobnego algorytmu. Jednak na pewno nie jest on powszechnie znany. Podobnie jest z twierdzeniami na których opieram algorytm - najprawdopodobniej większość z nich nie jest znana, na wszystkie mam dowody, tylko, że powiedzmy w luźnych notatkach i żeby to jakoś spójnie przedstawić musiałbym włożyć w to trochę pracy.

[omnia_...@interia.pl]

UWAGA: właśnie przypomniałem sobie o twierdzeniu które znacznie pozwala zmniejszyć wielkość ciągów użytych w algorytmie za pomocą których weryfikujemy liczby Mersenne'a. Dlatego mam prośbę, aby z ALGORYTMEM zapoznać się w moim 2 poście na forum (a nie tym zaczynającym wątek) w którym widnieje poprawiony algorytm.

[omnia_...@interia.pl]

Algorytm pozwola na ustalenie w prosty sposób różnych własności. Na przykład, że wszystkie liczby Mersenn'a postaci 2^(3n)-1 są podzielne przez 7, a wszystkie liczby postaci 2^(4n)-1 przez 5. Natomiast wszystkie liczby 2^(2n)-1 przez 3. A na przykład liczby postaci 2^(18n)-1 przez 19. Z kolei przez 101 są podzielne wszystkie liczby postaci 2^(102n)-1. Ciekawe.

Znalazłem też na przykład wzór na liczby Mersenne'a podzielne przez 3*5*7*9*11*13*15. Są to liczby postaci 2^(540n)-1.

[J.F.]

Dnia Sun, 24 Feb 2013 15:56:49 -0800 (PST), omnia_...@interia.pl
> Algorytm pozwola na ustalenie w prosty spos�b r�nych w�asno�ci. Na
> przyk�ad, �e wszystkie liczby Mersenn'a postaci 2^(3n)-1 s� podzielne

> przez 7, a wszystkie liczby postaci 2^(4n)-1 przez 5. Natomiast

> wszystkie liczby 2^(2n)-1 przez 3. A na przyk�ad liczby postaci
> 2^(18n)-1 przez 19. Z kolei przez 101 sďż˝ podzielne wszystkie liczby
> postaci 2^(102n)-1. Ciekawe.

Wcale nieciekawe. Czytales chocby w wikipedii rozwiniecie ?

> Znalaz�em te� na przyk�ad wz�r na liczby Mersenne'a podzielne przez
> 3*5*7*9*11*13*15. Sďż˝ to liczby postaci 2^(540n)-1.

A to moze i ciekawe ... a moze i nie :-)

J.

[omnia_...@interia.pl]

W dniu poniedziałek, 25 lutego 2013 01:26:02 UTC+1 użytkownik J.F. napisał:
> Dnia Sun, 24 Feb 2013 15:56:49 -0800 (PST), omnia_...@interia.pl
>
> > Algorytm pozwola na ustalenie w prosty spos�b r�nych w�asno�ci. Na
>
> > przyk�ad, �e wszystkie liczby Mersenn'a postaci 2^(3n)-1 s� podzielne
>
> > przez 7, a wszystkie liczby postaci 2^(4n)-1 przez 5. Natomiast
>
> > wszystkie liczby 2^(2n)-1 przez 3. A na przyk�ad liczby postaci
>
> > 2^(18n)-1 przez 19. Z kolei przez 101 sďż˝ podzielne wszystkie liczby
>
> > postaci 2^(102n)-1. Ciekawe.
>
>
>
> Wcale nieciekawe. Czytales chocby w wikipedii rozwiniecie ?

Faktycznie za pomocą tego rozwinięcia można tworzyć pewne szczególne przypadki złożonych liczb Mersenne'a. Ale ma ono także swoje ograniczenia, jak sądzę. Jak na przykład za jego pomocą znaleźć liczby Mersenne'a podzielne przez 987654321?

Mnie na przykład udało się ustalić, że to liczby postaci 2^(3873143n)-1. Przy czym zajęło to mojemu komputerowi kilka minut.

[Oli]

Poniewa� spokojnie przyjmujesz biczowanie, ku doedukowaniu podsy�am:

U�ytkownik omnia_...@interia.pl napisa�:

> Algorytm pozwola na ustalenie w prosty spos�b r�nych w�asno�ci.
>

> Znalaz�em te� na przyk�ad wz�r na liczby Mersenne'a podzielne przez 3*5*7*9*11*13*15. S� to liczby postaci 2^(540n)-1.
>

Liczby 2^(540n)-1 s� podzielne przez ka�d� liczb� z tego ci�gu
{ {3, 5, 7, 9, 11, 13, 15, 19, 31, 37, 41, 61, 73, 109, 151, 181,
271, 331, 541, 631, 811, 1321, 15121, 23311, 30241, 49681, 54001,
87211, 246241, 262657, 279073, 348031, 18837001, 29247661,
49971617830801, 165041853060421, 385838642647891, 166242935471754241}

oraz przez wszelkie mo�liwe kombinacje iloczyn�w z tego ci�gu.
( zadanie za 2 gr , ile jest ��cznie podzielnik�w ?)

Do tego nie potrzeba twojego algorytmu ( ba nie jest mo�liwe znalezienie wszystkich), tylko wiedzy o
faktoryzacji liczb 2^k-1 ( gdzie k jest liczb� z�o�on�) + komputer i funkcja modulo

--
Oli

[Oli]

U�ytkownik omnia_...@interia.pl napisa�:

> Algorytm pozwola na ustalenie w prosty spos�b r�nych w�asno�ci. Na przyk�ad, �e wszystkie liczby Mersenn'a

> postaci 2^(3n+3)-1 sďż˝ podzielne przez 7, a wszystkie liczby postaci 2^(4n+4)-1 przez 5. Natomiast wszystkie
>liczby 2^(2n+2)-1 przez 3. A na przyk�ad liczby postaci 2^(18n+18)-1 przez 19. Z kolei przez 101 s� podzielne
> wszystkie liczby postaci 2^(102n+102)-1. Ciekawe.
>
Ostatnie to nie 101 a 103
Ciekawe b�dzie jak to b�dzie systematyczne dane a nie przypadkowe dane.

Liczby 2^(k(n+1))-1 s� podzielne przez mn�stwo liczb.
Dzielnikiem jest na pewno k+1 dla k, kt�rego k+1 jest pierwsze
czyli dla k {2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52.....}
Niestety nic tu ciekawego, tak po prostu musi byďż˝.

Ten sam tekst mo�emy powt�rzy� (czyli dzielnikiem jest na pewno k+1 - pierwsze) dla
liczb 2^(k(n+m))-1 (m dowolna liczba ca�kowita za wyj�tkiem -1)

I dlatego w twoim innym przyk�adzie 2^(540 n)-1, dzielnikiem jest 541 bo
k = 540 , m=0 , k+1 = 541 - jest pierwsza

--
Oli

[bartekltg]

W dniu 2013-02-25 04:55, omnia_...@interia.pl pisze:

>> Wcale nieciekawe. Czytales chocby w wikipedii rozwiniecie ?
>
> Faktycznie za pomocą tego rozwinięcia można tworzyć pewne szczególne
> przypadki złożonych liczb Mersenne'a. Ale ma ono także swoje
> ograniczenia, jak sądzę. Jak na przykład za jego pomocą znaleźć
> liczby Mersenne'a podzielne przez 987654321?
>
> Mnie na przykład udało się ustalić, że to liczby postaci
> 2^(3873143n)-1. Przy czym zajęło to mojemu komputerowi kilka minut.

Jestem niemal pewny, że przez 987654321 podzielne jest 2^(3873144*n)-1

Wyliczone w sekundę, całość algorytmu sprowadza się do
tego, że


d|2^x-1 <=> 2^x-1 == 0 (mod d) <=> 2^x == 1 (mod d)

a liczby postaci 2^n dla n = 1,2... możemy liczyć
sukcesywnie jedna po drugiej w pojedynczym rejestrze.

Kod:


#include <cstdio>
#include <cmath>

int main()
{
long long int x, licznik; //zawyżone, starczy int,
// na x64 nie ma znaczenia
const long long int dzielnik = 987654321;

x=1;
licznik=0;
while(licznik<100000000)
{
licznik++;
x=(x*2)%dzielnik;

//niezmiennik: x == (2^licznik) mod dzielnik

if (x==1) printf("%lld\n",licznik);
}
return 0;
}


pzdr
bartekltg

[bartekltg]

W dniu 2013-02-26 03:29, omnia_...@interia.pl pisze:

>>> Wyliczone w sekundę, całość algorytmu sprowadza się do
>>>
>>> tego, że
>>>
>>>
>>>
>>>
>>>
>>> d|2^x-1 <=> 2^x-1 == 0 (mod d) <=> 2^x == 1 (mod d)
>>>
>>>
>>>
>>> a liczby postaci 2^n dla n = 1,2... możemy liczyć
>>>
>>> sukcesywnie jedna po drugiej w pojedynczym rejestrze.

> Rozumiem. Ja z kolei liczyłem to w taki sposób, że dla dzielnika d
> tworzyłem ciąg:
>
> f(x) = 0,5*x+d - gdy x nieparzyste f(x) = x/2 - gdy x parzyste
>
> I sprawdzałem po ilu iteracjach ciąg się zapętli. Ilość iteracji
> wskazuje wykładnik liczby Mersenne'a. Największy wynik jaki uzyskałem
> w kilkadziesiąt sekund to, że 99999999999999 dzieli liczby
> (2565451980n)-1.

O, to jest ciekawe, przynajmniej od strony teoretycznej.
Od jakiego x zaczynasz?

Naszkicujesz dowód, dlaczego ilość iteracji to wykładnik naszej liczby?

pzdr
bartekltg

[omnia_...@interia.pl]

> ( zadanie za 2 gr , ile jest łącznie podzielników ?)
10848333148993832953358283699495717194630934863463816093697?

W dniu poniedziałek, 25 lutego 2013 18:07:32 UTC+1 użytkownik Oli napisał:
> U�ytkownik omnia_...@interia.pl napisa�:
>
> > Algorytm pozwola na ustalenie w prosty spos�b r�nych w�asno�ci. Na przyk�ad, �e wszystkie liczby Mersenn'a
>
> > postaci 2^(3n+3)-1 sďż˝ podzielne przez 7, a wszystkie liczby postaci 2^(4n+4)-1 przez 5. Natomiast wszystkie
>
> >liczby 2^(2n+2)-1 przez 3. A na przyk�ad liczby postaci 2^(18n+18)-1 przez 19. Z kolei przez 101 s� podzielne
>
> > wszystkie liczby postaci 2^(102n+102)-1. Ciekawe.
>
> >
>
> Ostatnie to nie 101 a 103

Przy 101 jest chyba błąd, bo wychodzi mi teraz, że liczby podzielne przez 101 to 2^(100n)-1, a przez 103 liczby 2^(51n)-1.

Pomyliłem się tu w tych kilku przykładach o +/- 1, ponieważ do obliczonego przez program wyniku muszę zawsze dodać 1 i zapomniałem o tym kilka razy.

> Jestem niemal pewny, że przez 987654321 podzielne jest 2^(3873144*n)-1

Racja. Pomniejszyłem przez nieuwagę wykładnik o 1.

> Wyliczone w sekundę, całość algorytmu sprowadza się do
>
> tego, że
>
>
>
>
>
> d|2^x-1 <=> 2^x-1 == 0 (mod d) <=> 2^x == 1 (mod d)
>
>
>
> a liczby postaci 2^n dla n = 1,2... możemy liczyć
>
> sukcesywnie jedna po drugiej w pojedynczym rejestrze.

Rozumiem. Ja z kolei liczyłem to w taki sposób, że dla dzielnika d tworzyłem ciąg:

f(x) = 0,5*x+d - gdy x nieparzyste
f(x) = x/2 - gdy x parzyste

I sprawdzałem po ilu iteracjach ciąg się zapętli. Ilość iteracji wskazuje wykładnik liczby Mersenne'a. Największy wynik jaki uzyskałem w kilkadziesiąt sekund to, że 99999999999999 dzieli liczby 2^(2565451980n)-1.

Mam jeszcze pytanie czy pytanie o to czy dla dowolnej liczby nieparzystej można znaleźć liczbę Mersenne'a którą ta liczba dzieli jest rozstrzygalne w jakiś sposób, czy to problem otwarty?

[omnia_...@interia.pl]

> O, to jest ciekawe, przynajmniej od strony teoretycznej.
>
> Od jakiego x zaczynasz?

Obliczamy tylko jeden ciąg dla liczby x=1.

> Naszkicujesz dowód, dlaczego ilość iteracji to wykładnik naszej liczby?

Postaram się mniej więcej wyjaśnić dlaczego tak się dzieje, nie mam gotowego dowodu. Dlatego sam uznaję ten fakt jeszcze za hipotezę, ale jest ona raczej w zasięgu nawet kogoś takiego jak ja.

[bartekltg]

W dniu 2013-02-26 08:40, omnia_...@interia.pl pisze:

Skąd ten nieporządek w odpowiedzi? Wysyłasz po dwa razy,
dodając nową treść wrzucasz też znów to samo (normalnie
nie zauważyłbym tych nowych 2 linijek na końcu),
i nie w odpowiedzi na post, który by logicznie na to zasługiwał,
ale za każdym razem na korzeń wątku?

>> Wyliczone w sekundę, całość algorytmu sprowadza się do
>> tego, że
>> d|2^x-1 <=> 2^x-1 == 0 (mod d) <=> 2^x == 1 (mod d)
>> a liczby postaci 2^n dla n = 1,2... możemy liczyć
>> sukcesywnie jedna po drugiej w pojedynczym rejestrze.
>
> Rozumiem. Ja z kolei liczyłem to w taki sposób, że dla dzielnika d
> tworzyłem ciąg:
>
> f(x) = 0,5*x+d - gdy x nieparzyste f(x) = x/2 - gdy x parzyste
>
> I sprawdzałem po ilu iteracjach ciąg się zapętli. Ilość iteracji
> wskazuje wykładnik liczby Mersenne'a. Największy wynik jaki uzyskałem
> w kilkadziesiąt sekund to, że 99999999999999 dzieli liczby
> 2^(2565451980n)-1.

796114956

58s wspomnianym bruteforce. W sumie powiny być tego samego
rzędu, bo robimy tyle samo iteracji (tyle, ile wykładnik wyniku).

Na pewno da się to poprawić.

> Mam jeszcze pytanie czy pytanie o to czy istnieje liczba Mersenne'a
> podzielna przez dowolną liczbę nieparzystą jest rozstrzygalne w jakiś
> łatwy sposób, czy to problem otwarty?

Dość łatwy. Nie trzeba przekombinować, tylko wprost
policzyć 2^n modulo dzielnik. Jeśli wynik to 1, mamy podzielność
liczby 2^n-1 przez dzielnik.

A potęgowanie możemy wykonać algorytmem potęgowania binarnego modulo.
http://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania

Spreparowałem specjalne liczby na podstawie
http://en.wikipedia.org/wiki/Mersenne_prime#Factorization_of_composite_Mersenne_numbers
dzielnik stamtąd, wykładnik to 41521* liczba podobnego rzędu
oto wynik:

reszta z dzielenia 2^6882692757836160374606182621936716251267028759-1
przez 41602235382028197528613357724450752065089 = 0
czas 0.007s

Złożoność czasowa to m*d^2,
gdzie d to liczba cyfr w dzielniku, a m liczba cyfr wykładnika.

Skorzystałem z malutkiej biblioteczki http://www.ttmath.org


Kod:

#include <iostream>
#include <cmath>
#include <time.h>
#include <ttmath\ttmath.h>

using namespace std;

int main()
{
clock_t start,end;
ttmath::UInt<10> dzielnik="41602235382028197528613357724450752065089";
ttmath::UInt<10>
wykladnik="6882692757836160374606182621936716251267028759";
ttmath::UInt<10> z,y,m;

start = clock();
y=1;
z=2;
m=wykladnik;
while (m>0)
{
if (m%2==1) y=(y*z)%dzielnik;
m = m/2;
z=(z*z)%dzielnik;
}
y=y-1;
cout<<"reszta z dzielenia 2^"<<wykladnik<<"-1 przez "<<dzielnik<<" =
"<<y<<endl;
cout<<"czas "<<((float)(clock()-start))/CLOCKS_PER_SEC <<"s"<<endl;
return 0;
}

Długie to nie jest.

BTW, wkładając tam liczby 660 cyfrowe (i zmieniając używane
liczby na UInt<200>) obliczenia zajmują 0.5s.

pzdr
bartekltg

[omnia_...@interia.pl]

> Skąd ten nieporządek w odpowiedzi?

W czasie kiedy pisałeś odpowiedź usunąłem swoją wypowiedź, korzystając, że nikt jeszcze nie dodał odpowiedzi, bo był tam jakiś błąd i chciałem ją wysłać jeszcze raz. Ale zanim to zrobiłem Ty napisałeś już swoją odpowiedź ;)

> 796114956
>
>
>
> 58s wspomnianym bruteforce. W sumie powiny być tego samego
>
> rzędu, bo robimy tyle samo iteracji (tyle, ile wykładnik wyniku).

Mi wyszło dokładnie 34 s.

> > Mam jeszcze pytanie czy pytanie o to czy istnieje liczba Mersenne'a
>
> > podzielna przez dowolną liczbę nieparzystą jest rozstrzygalne w jakiś
>
> > łatwy sposób, czy to problem otwarty?
>
>
>
> Dość łatwy. Nie trzeba przekombinować, tylko wprost
>
> policzyć 2^n modulo dzielnik. Jeśli wynik to 1, mamy podzielność
>
> liczby 2^n-1 przez dzielnik.

Tak jak pisaliśmy wcześniej, ale chodzi mi o to skąd mamy pewność, że algorytm dla dowolnie wybranego dzielnika się zatrzyma?

> A potęgowanie możemy wykonać algorytmem potęgowania binarnego modulo.
>
> http://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania
>
>
>
> Spreparowałem specjalne liczby na podstawie
>
> http://en.wikipedia.org/wiki/Mersenne_prime#Factorization_of_composite_Mersenne_numbers
>
> dzielnik stamtąd, wykładnik to 41521* liczba podobnego rzędu
>
> oto wynik:
>
>
>
> reszta z dzielenia 2^6882692757836160374606182621936716251267028759-1
>
> przez 41602235382028197528613357724450752065089 = 0
>
> czas 0.007s

I wykonałeś te obliczenia tą metodą "bruteforce"? Nie rozumiem w ogóle jak znalazłeś tą liczbę Mersenne'a. Nie sądziłem, że takie liczby są w zasięgu do jakichkolwiek dzieleń.

Czym jest "UInt<200>"?

[omnia_...@interia.pl]

> > > Mam jeszcze pytanie czy pytanie o to czy istnieje liczba Mersenne'a
> >
> > > podzielna przez dowolną liczbę nieparzystą jest rozstrzygalne w jakiś
> >
> > > łatwy sposób, czy to problem otwarty?
> >
> >
> >
> > Dość łatwy. Nie trzeba przekombinować, tylko wprost
> >
> > policzyć 2^n modulo dzielnik. Jeśli wynik to 1, mamy podzielność
> >
> > liczby 2^n-1 przez dzielnik.

> Tak jak pisaliśmy wcześniej, ale chodzi mi o to skąd mamy pewność, że algorytm dla dowolnie wybranego dzielnika się zatrzyma?

Właściwie chyba mogę cofnąć to pytanie, bo nie wiadomo czy złożonych liczb Mersenn'a jest nieskończenie wiele. A gdyby było ich skończenie wiele, to byłoby także skończenie wiele dzielników, które je dzielą bez reszty. W takim razie być może pytanie czy liczb złożonych Mersenne'a jest nieskończenie wiele będzie można sprowadzić do pytania czy wszystkie ciągi:

f(x)= x/2 + d/2 - gdy x nieparzyste

f(x) = x/2 - gdy x parzyste

dla x=1 i dowolnego d się zapętlają.

[Oli]

bartekltg napisał:

> Spreparowałem specjalne liczby na podstawie
> http://en.wikipedia.org/wiki/Mersenne_prime#Factorization_of_composite_Mersenne_numbers
> dzielnik stamtąd, wykładnik to 41521* liczba podobnego rzędu
> oto wynik:
>
> reszta z dzielenia 2^6882692757836160374606182621936716251267028759-1
> przez 41602235382028197528613357724450752065089 = 0

Sam spreparowałeś te liczby ??

bo najmniejsza liczba, która jest podzielna przez 41602235382028197528613357724450752065089 jest 2^41521 -1 ;)

Twój przykład to 2^(41521*n) - 1 gdzie n=165764137613163468476341673416746134516679

Zacytowany pre Ciebie program umożliwia weryfikację ale nie ma możliwości typowania wykładnika i dzielnika

PS. dyskusja odbiegła od tematu wątku, wiec zmieniłem tytuł

--
Oli

[Oli]

Użytkownik Oli napisał:

> bartekltg napisał:
>
>> Spreparowałem specjalne liczby na podstawie
>> http://en.wikipedia.org/wiki/Mersenne_prime#Factorization_of_composite_Mersenne_numbers
>> dzielnik stamtąd, wykładnik to 41521* liczba podobnego rzędu
>> oto wynik:

>

> bo najmniejsza liczba, która jest podzielna przez 41602235382028197528613357724450752065089 jest 2^41521 -1 ;)

I'm sorry, nie zauważyłem, że wcześniej sam napisałeś "41521*" a przykład dobrałeś do weryfikacji napisanego
algorytmu

--
Oli

[bartekltg]

W dniu 2013-02-27 17:30, omnia_...@interia.pl pisze:

>
>>> Mam jeszcze pytanie czy pytanie o to czy istnieje liczba
>>> Mersenne'a
>>
>>> podzielna przez dowolną liczbę nieparzystą jest rozstrzygalne w
>>> jakiś
>>
>>> łatwy sposób, czy to problem otwarty?
>>
>>
>>
>> Dość łatwy. Nie trzeba przekombinować, tylko wprost
>>
>> policzyć 2^n modulo dzielnik. Jeśli wynik to 1, mamy podzielność
>>
>> liczby 2^n-1 przez dzielnik.
>
> Tak jak pisaliśmy wcześniej, ale chodzi mi o to skąd mamy pewność, że
> algorytm dla dowolnie wybranego dzielnika się zatrzyma?

Oj, źle zrozumiałem pytanie.

Napisałem przydługi post z linkami do grupy multiplikatywnej,
cyklicznej, chińskiego twierdzenie o resztach etc.
Ale wszytko sprowadziło się do udowodnienia tego:)

http://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29

Dla każdej liczby m względnie pierwszej z _a_ mamy
a^phi[n] -1 = 0 (mod n)

phi[n] to funkcja Eulera, czyli liczba <=n liczb względnie
pierwszych z _n_.
http://pl.wikipedia.org/wiki/Funkcja_%CF%86

Nieparzysta liczba _n_ jest względnie pierwsza z 2, więc
zawsze

2^phi[n] - 1 jest podzielne przez _n_.

Co ważne, phi[n]<n.


Dodatkowo, k=phi[n] wyznacza nam liczbę Mersenne'a
która dzieli się na _n_, ale nie daje nam najmniejeszej
takiej liczby.

Choćby przypadek z wiki:
http://en.wikipedia.org/wiki/Mersenne_prime#Factorization_of_composite_Mersenne_numbers
In[21]:= x = 41602235382028197528613357724450752065089;

Funkcja Eulera od tej liczbt jest dość duża

In[26]:= phi = EulerPhi[x]
Out[26]= 41602221299144638729525712747024114909856

CO nie dziwi patrząc na jej rozkład.
In[23]:= FactorInteger[x]
Out[23]= {{2989513, 1}, {249375127, 1}, {55803711703045241786952239,
1}}

Ala jak pamiętamy, istaniła znacznie mniejsza l.Mersennea
dzieląca się na x.

In[24]:= w = 41521;
PowerMod[2, w, x]
Out[25]= 1

:)


Jeśli przyjrzysz się dowodowi tego twierdzenia korzystającego
z grup, albo dowodowi Małego Twierdzenia Fermata, widać, że
niezłymi kandydatami na ta liczby są wszystkie dzielniki
liczby phi[n]. Co potwierdza nam też nasz przykład:

In[28]:= Mod[phi, w]
Out[28]= 0

In[29]:= FactorInteger[phi]
Out[29]= {{2, 5}, {3, 3}, {7, 1}, {11, 1}, {13, 1},
{__41521__, 3}, {674649119, 1}, {996064193881, 1}}


Chwile bym musiał się zastanowić, czy nie mogą
istnieć inne wykładniki dla liczb Mersenne'a
podzielnych przez zadane n, ale wątpie.
A jeśli tak, to znacząco przyspiesza algorytm wyszukiwania.

In[141]:= x = 38746378592365932659594769345;
phi = EulerPhi[x]

Out[142]= 20664735249261830751783876960

In[143]:= wykladniki = Divisors[phi];
In[144]:= reszty = PowerMod[2, wykladniki, x] - 1;
In[145]:= Pick[wykladniki, reszty, 0]

Out[145]= {861030635385909614657661540, 1722061270771819229315323080, \
2583091906157728843972984620, 3444122541543638458630646160, \
5166183812315457687945969240, 6888245083087276917261292320, \
10332367624630915375891938480, 20664735249261830751783876960}


Dla x=
5645456435345738746378592365932659594769345;
najmniejszy wykładnik
299906685318216811177603563089766662340

x=78564556456435345738746378592365932659594769345
m=388409043155410697993432090901387109356392340

Czas działania w sekundach, ale przy tym zapisie
bardzo dużo zależy od liczby dzielników.

>
> I wykonałeś te obliczenia tą metodą "bruteforce"? Nie rozumiem w
> ogóle jak znalazłeś tą liczbę Mersenne'a. Nie sądziłem, że takie
> liczby są w zasięgu do jakichkolwiek dzieleń.

Jak wspomnialem na początku, zaszla pomyłka. Twoje pytania
o istnienie rozwiązania zrozumialem jako pytania
o sprawne sprawdzenia podzielności zadanej pary.

Te liczby nie są takie duże, nie liczyłem oczywiście
2^6882692757836160374606182621936716251267028759,
ale
2^6882692757836160374606182621936716251267028759 mod
41602235382028197528613357724450752065089
A do tego na dobrą sprawę potrzebowałem liczb 82 cyfrowych.

> Czym jest "UInt<200>"?

Liczba całkowita bez znaku o 32*200 bitach,
niecałe dwa tysiące liczb dziesiętnych,
z dość lekkiej, małej i niedopracowanej biblioteczki.
Do porządnych zastosowań są kombajny jak to:
http://gmplib.org/

A w obliczaniach używa się większych liczby.
Największa liczba Mersenne'a zajmuje kilka megabajtów,
17 milionów cyfr dziesiętnych.
A policzenie pi do miliarda miejsc po przecinku nie
przekracza możliwości domowego komputera.

pzdr
bartekltg

[bartekltg]

W dniu 2013-02-27 23:43, Oli pisze:

>
> Zacytowany pre Ciebie program umożliwia weryfikację ale nie ma
> możliwości typowania wykładnika i dzielnika

Tak, coś mi sie przewidziało i odpowiedziałem na inne pytanie.

Za to obok rzucam propozycję, jakie liczby są kandydatami
na liczbę Mersene'a podzielnymi przez zadane n są liczby
2^m-1 gdzie m jest dzielnikiem phi[n].
Phi - funkcja eulera. http://pl.wikipedia.org/wiki/Funkcja_%CF%86
a dla m=phi[n] podzielność na pewno występuje
[ http://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29 ]


pzdr
barteklg

[bartekltg]

W dniu 2013-02-27 22:56, omnia_...@interia.pl pisze:

>>>> Mam jeszcze pytanie czy pytanie o to czy istnieje liczba
>>>> Mersenne'a
>>>
>>>> podzielna przez dowolną liczbę nieparzystą jest rozstrzygalne w
>>>> jakiś
>>>
>>>> łatwy sposób, czy to problem otwarty?
>>>
>>>
>>>
>>> Dość łatwy. Nie trzeba przekombinować, tylko wprost
>>>
>>> policzyć 2^n modulo dzielnik. Jeśli wynik to 1, mamy podzielność
>>>
>>> liczby 2^n-1 przez dzielnik.
>
>> Tak jak pisaliśmy wcześniej, ale chodzi mi o to skąd mamy pewność,
>> że algorytm dla dowolnie wybranego dzielnika się zatrzyma?
>
> Właściwie chyba mogę cofnąć to pytanie, bo nie wiadomo czy złożonych
> liczb Mersenn'a jest nieskończenie wiele. A gdyby było ich skończenie

Wróć i przemyśl co napisałeś:)

Nie wiadomo, czy jest skończenie wiele _pierwszych_ liczb
Mersenne'a. A te z definicji nas nie interesują,
bo nie są podzielne na nic, poza samym sobą;)

> wiele, to byłoby także skończenie wiele dzielników, które je dzielą
> bez reszty. W takim razie być może pytanie czy liczb złożonych
> Mersenne'a jest nieskończenie wiele będzie można sprowadzić do
> pytania czy wszystkie ciągi:

Oczywiście, że złożonych liczb Mersena jest nieskończenie wiele,
bo liczb naturalnych jest nieskończenie wiele, a każda
n \in N ma swoją liczbę M 2^n-1 ;)

pzdr
bartekltg

[omnia_...@interia.pl]

> Oczywiście, że złożonych liczb Mersena jest nieskończenie wiele

Do reszty ustosunkuję się później. A tak na szybko, tu:

http://www.matematyka.net/index.php/teoria/wszystko-o-liczbach/ciekawe-liczby

piszą: "Nie wiadomo, czy wśród liczb Mersenne'a jest nieskończenie wiele liczb pierwszych, nie wiadomo też, czy wśród tych liczb jest nieskończenie wiele liczb złożonych."

To jakaś pomyłka? Czy chodzi im o coś innego?

[bartekltg]

W dniu 2013-02-28 18:37, omnia_...@interia.pl pisze:

Nie pomyłka, tylko bałągan w nazewnictwie. Są dwie
różne definicje liczby Mersenne.
Jedni piszą, że to dowolna liczba 2^n-1 dla n naturalnych,
inni, że tylko n będących liczbami pierwszymi.

W całym tym wątku korzystałeś (jak i reszta) z pierwszej
definicji. Widać to po liczbach, które wrzucasz
"2^(18n+18)-1", "2^(540*n)" te wykładniki na pewno nie są pierwsze;)

I przy niej nie ma wątpliwości, że złożonych liczb
postaci 2^n-1 jest nieskończenie wiele, będą to choćby
wszystkie 2^(2n)-1 = (2^n-1)(n^2+1) ;)

A ile jest wśród 2^p-1 (p pierwsze) liczb złożonych
jest osobnym problemem.

pzdr
bartekltg