26 marca 2018

Liczby binarne jako palindromy

Liczby binarne można zanurzyć w strukturę palindromu - listy wyglądającej identycznie wspak.
Do zanurzenia korzystamy z własności, którą ostatnio też często stosuję - na miejscu cyfr mogą stać dowolne wartości, jak reprezentacja Zeckendorfa liczb Fibonacciego.
Najlepiej to widać, kiedy zastosujemy cyfry systemu mającego nieskończenie wiele różnych cyfr, jaki opisywałem kilka miesięcy temu. Stosując system dziesiętny lub binarny nie widać tego od razu (cyfry zapisywane jako liczby nie wyglądają na palindromy).

Potęgę 2 zapisujemy jedną cyfrą, jest to palindrom długosci 1.
Dzielnik 3 liczby pozwala uzyskać palindrom o jeden dłuższy.
Pozostałe dzielniki pozwalają uzyskać palindrom o dwa dłuższy.

Twierdzenie. Dowolną liczbę binarną możemy przedstawić jako palindrom.
Dowód - konstrukcja.
Dla potęgi 2 nic więcej nie można zrobić. Liczba trzy jest już palindromem
3 = 11b = (1 1)
Dowolną liczbę nieparzystą N przedstawiamy np. jako trójkę:
(1  (N-5)/2  1) ,
gdyż 1*4+ (N-5)/2*2 + 1 = N.
Liczbę parzystą 2N zapisujemy jako palindrom liczby N podwajając jej współczynniki.

Przykłady takich palindromów:
37 = (1 16 1) = (1 0 5 0 1) = (1 2 0 2 1);
20 = (4 0 4);
51 = (3 0 0 0 3) = (17  17)
Widać, że reprezentacja nie jest jednoznaczna.

Struktura ta ma pewne ciekawe własności. Iloczyn dwu palindromów też jest palindromem:
(a b a) * (c d c) =                                             (1)
(ac (ad+bc) (bd+2ac) (ad+bc) ac) 
Wartości a, c są zawsze nieparzyste dla liczby N nieparzystej. 
Schematy przekształceń palindromów wykorzystują zasady systemu binarnego, np.:
[+2 -3 -1 -3 +2],
po przetłumaczeniu na liczbę binarną polega na dodaniu 2*17=34 i odjęciu (3*5+2)*2 = 34.

Czy można to zastosować do rozkładu liczb? Niezbyt. Przedstawiając liczbę N jako przykładowy palindrom z twierdzenia (1 (N-5)/2 1) szukałem odpowiedniego iloczynu palindromów, z którego jestem w stanie rekursywnie wydobyć dzielniki. Doszedłem do wzorów dla odpowiednio dużych N:
N = 4k+1, wyrażenie
(-2+(N-17)/4 + x^2) / (2x+5)
ma rozwiązanie całkowite dla dzielników liczby N.
N = 4k+3, odpowiednie wyrażenie to
(-2+(N-27)/4 + x^2 - x) / (2x+5).
Jest to inna postać rozkładu metodą 'trial division'. Jedynym plusem są mniejsze dzielne, podzielność można rozdzielić na sumę stałej (rzędu N/4) i kwadratu zmiennej. Rekursja dla rozkładu ac zawiedzie. Dopasowanie właściwej postaci też jest żmudne (iloczyn na pozycji pierwszej, suma jego czynników na drugiej).