W poprzednim swoim wpisie przedstawiłem definicję nowej funkcji, którą nazwałem Awangarda, po angielsku Van. Jest to funkcja dwuargumentowa, i stanowi iloraz primorialu liczby większej, podzielonego przez primorial liczby mniejszej. Przypomina to nieco współczynnik dwumianowy Newtona, z wyjątkiem tego, że u Newtona pod kreską jest dodatkowo jeszcze silnia różnicy tych liczb. Zaproponowałem zapis:
\(\displaystyle{ \#pq = p\#/q\#}\) gdzie obie liczby są pierwsze, i \(\displaystyle{ p > q}\) oraz \(\displaystyle{ p-q= Δ}\)
Ale po namyśle zmieniam konwencję:
poręczniejszy, bardziej obrazowy będzie bowiem równoważny powyższemu zapis
\(\displaystyle{ \#p₀Δ₀ = (p₀+Δ₀)\#/p₀\#}\)
— przy czym należy go rozumieć symbolicznie, ponieważ \(\displaystyle{ Δ}\) nie jest liczbą, lecz oznacza powiększenie numeru liczby pierwszej \(\displaystyle{ p₀}\) — o zadaną ilość kroków \(\displaystyle{ Δ₀}\), w stosunku do numeru porządkowego liczby \(\displaystyle{ p₀}\).Dodatkowo, ponieważ \(\displaystyle{ p₀}\) wciąż będzie się zmieniać, to wygodnie będzie je po prostu indeksować:
\(\displaystyle{ p₁; p₂; p₃... pₙ}\) zmieniać się będzie również \(\displaystyle{ Δ₀}\), ponieważ istotna jest nie tyle odległość pomiędzy kolejnymi liczbami pierwszymi, co otrzymana w wyniku ich wymnażania liczba, co do której z jakichś powodów mamy warunek, aby nie była zbyt duża.
Z jakich powodów (zapyta ktoś)? Nie wiem! Wyjdzie to w praniu, to znaczy przy algorytmów układaniu...
Jak się okazuje funkcja taka jest przydatna w teorii liczb. Zanim to wyjaśnię — mała dygresja:
Faktoryzację liczb stosunkowo małych, można prowadzić tak zwaną metodą naiwną, albo inaczej prymitywną, przypominającą nieco jednak genialne sito Eratostenesa, dzieląc po prostu (lub też raczej usiłując podzielić) liczbę badaną, przez kolejne liczby pierwsze. Kiedy nam się to uda, wynik dzielenia próbujemy dzielić ponownie przez ostatnio użytą liczbę, bo być może liczba badana dzieli się przez nią kilkakrotnie.
Każda liczba pierwsza, przez którą dzieli się liczba badana, oczywiście w adekwatnej potędze — jest składnikiem iloczynu liczb pierwszych, iloczynu tworzącego konkretną liczbę badaną.
Otrzymany wynik dzielenia traktujemy teraz jak kolejną liczbę badaną, i dzielimy go przez następne w kolejności liczby pierwsze, powtarzając procedurę aż do chwili, gdy otrzymany wynik będzie mniejszy od liczb pierwszych kolejno następujących w stosowanej przez nas procedurze, progresywnie wspinającej się w górę szeregu liczb pierwszych. Oczywiście przez nie próbować dzielić nie ma już sensu najmniejszego, bowiem obracamy się w sferze liczb całkowitych.
A teraz nawiązując do tej dygresji, przypomnę, że zaproponowana w jednym z poprzednich wpisów metoda primorial sieve, stanowiąca bardzo wydajny sposób wykrywania dużych liczb złożonych, poniekąd ma coś wspólnego z opisaną powyżej metodą naiwną. Ale jest istotna różnica. Rzecz w tym, że podobnie jak człowiek, komputer mnożenie wykonuje zauważalnie szybciej, niż dzielenie: różnica sięga kilkudziesięciu procent — liczonych czy to w czasie wykonania, czy w ilości taktów procesora. W metodzie primorial sieve w pierwszym kroku wymnażamy przez siebie kilka liczb, a później liczbę badaną dzielimy (lub próbujemy podzielić) już przez ich iloczyn: i warto się zastanowić nad tym, o ile to jest szybsze, niż gdybyśmy dzielili przez każdą z tych liczb osobno.
Ale nie jest to różnica najistotniejsza (chociaż swoją wagę posiada), bowiem dużo większe znaczenie ma przemyślne badanie otrzymywanych reszt z dzielenia, i określanie, które z nich są liczbami pierwszymi, a które nie: otóż ten drugi przypadek wskazuje na to, że liczba badana jest liczbą złożoną, dzieli się bowiem przez przynajmniej jeden ze składników owej reszty, będącej również liczbą złożoną.
Metoda primorial sieve dedykowana jest do badania liczb olbrzymich, zbudowanych z dziesiątek tysięcy cyfr, a nawet większych.
Warto wspomnieć, że wśród nich największe zainteresowanie budzą nie takie, które są podzielne przez stosunkowo małe liczby pierwsze, ale liczby stanowiące iloczyn dokładnie dwóch dużych liczb pierwszych zbliżonej wielkości. Liczby te oczywiście nie będą wykrywane w pierwszym, wstępnym kroku procedury primorial sieve, ani też nawet w krokach kolejnych, niezbyt jeszcze wysokich. Stąd pojawiła się potrzeba zastosowania funkcji awangarda.
Otóż gdy liczba badana oparła się próbom jej faktoryzacji w pierwszym już etapie, to w następnym, i w kolejnych, będziemy używać funkcji Van, tak dobierając jej \(\displaystyle{ Δ}\), aby spełnić pewne warunki, które zostaną opisane później.
W wyniku zastosowania tej procedury otrzymamy całkiem już sporą (a będzie to przyczyną zauważalnych kłopotów) ilość reszt z dzielenia, i znowu, jak w poprzednim etapie, te z nich, które będą liczbami złożonymi — sygnalizują, że liczba badana również jest liczbą złożoną, i dzieli się przynajmniej przez jeden ze składników, tworzących daną resztę.
Tym razem naszą podłogę do wyliczeń (wiem, że w matematyce termin podłoga, ma określone znaczenie ściśle techniczne, ale tutaj używam go w innym kontekście: na określenie progu, od którego zaczynamy dalszą procedurę, jest to bowiem liczba \(\displaystyle{ p₁= \#p₀Δ₀}\)).
O ile nie pogubiłem się z tymi indeksami, co możliwe, bo jestem już trochę zmęczony, to potrzebna nam będzie baza danych, zawierająca kompletne zestawienie ponumerowanych kolejnych liczb pierwszych, zawartych w przedziale \(\displaystyle{ (p₀; p₁)}\).
Ale chyba raczej zawartych w przedziale \(\displaystyle{ (p₁; p₂)}\) — no, niech ktoś podpowie, piętra mi się plączą...
Późno już, i trudno mi się skupić nad detalami, ale chcę dokończyć rozpoczętą myśl, od detali bardziej istotną. Jednak trudno mi rozstrzygnąć teraz, co z resztami z dzielenia, które będą liczbami pierwszymi, ale są mniejsze od wspomnianego przedziału? A zauważmy, że nie jest to problem tylko w drugim kroku (czyli w piętrze... pierwszym) procedury, ale ma naturę ogólną, bowiem w kolejnych pojawi się również, jednak rozwiązanie będzie takie same, jak na drugim procedury piętrze. Jest więc to problem bardzo istotny, a ponieważ w tej chwili rozwiązania nie znajduję, to proszę o pomoc, licząc na podpowiedzi...
Na koniec krótkie résumé: wciąż podnosząc poprzeczkę wysokości liczb pierwszych, za pomocą których testujemy liczbę badaną, przechodzimy w indeksach funkcji primorial sieve, od \(\displaystyle{ p₀}\), do \(\displaystyle{ p₁}\), potem do \(\displaystyle{ p₂}\), i tak dalej, aż kolejne \(\displaystyle{ pₙ}\) będzie większe od liczby badanej. W ten sposób sfaktoryzujemy wszystkie liczby złożone, natomiast w przypadku liczby pierwszej — otrzymamy stuprocentowe potwierdzenie jej prymarności...
i t. b. b. n. t...
Dodano po 16 godzinach 35 minutach 45 sekundach:
Powinno być, uwzględniając wymogi LaTeXa:c-rasz pisze: 16 cze 2024, o 03:39 Zaproponowałem zapis:
\(\displaystyle{ \#pq = p\#/q\#}\) gdzie obie liczby są pierwsze, i \(\displaystyle{ p > q}\) oraz \(\displaystyle{ p-q= Δ}\)
\(\displaystyle{ \#pq = \frac{p\#}{q\#}}\)
Ale po namyśle zmieniam konwencję:
poręczniejszy, bardziej obrazowy będzie bowiem równoważny powyższemu zapis
\(\displaystyle{ \#p₀Δ₀ = (p₀+Δ₀)\#/p₀\#}\)— przy czym należy go rozumieć symbolicznie, ponieważ \(\displaystyle{ Δ}\) nie jest liczbą, lecz oznacza powiększenie numeru liczby pierwszej \(\displaystyle{ p₀}\) — o zadaną ilość kroków \(\displaystyle{ Δ₀}\), w stosunku do numeru porządkowego liczby \(\displaystyle{ p₀}\).
uwzględniając wymogi LaTeXa:
\(\displaystyle{ \#p₀Δ₀ = \frac{(p₀+Δ₀)\#}{p₀\#} }\)
— przypomnę ponownie, iż "działanie" \(\displaystyle{ (p₀+Δ₀)}\) dodawaniem nie jest,
lecz operacją na indeksach tablicy numerowanych liczb pierwszych, i oznacza wyrażoną numerem indeksu odległość pomiędzy \(\displaystyle{ p₀}\) a \(\displaystyle{ p_{1} }\) — tedy \(\displaystyle{ (p₀+Δ₀)}\) należy czytać jako \(\displaystyle{ p_{1} }\) — to jest zapis równoważny...
