Detekcja wielokrotności potęg w dużych liczbach

Palindromy mogą służyć jako w miarę prosty detektor, czy dana liczba (odpowiednio duża) jest postaci
N = p*q^k,
operując na mniejszych potęgach a^k.
Pokażę sposób dla k=2.

Liczbę A = 4a+2b+a zapiszemy jako palindrom [a b a]. Reprezentacja ta jest niejednoznaczna, np. nieparzyste A przedstawimy także jako A = [1 (A-5)/2 1]. Niezmienicza jest jednak wartość liczby. Podobnie inne palindromy nad systemem binarnym mają niezmienianą wartość.

Pomnóżmy zachowując strukturę palindromu [...], tzn. nie wykonując przeniesień pomiędzy poszczególnymi pozycjami:
A*A = A^2 = [a^2  2ab  2a^2+b^2  2ab  a^2]
Pomnóżmy to dodatkowo przez Q = [1 c 1]
QA^2 = [a^2   ca^2+2ab   3a^2+b^2+2abc   c(2a^2+b^2)+4ab   3a^2+b^2+2abc   ca^2+2ab   a^2]
Na poszczególnych pozycjach pojawia się stosunkowo prosta kombinacja współczynników.

Wystarczy teraz dopasować wartość liczby N do tych współczynników.
Pragniemy uzyskać jak najprostsza postać, czyli stosunkowo największe a, najmniejsze b i ogromne c. Rozwiązujemy układ równań na a, b, c, przenosząc wartości jak w systemie binarnym, tzn.
schemat [2 -1 0 -12 0 -1 2] oznacza 2*(64+1) - (32+8*12+2)  = 0.
Inny schemat roboczy [0 2 -1 -6 -1 2 0] 


Dla liczby 1087^2 * 8219 takim palindromem jest:
[217^2   217^2*4107+434   1+4107*2*217+3*217^2   4107(1+2*217^2)+2*2*217   1+4107*2*217+3*217^2   217^2*4107+434   217^2]
oraz [217 1 217] = 1087, [1 4107 1] = 8219.

Wartość 1087^2 została zastąpiona przez 217^2, co przy detekcji ma znaczenie.
Dodatkowo, dla liczb nieparzystych a jest zawsze nieparzyste.

Liczby dziesiętne jako palindromy

Palindromy opisane dla systemu binarnego działają także dla odpowiednio dużych liczb dziesiętnych.
Okazuje się, że każdą liczbę większą niż 4 można w pewnym systemie zapisać jako palindrom długości 3.
Każdą liczbę większą niż 16 można w pewnym systemie zapisać jako palindrom długości 5, może być zarówno liczbą pierwszą jak i złożoną. Wynika to z faktu, że jest to mieszanka liczb względnie pierwszych (w binarnym: 17, 10, 4; oraz nwd(17,10,4)=1 )

Zatem to podejście nie nadaje się na faktoryzację.
Przykład palindromu wskazującego dzielniki wg wzoru:
(a, b, a) * (c, d, c) = (ac, ad+bc, 2ac+bd, ad+bc, ac)
8934053 = (63, 5459, 27904, 5459, 63)
I jest to jedyny wskazujący dzielniki w dziesiętnym o wartościach nieujemnych, gdyż chcąc uzyskać a, c dwucyfrowe mamy
(1653, -7600, 784, -7600, 1653).
Są też inne z których niewiele odczytamy, np. (3, 5, 88990, 5, 3), (873, 8, 1951, 8, 883).

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).