Написание программы для поиска полинома $ f (x) $ из $ f (1) $ и $ f (f (1) $

Question

Пусть $ f (x) = a_0+a_1x+a_2x^2+ dots+a_nx^n $, где $ a_i ge0 $ и $ a_i $ является целым числом.

Учитывая $ f (1) = p $ и $ 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 $ и $ f (p) = q $ подразумевают следующие два уравнения: $$ begin {align} & sum_ {i = 0}^n a_i = p, & 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 $.

Интуитивно, полином минимизирует $ sum_i a_i $ в соответствии с вторым ограничением, выше, получается путем написания $ q $ в базовых $ p $ natation (первые $ n $ цифры) и устанавливая остальные в качестве коэффициента $ a_n $. Обознайте это решение $ b_0, ldots, b_n $. Если $ sum_i b_i> p $, то нет решения. Если $ sum_i b_i = p $, то мы нашли уникальное решение. Отныне предположим, что $ sum_i b_i <p $; Это подразумевает, что базовое расширение $ p $ на сумму $ Q $ имеет большую часть $ 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 $, мы можем увеличить $ g (1) $, применив обновление $ (b '_ {i+1}, b '_i) get (b_ {i+1} - alpha, b_i+p alpha) $ (когда $ b_ {i+1} geq alpha $); Это увеличивает $ g (1) $ по $ alpha (p-1) $. Мы можем систематически применять эти обновления, перемещая массу вплоть до полинома $ Q $. Поскольку $ sum_i b_i <p leq q $ и $ q aquiv p pmod {p-1} $, где-то по пути мы найдем (уникальный) полином, удовлетворяющий оба требования выше.

Как мы выполняем этот процесс алгоритмически? Мы переживаем индексы от $ b_n $ до $ b_1 $ в порядке. В каждой точке мы вычитаем из $ b_i $ максимальная сумма $ alpha $, которая сохраняет инвариантную $ g (1) leq p $. После обработки $ b_1 $ мы должны достичь желаемого полинома. (Мы в основном смотрим на базовое расширение $ P -1 $ в размере $ P - G (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)} $.

Это показывает, что существует лишь конечное количество кандидатных полиномов. Затем вы можете перечислить все возможные решения. Сначала вычислите максимальную степень $ n $ $ f $. Затем переоценивайте возможные степени ($ 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 $ и $ 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 $ слишком велик.