Prototyp rozkładu przeniesieniami

Mam liczbę w systemie siódemkowym [2, 6, 3]_7. Domyślam, się, że jest złożona, pokażę kolejny sposób, który ewentualnie moze być użyty do rozkładu liczb. Jest to prototyp dla małej wartości podstawy p=7. 

Jeśli mam iloczyn (ap+b)*(cp+d) o nieznanych a, b, c, d, to mogę przenieść w jednym z czynników 'dziesiątkę;, tu dokładniej siódemkę uzyskując zamiast cp+d = (c+1)p+(d-p) = (c+1)p - e. Co to powoduje w zapisie liczby

(ap+b)*(cp+d) = acp^2 + (bc+ad)p + bd ?

Wykorzystamy przeniesienie, które można zapisać xp = xd+xe, gdxie x jest dowolną wartością: a, b. Teraz 

(ap+b)*((c+1)p-e) = a(c+1)p^2 + (bc+b-ae)p - be . 

Różnice na pozycjach między tymi dwoma zapisami można podsumować +[a, b-ap, -pb]_p, kompletnie nie zależą one od c oraz d. 

W przykładzie 

[2+a, 6-7a+b, 3-7b]_7

zarazem 2>=ac, załóżmy a>=c, zatem a może być równe 1, 2, c równe 1, ewentualnie 0, gdyby się okazało, że podstawa p jest odpowiednio duża. Załóżmy, że a=1 oraz skorzystamy z jeszcze jednego przeniesienia by mieć pewność wartości ujemnej w cyfrze jednostek: 

[3, -1+b-1, 3-7-7b] _7 = [3, -2+b, -4-7b]_7

Sugerowana jest wartość ujemna na cyfrze 'dziesiątek' -2+b, przeniesiemy z cyfry setek zmniejszając tu równocześnie ac=1: 

[1, 5+b, -4-7b]_7 . 

W postaciach ogólnych mieliśmy w cyfrze jedności bd, -be, istnieje wspólny dzielnik będący wielokrotnością b. Jakie wartości przyjmuje cyfra jedności dla kolejnych b, szukamy podzielnych przez 3: -4, -11, -18. Różnica 3-(-18) = 3*7, co sugeruje b=3. Wstawmy siłowo: 

[1, 5+3, -4-7*3]_7 

W tym zamieszamiu przeniesieniami tracimy wartość liczby rozkładanej. Przywracamy jej postać, już po uwzględnieniu wartości a i b na cyfrach innych niż jedności, przy okazji ustawiamy c=1: 

[1, 8, 38]_7

Ponieważ cyfra jedności powinna być złożona, a kombinacja liniowa dzielników powinna dać cyfrę 'dziesiątek', kolejne przeniesienia korygują: 

[1, 8, 38] _7 = [1, 9, 31]_7 = [1, 10, 24]_7 

i rozpoznajemy: 24=4*6, 1*4+1*6=10 spełnia te warunki. Naszymi dzielnikami liczby początkowej są [1, 4]_7 = 11, [1, 6]_7 = 13, i można sprawdzić, że naszą początkową wartością jest [2, 6, 3]_7 = 11*13 = 143...

Z innych znalezionych ostatnio własności: sposób zmniejszania podstawy o 1 przez dodawania cyfry poprzedzajacej działa także dla systemu binarnego! W szczególności przy odpowiednim sumowaniu (jest symetryczne dla długości liczby, choć dopiero niedawno na to wpadłem) w cyfrze jedności odkłada się suma ustawionych bitów zapisu liczby binarnej. 

Faktoryzację przeglądem zupełnym warto zaczynać nie od dzielników najmniejszych 2, 3, ... , ale od podstaw równych największym możliwym potęgom 2, a mniejsze dzielniki uzyskamy przez połowienie podstawy systemu - mniej obliczeń i znacznie mniejsza redundancja możliwych podstaw.

Palindrom i hiperbola

Mam palindrom nad systemem niedziesiątkowym. Czy mogę przejść na inny palindrom mający tę samą resztę? 

Jest to możliwe, rozkładając na czynniki wartość stojącą jako druga najmniej znacząca. Wtedy wystarczy konwersja zmiany systemu na wielokrotność podstawy systemu, oraz naprawa uszkodzonego przekształceniem palindromu. 

W ogólności nie można tego zrobić, gdyż wartość na pozycji najmniej znaczącej jest zależna od dzielników liczby zapisanej palindromem. To znaczy, jeśli chcemy zachować resztę 1, a liczba należy do orbity 3N+2, w systemie trójkowym nie uzyskamy palindromu z resztą 1 na pozycjach skrajnych. 

Jaki jest związek palindromu z hiperbolą? Przekształcenie niezmiennicze palindromu nad systemem wyraża się prostym równaniem nieliniowym, będącym akurat równaniem hiperboli, co zaraz uzasadnię. 

W szczególności, nawiązując do szukania dzielników liczb. Niezmiennikiem wartości palindromu N = [a, b, a]_2 nad systemem binarnym jest [a+2, b-5, a+2]_2, a ogólniej N = [a+2k, b-5k, a+2k]_2 dla dowolnego k całkowitego. 

Dzielniki występują wtedy, gdy każdy współczynnik palindromu jest podzielny przez pewną wartość d: [ad, bd, ad]_2. W szczególności wspólny dzielnik nwd(bd, ad) >= d >1. Załóżmy więcej, nawet wielokrotność b = sa. Wykorzystując niezmiennik, rozwiążemy równanie b-5k = s(a+2k). Uwzględnimy jeszcze, że N jest nieparzyste, zaczniemy od a=1, do b odłożymy największą (nad systemem binarnym) wartość i dostajemy zależność:

(N-5)/2 - 5k = s(1+2k) 

w liczbach całkowitych. Sprowadza się ona do równania hiperboli 

2ks + 5k + s - n = 0 , n jest stałą n = (N-5)/2.

Punkty kratowe tej hiperboli są związane z dzielnikami liczby N. Gdyż po wstawieniu rozwiązania (k,s) mamy wartość dzielnika (1+2k) na pozycji skrajnej palindromu.