Tak podglądam sobie zachowanie liczb podczas konwersji. Chcę teraz podsumować główne spostrzeżenia.
Jeśli natrafimy na miejsce, gdzie dla podstawy nieparzystej mamy na pozycji jedności zero, mamy dzielnik. Z kolei, gdy dla podstawy parzystej mamy sumę cyfr równą dzielnikowi, albo naprzemienną sumę cyfr równą 0, mamy dzielnik na sąsiedniej pozycji.
Krotność obliczeń jest nie większa niż ta potęga dwójki i = 2^k, gdy i<=sqrt n < 2i.
Zatem przegląd zupełny może biec tylko po liczbach trój- oraz dwycyfrowych. Konwersja o 1. Cyfra setek przyjmuje wtedy jedną z czterech wartości: 0, 1, 2, 3. Małe liczby pierwsze mają silne ślady w tym przedziale.
Znalezienie dzielnika zamiast rozkładu całej liczby, sprowadza się do rozkładu podstaw systemów oraz obliczanie największego wspólnego dzielnika podstawy z cyfrą jedności. Podstawa nieparzysta odsiewa duże liczby, podstawa parzysta (można wyłączyć dwójki) odsiewa mniejsze liczby, m. in. pierwsze. Można zastosować sito modyfikując podstawę systemu, by sprawdzać kandydatów nie więcej niż raz.
Jeśli chcemy zmniejszać krotność sprawdzanych przypadków, dla podstaw parzystych zapis liczby jest w postaci:
[a, b+a, b+r] _p
przy podstawie p jest nieliniowy, ale zachowuje się na tyle gładko, że r jest przedziałami monotoniczne. Dzielnik towarzyszy jednej z dużych zmian wartości r.
I zapraszam na łowy! Dla jakiej podstawy dzielnik jednocyfrowy liczby staje się dwucyfrowy?
Brak komentarzy:
Prześlij komentarz