Już parę razy zastanawiałem się tutaj, czy istnieje wzór na dzielniki liczby. I teraz znalazłem postać, dla której istnieje układ równań, z którego można wyznaczyć dzielniki.
W tym poście przedstawię ową specyficzną postać zapisu liczby.
Palindromem nad postawą p nazywamy wielomian o współczynnikach całkowitych postaci
a[n] * p^n+ ... + a[1] *p + a[0],
w którym a[n] = a[0], a[n-1] = a[1], ... po zmianie oznaczeń (n = 2k+1, r naturalne, dla n parzystego dwa sąsiednie wyrazy w środku są równe) a[k+r]=a[k-r] ,
np. [7, 12, 18, -1, 18, 12, 7]_{16} to palindrom nad systemem szesnastkowym o długości 7 i wartości liczbowej N = 7*(16^6+1) + 12*(16^5+16) + 18*(16^4+16^2) - 1*16^3. Palindrom tworzymy po prostu przenosząc od krajów wartości z cyfr do cyfr mniej znaczących kończąc w środku. Skaczemy od cyfr mało znaczących do dużo znaczących i na odwrót dopasowując wartości najpierw na pozycjach mniej znaczących.
Własności palindromu nad systemem p:
- z dowolnej liczby całkowitej można uzyskać palindrom nieparzystej długości, palindrom parzystej długości udaje się wyznaczyć tylko wtedy, gdy wartość liczbowa jest podzielna przez p+1.
- skrajne współczynniki palindromu są wielokrotnościami reszty z dzielenia N przez p.
- cecha podzielności: wartość palindromu jest podzielna przez x, gdy wszystkie współczynniki palnidromu są wielokrotnościami x, np. [x, 3x, 0, 2x, 0, 2x, 0, 3x, x]_p; albo wspólny dzielnik wyraz skrajnego a[0] i p jest dzielnikiem N.
- iloczyn palindromów jest palindromem.
- konwersja palindromu długości 3: [a, b, a] na sąsiedni system (p+1) lub (p-1) ma z dokładnością do znaku tylko dwa różne współczynniki [a, 2a+b, 2a+b]_{p-1} oraz [a, b-2a, 2a-b]_{p+1}. Konwersje niszczą zatem strukturę palindromu.
- palindrom nie jest jednoznacznie wyznaczony, niezmiennikiem palindromu długości 3 jest [a+p, b-p*p-1, a+p]_p = [a,b,a]_p . Najwięcej napotykanych palindromów jest nad systemem binarnym. np. skrajne o wyrazach dodatnich liczby nieparzystej to: pierwszy [1, (N-5)/2, 1]_2, w drugim mamy około (zależy od parzystości N) [floor(N/5), x, floor*N/5)]_2 , gdzie x ma jedną z wartości: 0, 1, 2, 3, 4 w zależności od N. Dla 8934053 mamy w ten sposób palindromy o wyrazach dodatnich między [1, 4467024, 1]_2 oraz [1786809, 4, 1786809]_2. Ze wzrostem p palindromy są coraz rzadziej spotykane.
Przechodzę do postaci liczby N.
Tworzę palindrom długości 5 o takiej podstawie, by jego współczynniki były stosunkowo małe, a wyrazy skrajne były wielokrotnościami reszty z dzielenia przez p takimi, by wyraz skrajny a[0] = m*n \equiv (N%p) (mod p). Dobieram je tak, by 0<=m,n<p oraz p^2 | (N-mn). Oznacza to, że m, n są cyframi jedności dzielników liczby N zapisanymi w systemie p.
np. N = 8934053 \equiv 5 (mod 16), oraz można tę wartość przedstawić jako palindromy
N = [85, 85, 11773, 85, 85]_{16}
oraz
N = [165, 0, -7342, 0, 165]_{16}
W tej drugiej postaci mamy odpowiednie wartości 165 = 15*11, zatem jest to iloczyn palindromów
N = [15, x, 15]_{16} * [11, y, 11]_{16}
Mnożąc te palindromy uzyskujemy układ kongruencji, z których można poszukiwać zmiennych z oraz y. Ale jest to także układ wejściowy dla utworzenia układu równań, z których można wyznaczyć brakujące współczynniki dzielników... Zamierzam umieścić wkrótce...
Brak komentarzy:
Prześlij komentarz