Matematické Fórum

liamlim · 06. 05. 2016 22:53

Zdravím.

Vymyslel jsem takový zajímavý algoritmus na počítání všech prvočísel tvaru $n^2+1$ . Myslím si, že jsem též dokázal jeho správnost a když se naprogramuje, dává docela zajímavé výsledky.

Následující je poněkud dlouhý program C#. Asi není nejlépe napsán, jen jsem si chtěl rychle ověřit funkčnost. Dávám to sem, kdyby někdo chtěl jen rychle nějaký program, který dané věci počítá. Ještě jednou říkám - psání programů není mou silnou stránkou, já jsem spíše na matematiku, kód tedy není PĚKNÝ.

pozn.: číslo před dvojtečkou udává, kolikáté se jedná o prvočíslo tvaru n^2+1 (počítáno od 0). Číslo za dvojtečkou udává onu hodnotu. Aby se hodnoty nevypisovaly příliš rychle, vypisuji na obrazovku každé tisící spočítané číslo.

Autor skryl část textu. Zobrazit/skrýt!

Zde je podrobný zápis začátku běhu algoritmu. Myslím si, že by měl být jasný po přečtení. Na požádání vysvětlím nedostatky. Pro důkaz správnosti je potřebné ukázat, že po dělení všech dělitelů zůstane číslo, které MUSÍ být prvočíslem. Což si myslím, že jsem dokázal. Bylo by to docela pěkné, protože i tím docela hloupým programem, který jsem poslal výše, jsem spočítal prvních milión prvočísel tvaru $n^2+1$ během pár minut. Bylo by pěkné, kdyby to opravdu prvočísla byla (nejvyšší bylo vyšší jak 600 bilionů).

Autor skryl část textu. Zobrazit/skrýt!

check_drummer · 08. 05. 2016 13:13

↑ liamlim:
Ahoj, jak rychlý je tvůj program? Tj. kolik kroků zhruba provede než vypíše provočísla do daného n?
Co znamená "Vydělíme f(3) všemi prvočísly"? Dělíme jen 5kou a nebo opravdu všemi? pak ale dostaneme vždy 1...
Jaký je důkaz správnosti?

liamlim

↑ check_drummer:

jen takovymi n ze v seznamu mame dvojici (3,a).

edit:

Tak konečně se vyjádřím obsáhleji. Ono to hlavní, co mám, je algoritmus, který pro dané číslo ověří, jestli je prvočíslem, případně napíše proč by prvočíslem nebylo. Když jsem ten program zkoušel, tak velmi rychle tuto otázku odpovídal. Abych to ozřejmil... Máme číslo $n$ . Řekněme, že například $n = 91 = 9^2 + 10$ . Zkoumám tedy funkci $f(x) = x^2 + 10$ analogicky k uvedenému algoritmu, akorát zahazuji nepotřebná čísla (takže se paměťová náročnost zásadně sníží). Jinak se všechny funkce $f(x) = x^ + a$ chovají podobně hezky, jako $f(x) = x^2+1$ ... Pro některé $a$ však hezčeji než pro jiná.

Mým cílem je najít pro zadané $x$ takové $a$ , že je možno $x$ vyjádřit tvarem $n^2 + a$ a to tak, aby $a$ bylo co "nejhezčí". Velmi pěkné je například $a = 163$ , což souvisí se známou řadou $n^2+n+41$ .

Ten algoritmus však má i nějaké problémy. Konkrétně pokud narazím na kandidáta na prvočíslo, pak má program občas problémy, pokud má tento kandidát pouze dva prvočíselné dělitele, které jsou si velmi blízké (jednotky...). Pro správnou funkčnost je však bezpodmínečně nutné buď to aby všichni kandidáti byly prvočísla, nebo opravdu velmi rychle oba prvočíselné dělitele nalézt (to by se opakovalo velmi často, takže by to muselo být skutečně rychlé).

Ještě jeden problém u toho přístupu mám. Řekněme, že máme funkci $f(x) = x^2 + 8$ . Pak f(0) = 8, f(1) = 9, f(2) = 12... Pro první dva členy je potřeba faktorizaci udělat jiným algoritmem, pak už algoritmus funguje. Pro jiné $a$ , řekněme třeba 14521 to neumím zatím vidět... Tím myslím kolik prvních členů je potřeba faktorizovat jiným algoritmem, než ten popisovaný "naběhne". Já to dělal tak, že jsem faktorizoval prvních odmocnina (a) členů. Pro funkci x^2+8 tedy první 3 členy (horní celá mez odmocniny 8). Neumím říct, jestli je to moc, nebo málo. Ale docela to funguje.

edit.: Algoritmus vůbec nebere do ruky pro funkci n^2 + a taková prvočísla, která nedělí žádné číslo tvaru n^2+a. Navíc v každém kroku se posune o docela velký kus dopředu, díky druhé mocnině...

Eratosthenes · 11. 05. 2016 00:31

ahoj ↑ liamlim:,

no, nevím. Zkontroloval jsem to velmi jednoduchým algoritmem postupného dělení a vychází mi to dost jinak. Neříkám, že to mám dobře, samozřejmě se můžu mýlit, ale na druhou stranu si myslím, že čím jednodušší algoritmus, tím menší prostor pro chyby. Podle mě tam soustu prvočísel nemáš, protože to milionté je o dost nižší. Moje výsledky jsou:

pořadí
prvočísla prvočíslo

100 000 3 818 037 840 401
200 000 17 044 148 943 937
300 000 40 710 958 904 197
400 000 75 401 261 892 101
500 000 121 645 590 841 637
600 000 179 912 485 617 317
700 000 250 164 709 027 217
800 000 332 701 831 693 457
900 000 427 826 780 432 677
1 000 000 535 442 291 419 877

Matematické Fórum

#1 06. 05. 2016 22:53

Důkaz správnosti - algoritmus prvočísla

#2 08. 05. 2016 13:13

Re: Důkaz správnosti - algoritmus prvočísla

#3 08. 05. 2016 13:16 — Editoval liamlim (08. 05. 2016 14:12)

Re: Důkaz správnosti - algoritmus prvočísla

#4 08. 05. 2016 13:19 Příspěvek uživatele liamlim byl skryt uživatelem liamlim. Důvod: dva příspěvky ode mě za sebou

#5 11. 05. 2016 00:31

Re: Důkaz správnosti - algoritmus prvočísla

Zápatí