Scrivere un programma per trovare polinomio $ f (x) $ da $ f (1) $ e $ f (f (1)) $

Question

Sia $ f (x) = + a_0 a_1x + a_2x ^ 2 + \ puntini + a_nx ^ n $, dove $ A_i \ GE0 $ e $ A_i $ è intero.

Dato $ f (1) = p $ e $ f (f (1)) = q $, dobbiamo trovare $ a_0 $, $ A_1 $, $ a_2 $, $ A_3 $, $ \ puntini $, $ a_n $, in cui tale $ f (x) $ esiste. O dobbiamo confermare se tale $ f (x) $ esiste o se il polinomio è ambigua per esempio per $ p = 1 $ e $ q = 2 $, tale $ f (x) $ esiste ma per $ p = 1 $ e $ q = 1 $, $ f (x) = 1 $, $ f (x) = x ^ 2 $ entrambi possono essere una soluzione.

Devo scrivere un programma per farlo. Quale dovrebbe essere la mia procedura?

Answer 1

Le condizioni di $ f (1) = p $ e $ f (p) = q $ implicano i seguenti due equazioni: $$ \ Begin {align} & \ Sum_ {i = 0} ^ n = p A_i, \\ & \ Sum_ {i = 0} ^ n A_i p ^ i = q. \ End {align} $$ Quando $ p <0 $ o $ p $ non è un numero intero, non ci sono soluzioni. Quando $ p = 0 $, la prima equazione implica che il polinomio deve essere $ 0 $ e quindi $ q = 0 $. Quando $ p = 1 $, le equazioni implica che $ p = q $, e la prima equazione implica che le soluzioni sono i polinomi $ 1, x, \ ldots, x ^ n $. D'ora in poi, si assume che $ p \ geq 2 $.

Intuitivamente, il polinomio minimizzando $ \ sum_i a_i $ sotto il secondo vincolo sopra è ottenuto scrivendo $ q $ nella base di $ p $ notazione (primo $ n $ cifre) e conclude il resto come coefficiente di $ a_n $. Indichiamo questa soluzione da $ b_0, \ ldots, b_n $. Se $ \ sum_i b_i> p $ allora non c'è soluzione. Se $ \ sum_i b_i = p $ allora abbiamo trovato la soluzione unica. D'ora in poi, si supponga che $ \ sum_i b_i

I dati equazioni implicano più vincoli. Prima di tutto, $ q \ geq p $. In secondo luogo, dal momento che $ p \ equiv 1 \ pmod {p-1} $, dobbiamo avere $ q \ equiv p \ pmod {p-1} $. A partire con il polinomio $ g (x) = \ sum_ {i = 0} ^ n b_i x ^ i $, possiamo aumentare $ g (1) $ applicando l'aggiornamento $ (b '_ {i + 1}, b '_I) \ ottiene (b_ {i + 1} - \ alpha, b_i + p \ alpha) $ (quando $ b_ {i + 1} \ geq \ alpha $); Questo aumenta $ g (1) $ di $ \ alpha (p-1) $. Possiamo applicare questi aggiornamenti in modo sistematico, lo spostamento della massa fino al polinomio $ q $. Dal momento che $ \ sum_i b_i

Come si fa a eseguire questo processo algoritmicamente? Andiamo nel corso degli indici da $ b_n $ a $ q_1 $ in ordine. In ogni punto, sottraiamo da $ b_i $ l'ammontare massimo $ \ alpha $ che mantiene l'invariante $ g (1) \ leq p $. Dopo l'elaborazione $ q_1 $, dovremmo raggiungere il polinomio desiderato. (Ci sono fondamentalmente guardando alla base $ p-1 $ espansione delle $ p -. G (1) $)

Answer 2

Se $ p = 1 $, quindi i vincoli sono $ f (1) = 1 = q $ che è facilmente risolto in funzione del valore di $ q $. Vediamo ora assumono $ p \ ge 2 $. Supponiamo che $ f (x) = \ sum_k a_k x ^ k $ è una soluzione. Poi $ q = a_0 + a_1 p + a_2 p ^ 2 + \ ldots + a_n p ^ n $ dove $ n $ è il grado di $ f $ ($ a_n \ ne 0 $).

Per ogni $ k \ le n $, $ a_k \ le \ dfrac {q} {p ^ k} $. Questo dà un legato su ogni coefficiente.

Da $ p \ gt 1 $, questa disequazione dà anche un balzo per il grado di $ f $: $ 1 \ le a_n \ le \ dfrac {q} {p ^ n} $ in modo $ n \ le \ dfrac { \ log (q)} {\ log (p)} $.

Questo dimostra che c'è solo un numero finito di polinomi candidati. È quindi possibile enumerare tutte le possibili soluzioni. In primo luogo calcolare il massimo grado $ n $ di $ f $. Poi un ciclo su possibili gradi ($ n $ a $ 0 $). Per ciascun valore di grado $ m $, ciclo sui possibili valori di $ a_m $; per ogni valore di $ a_m $, un ciclo sui possibili valori di $ a_ {m-1} $, e così via. Mantenere le somme parziali $ S_k = a_m p ^ m + \ ldots + a_k p ^ k $ e $ R_k = a_m + \ ldots + a_k $; se una di queste somme supera $ q $ o $ p $ rispettivamente interruzione questo ramo dell'albero. Quando si arriva a $ k = 0 $, i vincoli $ f $ sono $ S_1 + a_0 = q $ e $ R_1 + a_0 = p $, in modo da controllare se $ S_1 - R_1 = q -. P $

Non ho idea se questo approccio è pratico - ci può essere una significativamente più veloce algoritmo di divisibilità sfruttando più

.

Answer 3

Hai bisogno di una tale polinomiale che $ f (1) = p $ e $ f (p) = q $. Questo può essere fatto finché $ p \ neq 1 $, $ p, q> 0 $ e $ \ frac {q-p {} p-1}> 0 $ (o $ p = q = 1 $). In tutti i casi un polinomio $ ax ^ n + b $ è sufficiente. Qui $ p ^ {n + 1}> q $. Si noti che nessun $ n $ è troppo grande.