Zastanawiałem się, czy opublikować pierwotną znalezioną wersję faktoryzacji liczbami parzystymi, kiedy naprowadziła już ona na heurystykę opisaną w poprzednim poście.Okazuje się, że ten przegląd zupełny ma nieco większą złożoność, i nie nadaje się do komputerów, tylko dla ludzi.
Ale niech tam. Przynajmniej pokażę, jak rozumowałem.
Przy faktoryzacji przebiegam jakieś 2^(lg n) reszt (trochę mniej - do pierwiastka) kwadratowego z n) dla kolejnych podstaw p. Klasycznie połowę, wystarczy brać p nieparzyste. I to jest standardowa metoda trial division, pozostaje kwestia czy stosowane jest dzielenie, czy konwersje o 2, ale to szczegół techniczny.
Przechodząc na podstawę parzystą, nie trafiam w dzielnik, ale tuż obok. Wtedy suma cyfr przystaje do zera modulo (p-1), albo naprzemienna suma (alternate sum) przystaje do zera modulo (p+1). Analogicznie jak cechy podzielności przez 9, 11 odpowiednio. Dla kolejnych wartości parzystych ta sama wartość np. 43 jest sprawdzana dwukrotnie, z obu stron 42 oraz 44. Mogę zatem zmniejszyć stałą M złożoności algorytmu trial division O(M log^2 n), biorąc co czwartą wartość i te cechy. Pokryją wartości nieparzyste oraz rozpatruję połowę M. Miłe.
Może jeszcze uda się zmniejszyć M? Przyjrzyjmy się wykładnikom przy potęgach liczby d dla kolejnych wielokrotności d w postaci kanonicznej (iloczyn kolejnych liczb pierwszych):
1 2 1 3 1 2 1 4 1 ...
Proszę porównać dla d=2 (kolejne liczby parzyste):
2 2^2 2*3 2^3 2*5 2^2*3 2*7 2^4 2*9 ...
Specyficzny ciąg. Jeśli zainicjować A=1, potem niech w A wartością maksymalną jest k, to tworzy się grzebień postaci
A (k+1) A
Ale są luki, jednak trzeba brać pod uwagę wszystkie wielokrotności 4.
Lecz możemy przeksztalcać liczbę nieco inaczej. Bardziej wielowątkowo.
Całka Riemanna pokrywa pole pod funkcją prostokątami pionowymi. Całka Lebesque'a 'prostokątami' poziomymi. W podobny sposób zmieniam kolejność obliczeń, przez co pojawią się wątki.
Pierwszy watek to podstawy będące wszystkimi nieparzystymi wielokrotnościami 4, drugi tworzą nieparzyste wielokrotności 8. Pokrywają przedział z lukami, kolejna luka zaczyna się od 2*8=16. Jest to kolejny wątek. I tak dalej.
Wątki inicjowane są kolejnymi potęgami 2: k= 4, 8, 16, 32,..., zaś w danym wątku kN liczone są postacie liczby n dla kolejnych podstaw 2pk. Postacie liczby, nie reszty z dzielenia.
Są to konwersje o podwojony najmniejszy wspólny dzielnik danego wątku.
Czyli podstawy przekształcanych systemów dla danej liczby tworzą ciągi:
4, 12, 20, 28, 36, 44, ...
8, 24, 40, ...
16, 48, ...
32, ...
...
Wygląd modyfikowanej liczby szybko się zmniejsza, obliczanie sum, naprzemiennych sum jest prosty, ale konwersje nie są już tak miłe. Pogarszają złożoność o kolejny log n.
Dla człowieka widać na pierwszy rzut oka na cyfry, czy warto liczyć sumy, dla komputera niezbyt bez dodatkowego kodu.
Ale przecież człowiek nie będzie rozkładać dużej liczby bez wsparcia komputera! Niech ten przebieg faktoryzacji pozostanie ciekawostką.
Brak komentarzy:
Prześlij komentarz