L'écriture d'un programme pour trouver polynôme $ f (x) $ de $ f (1) $ et $ f (f (1)) $

Question

Soit $ f (x) = a_0 + a_1x + a_2x ^ 2 + \ + points a_nx ^ n $, où $ a_i \ ge0 $ et $ a_i $ est un nombre entier.

Compte tenu de $ f (1) = p $ et $ f (f (1)) = q $, nous devons trouver $ a_0 $, $ A_1 $, $ A_2 $, $ A_3 $, $ \ points $, $ a_n $, lorsque cette $ f (x) $ existe. Ou bien nous confirmer si un tel $ f (x) existe $ ou si le polynôme est ambigu par exemple pour $ p = 1 et $ q = 2 $, aucun $ f (x) $ existe mais pour $ p = 1 et $ q = $ 1, $ f (x) = $ 1, $ f (x) = x ^ 2 $ à la fois peut être la solution.

Je dois écrire un programme pour le faire. Quelle devrait être ma procédure?

Answer 1

Les conditions $ f (1) = p $ et $ f (p) = q $ implique les deux équations suivantes: $$ \ Begin {align} & \ {Sum_ i = 0} ^ n = p a i, \\ & \ {Sum_ i = 0} ^ n ^ i p a i = q. \ End {align} $$ Lorsque $ p <0 $ ou $ p $ est pas un entier, il n'y a pas de solutions. Lorsque $ p = 0 $, la première équation implique que le polynôme doit être $ 0 $ et donc $ q = 0 $. Lorsque p = 1 $ $, les équations impliquent que $ p = q $, et la première équation implique que les solutions sont les polynômes de 1 $, X, \ ldots, x ^ n $. A partir de maintenant, nous supposons que $ p \ geq 2 $.

Intuitivement, le polynôme minimisant $ \ sum_i a_i $ en vertu de la deuxième contrainte ci-dessus est obtenu en écrivant $ q $ en base $ p notation $ (premier chiffre $ n $) et mettre le reste en tant que coefficient de $ a_n $. On note cette solution par b_0 $, \ ldots, b_n $. Si $ \ sum_i b_i> p $ alors il n'y a pas de solution. Si $ \ sum_i b_i = p $, alors que nous avons trouvé la solution unique. A partir de maintenant, supposons que $ \ sum_i b_i

Les équations données impliquent plus de contraintes. Tout d'abord, $ q \ geq p $. En second lieu, puisque $ p \ equiv 1 \ pmod {p-1} $, il faut avoir $ q \ p equiv \ pmod {p-1} $. En commençant par le polynôme $ g (x) = \ sum_ {i = 0} ^ n b_i x ^ i $, nous pouvons augmenter $ g (1) $ en appliquant la mise à jour $ (b '_ {i + 1}, b « _i) \ obtient (b_ {i + 1} - \ alpha, b_i + p \ alpha) $ (quand $ b_ {i + 1} \ geq \ alpha $); Cela augmente $ g (1) par $ \ alpha (p-1) $. Nous pouvons appliquer ces mises à jour systématiquement, déplacer la masse jusqu'au polynôme $ q $. Depuis $ \ sum_i b_i

Comment effectuer ce processus algorithmiquement? Nous allons au cours des indices de $ b_n $ à $ B_1 $ pour. A chaque point, nous soustrayons à partir de $ b_i $ le montant maximal $ \ alpha $ qui maintient l'invariant $ g (1) \ leq p $. Après le traitement B_1 $ $, nous devrions atteindre le polynôme souhaité. (Nous cherchons essentiellement à la base $ p-1 extension $ de $ p -. G (1) $)

Answer 2

Si $ p = 1 $, alors les contraintes sont $ f (1) = 1 = q $ qui est facilement résolu en fonction de la valeur de $ q $. Supposons maintenant $ p \ ge 2 $. Supposons que $ f (x) = \ sum_k A_K x ^ k $ est une solution. Ensuite $ q = a_0 + p + a_1 a_2 p ^ 2 + \ ldots + a_n p ^ n $ où $ n $ est le degré de $ f $ (a_n \ ne 0 $).

Pour tout k $ \ le n $, A_K $ \ le \ {dfrac q} {p ^ k} $. Cela donne une borne sur chaque coefficient.

Depuis $ p \ gt 1 $, ce inéquation donne également une limite pour le degré de $ f $: 1 $ \ le a_n \ le \ dfrac {q} {p ^ n} $ si n $ \ le \ dfrac { \ log (q)} {\ log (p)} $.

Cela montre qu'il n'y a qu'un nombre fini de polynômes candidats. Vous pouvez ensuite énumérer toutes les solutions possibles. Tout d'abord calculer le degré maximum $ n $ de $ f $. Puis boucle sur les degrés possibles ($ n $ à 0 $ $). Pour chaque valeur $ $ degré m, boucle sur les valeurs possibles de $ a_m $; pour chaque valeur de $ $ de a_m, boucle sur les valeurs possibles de $ a_ {m-1} $, et ainsi de suite. Maintenir les sommes partielles $ S_k = a_m p ^ m + \ ldots + A_K p ^ k $ et $ r_k = a_m + \ ldots + A_K $; si l'une de ces sommes dépasse respectivement $ q $ ou $ p $, abort cette branche de l'arbre. Lorsque vous arrivez à $ k = 0 $, les contraintes qui pèsent sur $ f $ sont $ S_1 + a_0 = q $ et $ R_1 + a_0 = p $, vérifier si si $ S_1 - R_1 = q -. P $

Je ne sais pas si cette approche est pratique - il peut y avoir un algorithme beaucoup plus rapide exploitation divisibilité plus

.

Answer 3

Vous avez besoin d'un polynôme tel que $ f (1) = p $ et $ f (p) = q $. Cela peut se faire aussi longtemps que $ p \ neq $ 1, $ p, q> 0 $ et $ \ frac {q-p} {p-1}> 0 $ (ou $ p = q = 1 $). Dans tous les cas, un polynôme ax $ ^ n + b $ est suffisant. Ici $ p ^ {n + 1}> q $. Notez qu'aucun $ n $ est trop grand.