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.
Brak komentarzy:
Prześlij komentarz