W ostatnim poście napisałem 'wzór na dzielniki'. Jest to raczej układ kongruencji, które są widoczne jako układ równań.
Postać wejściowa to palindrom [i,j,k,j,i]_p nad systemem pozycyjnym o podstawie p, który jest przedstawiony jako iloczyn dwu palindromów. W tym iloczynie wartości skrajne są znane, nieznane są tylko pozycje odpowiadające cyfrom dziesiątek liczb.
Zatem dany jest iloczyn [a, x, a]_p * [b, y, b]_p , z niewiadomymi x, y.
Konwertujemy palindrom na systemy o podstawach (p-1) oraz (p+1). Uzyskujemy w ten sposób nowe wielomiany, których współczynniki są blisko ze sobą związane. Niestety, przenoszenie między cyframi może się jeszcze zachować mimo próby jego uwzględnienia we współczynnikach stałych układu. Porównując teraz współczynniki (jako kombinacje liniowe i jako iloczyny) uzyskujemy wspomniany układ kongruencji.
I to wszystko.
Na przykładzie N = 8934053 = [15, x, 15]_{16} * [11, y, 11]_{16}
Jeden z palindromów to N = [165, 0, -7342, 0, 165]_{16}, inny N = [165, 3152, -57971, 3152, 165]_{16}.
Mamy dodatkową stałą 4*165 = 660, oraz układ równań:
N = [165, e, e+f, 2f, f] _{15} = [165, c, d-c, -2d, d]_{17}
e-c = 4*165 = 660 (co pochodzi z kombinacji liniowej (x,y) z (15,11))
c = 11x+15y-660
e = 11x+15y+660
d = xy -2*11x-2*15y+4*165 = g*h
f = xy+2*11x+2*15y+4*165 = (4*15-g)*(4*11-f)
g = 2*15-x
h = 2*11-y
W praktyce uzyskane współczynniki nie są zbyt miłe:
N = [165, 3812, -47525, -102674, -51337]_{15}
N = [165, 2492, -66437, 127890, -63945]_{17}
Dlatego jednak preferuję inne sposoby rozkładu... Nie jestem do końca pewien, czy potrafię rozwiązywać takie układy, czy palindrom początkowy nie ma tutaj znaczenia.
Brak komentarzy:
Prześlij komentarz