Prvocisla - golden part

Úvod

Autor všetkých uvedených súvislosti a metód: Robopol

Tento diel o prvočíslach bude ukážkou, ako sa dá pracovať s redukovanou Fermatovou vetou a algoritmom (prezentovaný v minulých dieloch). Výskum tejto problematiky nabaľuje ďalšie súvislosti a je možné nachádzať obrovské množstvo špecifických patternov (vzorov). Tieto vzory objavíme pri skúmaní chovania sa algoritmu (minulé diely, hlavne vylepšené hľadanie prvočísiel -2 diel).  V predchádzajúcom diely boli prezentované špeciálne prvočísla v tvare p=2ˆk+-1. Dnes sa pozrieme na schému všetkých prvočísiel, pretože každé prvočíslo sa dá zapísať ako:

Screenshot - 3_ 8jpg

Pre špeciálne prvočísla, s=1 je pattern ten najjednoduchší možný (s najkratšou periódou). Umožňuje nám však veľmi efektívne nájsť ľubovoľne veľké prvočíslo, resp. pseudoprvočíslo. To je možné na základe periódy m(i), n(i). Viac informácii v diely špeciálne prvočísla.

V prvých dieloch o prvočíslach som sa zamýšľal nad touto problematikou, či prvočísla vykazujú nejaké vzory. Dospel som k záveru na základe výskumu prezentovaného tu na blogu, že existujú a je ich pravdepodobne obrovské množstvo. V škále nekonečných čísiel je ich zrejme nekonečne veľa. No má to háčik. To sú anti vzory.Teda nevykazujú nejakú pravidelnosť, vykazujú však špecifické vlastnosti. Nedospel som k tomu skúmaním Riemannovej hypotézy, ale skúmaním malej, Fermatovej vety (presnejšie ide o geometrický aspekt malej Fermatovej vety). Všetko je to, ale prepojené a domnievam sa, že pre znalcov Riemannovej hypotézy, teda pre tých, čo naozaj rozumejú celej problematike do hĺbky, im tieto zistenia na tomto webe môžu pomôcť.  Pre mňa osobne je táto hypotéza správna (prakticky dokázaná) - pre velký počet bodov na kritickej priamke.


Príklady vzorov prvočísiel

Prezentované vlastnosti budú v tabuľkách excelu na príkladoch, pretože to je názornejšie. Z tabuliek zistíme, že pre rôzne "s" dostávame perieody T=(p-1)/2 alebo T=(p-1). V prípade, že prvočíslo má periódu T=(p-1), potom v hodnote (p-1)/2 sú hodnoty [ m(i),n(i) ] = [ 4,p-4 ]. Zložené čísla nemajú takéto periódy. Prvočísla teda okrem špeciálnych prvočísiel majú periódy velké, dlhé. Prvočísla však majú aj akratšie periódy ako T=(p-1)/2, napríklad číslo 113, 8209. Viac informácii (o periódach) v diely o algoritme na prvočísla.

príklad kde s=3

Screenshot - 3_ 8 002jpg

príklady kde s=3*3

Screenshot - 3_ 8 003jpg

Pseudo prvočísla

V niektorom z predchádzajúcich dielov som načrtol to, že by som sa chcel povenovať aj problematike pseudo prvočísiel. Malá Fermatová veta dáva v niektorých prípadoch zhodu aj pre tzv. pseudoprime. Čitateľ si môže dohľadať o čo presne ide, napr. na Wikipédii.  Pseudoprvočísla majú veľmi krátke periódy.

Pre základ a=2 v malej Fermatovej vete je najmenšie pseudoprvočíslo p=341. Pozrite sa ako elegantne ho algoritmus odhalil.

link: pseudoprvočísla (zdroj pre dáta)


vzťahy pre bunky:

m(i)=IF(MOD(G3;2)=1;$B$4-H4;(G3+2)/2)

n(i)=IF(MOD(H3;2)=1;$B$4-G4;(H3-2)/2)

pseudoprime1jpg

Dobre, skúsme to pre pseudoprvočíslo, ktoré sa objavuje pre viacero základov „a“ p=8911.

begin

pseudoprime2jpg

End

pseudoprime3jpg

Perióda prvočísla (v algoritme) tesne súvisí z jeho rozkladom na prvočísla.

Príklad:

341- má v algoritme periódu 10, rozklad čísla je 11.31 (najmenšie prvočíslo 11)

561- má v algoritme periódu 40, rozklad čísla je 561=3.11.17 (najmenšie prvočíslo 3)

1387- má v algoritme periódu 18, rozklad čísla je 1387=19.73 (najmenšie prvočíslo 19)

2047- má v algoritme periódu 11, rozklad čísla je 2047=23.89 (najmenšie prvočíslo 23)

...

Pre odhalenie zloženého čísla: Zložené číslo nesplní podmienku (p-1)=N,  -> N/perioda=integer. Pre zložené číslo nikdy nebude perióda celočíselným násobkom N ( s výnimkou pseudoprvočísiel, ktoré Fermatova veta nedokáže filtrovať).

Toto je veľmi zaujímavé z toho pohľadu, že efektivita takéhoto prehľadávania periódy  rastie pre rozklady, kde sú väčšie prvočinitele. Naopak kde sú rozklady na menších prvočiniteľov rastie efektivita klasického delenia (napr. Eratosovo sito). To sa dá použiť ako kombinácia metód (jedna z možnosti).

Existujú však pseudoprvočísla aj s veľmi krátkymi periódami, teda existujú aj pseudoprvočísla pre špeciálne prvočísla v tvare p+-1=2^k . Veľkosť periódy ich neodhalí!