多項式$ f（x）$から$ f（1）$および$ f（f（1））$からの多項式$ f（x）$を見つけるプログラムを作成する

Question

$ f（x）= a_0+a_1x+a_2x^2+ dots+a_nx^n $を、$ a_i ge0 $および$ a_i $は整数です。

$ f（1）= p $ and $ f（f（1））= q $が与えられた場合、$ a_0 $、$ a_1 $、$ a_2 $、$ a_3 $、$ dots $、$ a_n $を見つける必要があります、このような$ f（x）$が存在する場合。または、そのような$ f（x）$が存在するかどうか、または多項式が$ p = 1 $および$ q = 2 $の曖昧な場合、そのような$ f（x）$は存在しませんが、$ p = 1 $は存在しません。 $ q = 1 $、$ f（x）= 1 $、$ f（x）= x^2 $の両方が解決策になります。

私はそれをするためにプログラムを書かなければなりません。私の手順は何ですか？

Answer 1

条件$ f（1）= p $ and $ f（p）= q $は、次の2つの方程式を意味します。 sum_ {i = 0}^n a_i p^i = q。 end {align} $$ $ p <0 $または$ p $が整数ではない場合、解決策はありません。 $ p = 0 $の場合、最初の方程式は、多項式が$ 0 $、$ q = 0 $でなければならないことを意味します。 $ p = 1 $の場合、方程式は$ p = q $であることを意味し、最初の方程式は、ソリューションが多項式$ 1、x、 ldots、x^n $であることを意味します。これからは、$ p geq 2 $を想定しています。

直感的には、上記の2番目の制約の下で$ sum_i a_i $を最小限に抑える多項式は、$ q $をベース$ p $表記（最初の$ n $桁）に書き込み、残りを$ a_n $の係数として記入することで取得されます。このソリューションは、$ b_0、 ldots、b_n $で示します。 $ sum_i b_i> p $の場合、解決策はありません。 $ sum_i b_i = p $の場合、一意のソリューションが見つかりました。これからは、$ sum_i b_i <p $;と仮定します。これは、$ Q $のベース$ p $拡張がせいぜい$ n+1 $で長さであることを意味します。

与えられた方程式は、より多くの制約を意味します。まず、$ q geq p $。第二に、$ p equiv 1 pmod {p-1} $であるため、$ q equiv p pmod {p-1} $が必要です。多項式$ g（x）= sum_ {i = 0}^n b_i x^i $から始めて、アップデート$（b '_ {i+1}、bを適用することで$ g（1）$を増やすことができます。 '_i） gets（b_ {i+1} - alpha、b_i+p alpha）$（$ b_ {i+1} geq alpha $）;これにより、$ g（1）$ by $ alpha（p-1）$が増加します。これらの更新を体系的に適用し、質量を多項式$ Q $に移動することができます。 $ sum_i b_i <p leq q $ and $ q equiv p pmod {p-1} $であるため、途中のどこかで、上記の両方の要件を満たす（一意の）多項式を見つけることができます。

このプロセスをアルゴリズム的にどのように実行しますか？インデックスを$ b_n $から$ b_1 $に順番に進めます。各ポイントで、$ b_i $から最大$ alpha $を差し引きます。 $ b_1 $を処理した後、目的の多項式に到達する必要があります。 （基本的に、$ p -g（1）$のベース$ p -1 $拡張を見ています。）

Answer 2

$ p = 1 $の場合、制約は$ f（1）= 1 = q $です。これは、$ q $の値に応じて簡単に解決できます。今、$ p ge 2 $を想定しましょう。 $ f（x）= sum_k a_k x^k $がソリューションであると仮定します。 $ q = a_0 + a_1 p + a_2 p^2 + ldots + a_n p^n $ $ n $は$ f $（$ a_n ne 0 $）の程度です。

$ k le n $の場合、$ a_k le dfrac {q} {p^k} $。これにより、各係数にバインドされます。

$ p gt 1 $であるため、この不正は$ f $：$ 1 le a_n le dfrac {q} {p^n} $ so $ n le dfrac { log（ q）} { log（p）} $。

これは、有限数の候補多項式しかないことを示しています。その後、すべての可能なソリューションを列挙できます。最初に$ f $の最大度$ n $を計算します。次に、考えられる程度（$ n $〜$ 0 $）にループします。各度合いの値$ m $、$ a_m $の可能な値をループします。 $ a_m $の各値について、$ a_ {m-1} $の可能な値をループします。部分的な合計を維持します$ s_k = a_m p^m + ldots + a_k p^k $および$ r_k = a_m + ldots + a_k $;これらの合計のいずれかがそれぞれ$ q $または$ p $を超える場合、ツリーのこの枝を中止します。 $ k = 0 $に達すると、$ f $の制約は$ s_1 + a_0 = q $および$ r_1 + a_0 = p $です。したがって、$ s_1 -r_1 = q -p $かどうかを確認してください。

このアプローチが実用的であるかどうかはわかりません。分裂性をさらに活用するかなり速いアルゴリズムがあるかもしれません。

Answer 3

$ f（1）= p $ and $ f（p）= q $が必要な多項式が必要です。これは、$ p neq 1 $、$ p、q> 0 $および$ frac {qp} {p-1}> 0 $（または$ p = q = 1 $）の場合もあります。すべての場合において、多項式$ ax^n+b $で十分です。ここで$ p^{n+1}> q $。 $ n $が大きすぎないことに注意してください。