17 sierpnia 2020

Przegląd zupełny iloczynami liczb jako faktoryzacja

 Jeśli każda z cyfr liczby jest podzielna przez d, cała liczba też jest podzielna przez d.
Stwierdziłem ten fakt w poprzednim poście. I chciałem zastosować do liczb w systemie Fibonacciego. Same przeksztalcenie są trudne dla człowieka, nie z racji obliczeń, ale tego, że zmiany występują równocześie w trzech różnych miejscach, kiedy używam schematu nad liczbami Fibonacciego: 
[00300] = [10001]
Zapominam ciągle o tych zmianach na wszystkich trzech pozycjach [x0x0x].
Zatem zaczynam przekształcenia, i myśląc nad zapisem powoli dochodzę do wniosku, że wystarczy iloczyn liczby Fibonacciego i jakiejś duzej wartości, zmniejszanej ze wzrostem długości liczby. A potem okazało się, że i liczby Fibonacciego nie są konieczne.
Powstał nowy przegląd zupełny: liczbę n aproksymujemy iloczynami a*b+r, w którym a rośnie od 3 po kolejnych liczbach nieparzystych, zaś r jest jak najmniejszą resztą.Zapis
n = 3*(n/3) + (n%3) = a*b+r
to początek. O ile należy teraz zmniejszyć b, by uzyskać jak najlepsze oszacowanie dla zwiększonego a? Z pomocą przychodzi równanie (znalezione gdy 'rozprasowywałem' wartości cyfr Fibonacciego):
2(b-k) = ak ,
skąd
k = 2b/(a+2) ,
o którą zmniejszam b. Reszta powstająca przy znajdowaniu k wpływa na odległość iloczynu od n. Właściwie, możemy od razu odjąć tę wartość b-k otrzymując
b = ab/(a+2) .
Doświadczenie mówi mi, że znów możemy użyć konwersji, by uniknąć zarówno dzielenia, jak i mnożenia, gdyż przekształcenia wydają się parować. Ale tak nie jest, wzmacniają swoje działanie na liczbę. Mamy po prostu nieco zmodyfikowane współczynniki, zmienione podwojoną cyfrą poprzedzającą.

I znów mamy przegląd zupełny trójek (a,b,r), gdzie n = a*b+r.
(a,b,r) = (m, n/m, n%m), gdzie n = m*(n/m) + (n%m) . 
Dzielniki uzyskamy gdy r=0. Kończymy gdy a przekroczy b. Wartość a rośnie liniowo, wartość b jest tłumiona jak przy odwrotnej proporcjonalności.

 Praktycznie: nieco większa liczba;
a = [179, 253, 134, 259, 181, 270, 41, 172, 277, 83] _ {311}
mnożone przez 309 z resztą +26, czyli n = 309*a+26.
Odejmujemy podwojoną cyfrę poprzednią (równoważne mnożeniu przez 311/313):
a'=[179, -105, -372, -9, -337, -92, -499, 90, -67, -471]
oraz modyfikujemy resztę podwojoną cyfrą najmniej znaczącą r = 26-2*83 = -140.
Możemy poprawić (przenosząc 311 jako jedynkę do cyfry bardziej znaczącej), w szczególności cyfrą najmniej znaczącą staje się -472[+311], zaś reszta uzyskuje wartość -140+311 = 171. Konwertujemy a' na system 313 uzyskując
n = 311 * [168, 201, 77, 172, 61, 137, 256, 193, 123, 56]_{313} + 171
I tak dalej aż reszta będzie 0 (dzielniki), lub liczby się zrównają  a <= n/a (pierwsza).

Widać zmniejszenie najbardziej znaczącej cyfry a mimo zachowania stałej wartości n.