Szukanie dzielników liczby N zapisanej w systemie o podstawie większej niż pierwiastek kwadratowy z liczby wydaje się mijać z celem. Tyle przypadków... I co z tego, że istnieje system, w którym liczba N = s*q, s>q ma szczególnie prostą postać:
N = q q _ {s-1}
Jednak na ogół dzielnik można znaleźć zanim napotkamy tę postać. Korzystając z sita wspominanego parę wpisów wcześniej, na dzielnik N natrafimy stosując jeden ze sposobów: podstawa systemu oraz wyraz wolny mają wspólny dzielnik; dystans od wartości startowej jest tym dzielnikiem; dystans rozkłada iloczyn paru dużych liczb pierwszych, wyławiając dzielnik.
W systemie o podstawie odrobinę większym niż pierwiastek kwadratowy, postaci
N = a b _ {2p}
wartość a jest bliska temu pierwiastkowi kwadratowemu oraz maleje ze wzrostem podstawy systemu. Maleje aż do jedynki, ale możemy zatrzymać szybciej, po przejrzeniu połowy przypadków. Wykorzystamy fakty:
- wśród k kolejnych liczb naturalnych istnieje dokładnie jedna, która dzieli k;
- liczba pierwsza mniejsza niż k występuje co najmniej raz w przedziale [k, 2k);
- iloczyn dwu dużych liczb pierwszych w odpowiednim systemie niedziesiątkowym ma postać N = (r*q) q _ {2p}, gdzie q jest liczbą pierwszą, oraz drugi z dzielników jest równy s=2rp+1.
Zmodyfikujemy sito opisane przy liczbach trójcyfrowych na potrzeby liczb dwucyfrowych. Tam sito Eratostenesa działało dla podstaw systemów, teraz będzie obsługiwało cyfrę dziesiątek. Wartość cyfry jedności będzie oscylowała wokół cyfry dziesiątek. Cyfra dziesiątek maleje, a podstawę systemu trzymamy parzystą.
1) Wybieramy wartość startową bliską pierwiastka kwadratowego z N, zapisujemy ją jako liczbę dwucyfrową a b _ {2p} o podstawie parzystej.
2) Do wartości a stosujemy sito Eratostenesa, czyli zapamiętujemy kolejne dzielniki d, które wskazują kolejne, coraz mniejsze wielokrotności znajdowanych liczb pierwszych a-d. Połowę początkowej wartości a zapamiętujemy jako wartownika, oraz inicjujemy dystans d od punktu startowego.
3) Pętla. Zamierzamy przenieść jedynkę z a zwiększajac równocześnie cyfrę jedności b. Jeśli uzyskana wartość jest większa niż a, zabieramy parzystą wielokrotność a zwiększając podstawę systemu (konwersja na system o większej podstawie parzystej, by b było stosunkowo blisko a). Zwiększamy dystans o 1, oraz sprawdzamy, czy w wyniku tzw. trial division przez przyczepione sitem małe liczby pierwsze wobec a pojawiła się liczba pierwsza, podobnie jsk opisano w poprzednim poście. Dystans też może okazać się liczbą pierwszą, traktowaną jako znajdowana. Jeśli rozpoznamy liczbę pierwszą, sprawdzamy jej podzielność przez cyfrę jedności b, co może zakończyć się powodzeniem w znalezieniu dzielnika i zakończeniem. Takie wartości możemy kasować jako już niepotrzebne.
4) Kontunuujemy przebieg sita, aż znajdziemy dzielnik. Kiedy a zmaleje do wartości wartownika, nie znaleźliśmy dzielników, liczba jest pierwsza.
Pętla dla liczb pierwszych wykona się tyle razy, ile wynosi połowa wartości punktu startowego. Oprócz trail division jest dzielenie cyfry jedności przez rozpoznawane liczby pierwsze. Dopóki nie rozpoznamy prawidłowo gigantycznych liczb pierwszych w sicie, chyba potrzebujemy pamiętać te postaci. W innym przypadku do sita mogą trafiać liczby złożone. Kiedy dystans będzie tak duży, że jego kwadrat przekroczy a, każda napotkana większa wartość jest pierwsza, dystans przestaje być potrzebny. Mamy tyle dzieleń cyfr jedności, ile jest liczb pierwszych.
Dla liczby złożonej pętla często zatrzyma się, zanim dystans osiągnie wartość mniejszego z dzielników.
Sprawdziłem dodatkowe przyspieszenie, stosując cechy podzielności przez p-1 oraz p+1. Wartości w sicie są zapisywane jako pary (wartość o podstawie p=4k, produkt), w którym produkt przekształca się w postać kanoniczną wartości. Opisana wcześniej heurystyka jest modyfikowana, i raczej nie nadaje się do obliczeń ręcznych. Ale maszynowo może być wydajniejsza, bardziej dopasowana dla obliczeń współbieżnych rozproszonych. Wartość dystansu nieco traci na znaczeniu. Liczby pierwsze ujawniają się nawet przy wstawianiu nowej wartości do sita,
Funkcja sumy cyfr dla wielu liczb trójcyfrowych i dwucyfrowych jest funkcją piłokształtną. Gdy cyfra setek jest już wystarczająco mała i nie zmienia się podczas konwersji, cyfra dziesiątek jest od niej znacznie większa (co najmniej ośmiokrotnie), można łatwo oszacować system, w którym suma ta znów będzie blisko podstawy. Niech n = a*p*p + b*p + c. Iloraz p/(b-a) wyznacza przesunięcie podstawy, przy której znów a+b+c approx p. Stosuję to do sprawdzania pierwszości wartości odkładanych do sita, gdy liczba może być półpierwsza, czyli jest iloczynem dwu liczb pierwszych. Tempo zmiany podstaw z liniowego (x4) przechodzi w wykładnicze. A w ostatniej iteracji się na ogół sypie, ale wtedy mam heurystykę: kwadrat wyrazu wolnego nie przekracza wymaganego przesunięcia wartości podstawy systemu.
Brak komentarzy:
Prześlij komentarz