Mija miesiąc od ostatniego posta, czas na kolejny algorytm. Ale nie ma żadnego nowego mimo wytężonej pracy.
Przez ten czas przyglądałem się zastosowaniem wzorów skróconego mnożenia do przekształceń liczb. Ponownie odkryłem metodę Fermata a^2-b^2 w trzech odsłonach:
- klasyczną (np. u Knutha Sztuka programowania 4.5.4.C), kiedy odjemna jest zawsze kwadratem, zaś zwiększam b czasem zmniejszając a;
- odwróconą, kiedy odjemnik jest zawsze kwadratem, wtedy zmniejszamy b od czasu do czasu zwiększając a;
- mieszaną, kiedy naprzemiennie przenoszę jakąś wartość między odjemną a odjemnikiem pilnując, by zawsze co najmniej jedno z nich było kwadratem.
Algorytmy te zapisane za pomocą systemów niedziesiątkowych w obszarze z dużymi a oraz b sprowadzają się do prostych konwersji typu
1'2'a_p = 1'0'(a-1)_{p+1}
co oznacza, że dla bardzo dużych liczb działamy na małych wartościach. Nie zmienia to jednak złożoności.
Sprawdziłem także zachowanie się sumy sześcianów. Co prawda, nie każda liczba wyrazi się jako suma dwu sześcianów, ale przekształcenia wzięte z różnicy kwadratów działają i dla sześcianów.
Kiedy zbliżamy się do dzielników, jakiekolwiek przekształcenia wskazujące: 'jesteśmy coraz bliżej' zaczynają szwankować. Dlatego lepszą grupą są algorytmy szukajace dzielników mimochodem. Skaczące między różnymi podstawami.
W szczególności zastosowanie cechy podzielności przez (znany) dzielnik d w systemie o podstawie d+1 (cecha: różnica naprzemienna cyfr w zapisie liczby n jest 0 lub jest podzielna przez n) liczby trójcyfrowej n = a'b'c_p prowadzi do równania kwadratowego
ar^2 - br + c = 0
którego rozwiązania r czasem (nie zawsze) mogą przybliżać okolice dzielnika. W kolejnej iteracji przedstawiamy n w systemie o podstawie p+r albo p-r.
Kryterium: suma naprzemienna cyfr jest dodatnia, dzielnik może być mniejszy niż aktualna podstawa. Suma naprzemienna cyfr jest ujemna, dzielnik jest przy podstawie większej. Suma naprzemienna równa 0, dzielnik jest dokładnie o 1 mniejszy niż aktualna podstawa liczby.
Lecz zmian znaku sumy naprzemiennej cyfr liczby n zapisanej w różnych systemach pozycyjnych jako trójcyfrowa jest wiele. Wskazówką powodzenia może być fakt, że bardzo blisko dzielnika te zmiany są rzadkie. Tuż przy samym dzielniku równanie sugeruje daleki skok. Najdalsze propozycje są najbliżej dzielnika. Wtedy lepiej zastosować metodę siłową.
