Schreiben eines Programms, um Polynom $ f (x) $ von $ f (1) $ und $ f (1)) $ zu finden

Question

Sei $ f (x) = a_0+a_1x+a_2x^2+ dots+a_nx^n $, wobei $ a_i ge0 $ und $ a_i $ Ganzzahl ist.

Bei $ f (1) = p $ und $ f (f (1)) = q $ müssen wir $ a_0 $, $ a_1 $, $ a_2 $, $ a_3 $, $ dots $, $ a_n $ finden , wo solche $ f (x) $ existiert. Oder wir müssen bestätigen, ob solche $ f (x) $ existieren oder ob das Polynom mehrdeutig ist, z. und $ q = 1 $, $ f (x) = 1 $, $ f (x) = x^2 $ Beide können Lösung sein.

Ich muss ein Programm schreiben, um das zu tun. Was sollte mein Verfahren sein?

Answer 1

Die Bedingungen $ f (1) = p $ und $ f (p) = q $ implizieren die folgenden zwei Gleichungen: $$ begin {align} & sum_ {i = 0}^n a_i = p, & sum_ {i = 0}^n a_i p^i = q. end {align} $$ Wenn $ p <0 $ oder $ p $ keine Ganzzahl ist, gibt es keine Lösungen. Wenn $ p = 0 $, impliziert die erste Gleichung, dass das Polynom $ 0 $ und so $ q = 0 $ sein muss. Wenn $ p = 1 $, implizieren die Gleichungen, dass $ p = q $ und die erste Gleichung impliziert, dass die Lösungen die Polynome $ 1, x, ldots, x^n $ sind. Von nun an nehmen wir an, dass $ P Geq 2 $.

Intuitiv wird das Polynom minimiert, das $ sum_i a_i $ unter der obigen zweiten Einschränkung minimiert wird, indem $ q $ in Basis $ p $ Notation (erster $ n $ digit) geschrieben und den Rest als Koeffizient von $ a_n $ eingesetzt wird. Bezeichnen Sie diese Lösung mit $ b_0, ldots, b_n $. Wenn $ sum_i b_i> p $ dann gibt es keine Lösung. Wenn $ sum_i b_i = p $ dann haben wir die eindeutige Lösung gefunden. Nehmen wir von nun an an, dass $ sum_i b_i <p $; Dies impliziert, dass die Basis $ P $ -Erweiterung von $ Q $ länger höchstens $ n+1 $ hat.

Die angegebenen Gleichungen implizieren mehr Einschränkungen. Zunächst einmal $ Q Geq P $. Zweitens, da $ P äquiv 1 pmod {p-1} $ $ $ q äquiv p pmod {p-1} $ haben müssen. Beginnend mit dem Polynom $ g (x) = sum_ {i = 0}^n b_i x^i $ können wir $ g (1) $ erhöhen, indem wir das Update $ (b '_ {i+1}, B anwenden '_i) get (b_ {i+1} - alpha, b_i+p alpha) $ (wenn $ b_ {i+1} geq alpha $); Dies erhöht $ g (1) $ um $ alpha (p-1) $. Wir können diese Aktualisierungen systematisch anwenden und die Masse bis zum Polynom $ q $ verschieben. Da $ sum_i b_i <p leq q $ und $ q äquiv p pmod {p-1} $, irgendwo auf dem Weg finden wir ein (eindeutiges) Polynom, das beide Anforderungen an beide Anforderungen erfüllt.

Wie führen wir diesen Prozess algorithmisch aus? Wir gehen die Indizes von $ b_n $ bis $ b_1 $ in Ordnung durch. An jedem Punkt subtrahieren wir von $ b_i $ den maximalen Betrag $ alpha $, der den Invarianten $ g (1) Leq P $ hält. Nach der Verarbeitung $ B_1 $ sollten wir das gewünschte Polynom erreichen. (Wir betrachten im Grunde die Basis $ p -1 $ Erweiterung von $ p - g (1) $.)

Answer 2

Wenn $ p = 1 $, sind die Einschränkungen $ f (1) = 1 = q $, was je nach Wert von $ q $ leicht gelöst wird. Nehmen wir nun $ p ge 2 $ an. Angenommen, $ f (x) = sum_k a_k x^k $ ist eine Lösung. Dann $ q = a_0 + a_1 p + a_2 p^2 + ldots + a_n p^n $ wobei $ n $ der Grad von $ f $ ist ($ a_n ne 0 $).

Für alle $ k le n $ ist $ a_k le dfrac {q} {p^k} $. Dies gibt eine Grenze für jeden Koeffizienten.

Da $ P gt 1 $, enthält diese Ungleichung auch ein Grad von $ f $: $ 1 le a_n le dfrac {q} {p^n} $ so $ n le dfrac { log (log (log ( q)} { log (p)} $.

Dies zeigt, dass es nur eine begrenzte Anzahl von Kandidatenpolynomen gibt. Sie können dann alle möglichen Lösungen aufzählen. Berechnen Sie zuerst den maximalen Abschluss $ N $ von $ f $. Schleifen Sie dann die möglichen Abschlüsse ($ N $ bis $ 0 $). Schleifen Sie für jeden Gradwert $ M $ über die möglichen Werte von $ a_m $. Schleifen Sie für jeden Wert von $ a_m $ die möglichen Werte von $ a_ {M-1} $ und so weiter. Verwalten Sie die Teilsummen $ s_k = a_m p^m + ldots + a_k p^k $ und $ r_k = a_m + ldots + a_k $; Wenn eine dieser Beträge $ q $ bzw. $ P $ überschreitet, lassen Sie diesen Zweig des Baumes ab. Wenn Sie $ k = 0 $ erhalten, sind die Einschränkungen für $ f $ $ s_1 + a_0 = q $ und $ r_1 + a_0 = p $. Überprüfen Sie also, ob $ s_1 - r_1 = q - p $.

Ich habe keine Ahnung, ob dieser Ansatz praktisch ist - es kann einen erheblich schnelleren Algorithmus geben, der die Trennbarkeit mehr ausnutzt.

Answer 3

Sie benötigen ein Polynom, so dass $ f (1) = p $ und $ f (p) = q $. Dies kann so lange erfolgen, wie $ P neq 1 $, $ P, q> 0 $ und $ frac {qp} {p-1}> 0 $ (oder $ p = q = 1 $). In allen Fällen ist ein Polynom $ ax^n+b $ genug. Hier $ p^{n+1}> q $. Beachten Sie, dass kein $ n $ zu groß ist.