Escribir un programa para encontrar polinomial $ f (x) $ desde $ f (1) $ y $ f (f (1)) $

Question

Deje $ f (x) = a_0+a_1x+a_2x^2+ dots+a_nx^n $, donde $ a_i ge0 $ y $ a_i $ es entero.

Dado $ f (1) = p $ y $ f (f (1)) = q $, tenemos que encontrar $ a_0 $, $ a_1 $, $ a_2 $, $ a_3 $, $ dots $, $ a_n $ , donde existe tales $ f (x) $. O tenemos que confirmar si dichos $ f (x) $ existe o si el polinomio es ambiguo, por ejemplo, por $ p = 1 $ y $ q = 2 $, no existe tal $ f (x) $ pero por $ p = 1 $ y $ q = 1 $, $ f (x) = 1 $, $ f (x) = x^2 $ ambos pueden ser solución.

Tengo que escribir un programa para hacer eso. ¿Cuál debería ser mi procedimiento?

Answer 1

Las condiciones $ f (1) = p $ y $ f (p) = q $ implican las siguientes dos ecuaciones: $$ begin {align} & sum_ {i = 0}^n a_i = p, & sum_ {i = 0}^n a_i p^i = q. end {align} $$ Cuando $ p <0 $ o $ p $ no es un entero, no hay soluciones. Cuando $ P = 0 $, la primera ecuación implica que el polinomio debe ser de $ 0 $ y, por lo tanto, $ q = 0 $. Cuando $ P = 1 $, las ecuaciones implican que $ P = Q $, y la primera ecuación implica que las soluciones son los polinomios $ 1, x, ldots, x^n $. De ahora en adelante, suponemos que $ P GEQ 2 $.

Intuitivamente, el polinomio minimizando $ sum_i a_i $ bajo la segunda restricción anterior se obtiene escribiendo $ Q $ en base $ P $ Notación (primero $ N $ dígitos) y poniendo el resto como un coeficiente de $ a_n $. Denota esta solución por $ b_0, ldots, b_n $. Si $ sum_i b_i> p $, entonces no hay solución. Si $ sum_i b_i = p $, entonces hemos encontrado la solución única. De ahora en adelante, suponga que $ sum_i b_i <p $; Esto implica que la expansión base de $ P $ de $ Q $ tiene una longitud como máximo $ N+1 $.

Las ecuaciones dadas implican más restricciones. En primer lugar, $ q geq p $. En segundo lugar, desde $ p equiv 1 pmod {p-1} $, debemos tener $ q equiv p pmod {p-1} $. Comenzando con el polinomio $ g (x) = sum_ {i = 0}^n b_i x^i $, podemos aumentar $ g (1) $ aplicando la actualización $ (b '_ {i+1}, b '_i) gets (b_ {i+1} - alpha, b_i+p alpha) $ (cuando $ b_ {i+1} geq alpha $); Esto aumenta $ G (1) $ por $ alpha (P-1) $. Podemos aplicar estas actualizaciones sistemáticamente, moviendo la masa hasta el polinomio $ Q $. Dado que $ sum_i b_i <p leq q $ y $ q equiv p pmod {p-1} $, en algún momento encontraremos un polinomio (único) que satisfaga ambos requisitos anteriores.

¿Cómo realizamos este proceso algorítmicamente? Revisamos los índices de $ B_N $ a $ B_1 $ en orden. En cada punto, restamos de $ b_i $ la cantidad máxima $ alpha $ que mantiene el invariante $ G (1) leq P $. Después de procesar $ B_1 $, debemos alcanzar el polinomio deseado. (Básicamente estamos mirando la expansión base de $ P -1 $ de $ P - G (1) $.)

Answer 2

Si $ P = 1 $, entonces las restricciones son $ F (1) = 1 = Q $ que se resuelve fácilmente dependiendo del valor de $ Q $. Supongamos ahora $ p ge 2 $. Suponga que $ f (x) = sum_k a_k x^k $ es una solución. Entonces $ q = a_0 + a_1 p + a_2 p^2 + ldots + a_n p^n $ donde $ n $ es el grado de $ f $ ($ a_n ne 0 $).

Para cualquier $ k le n $, $ a_k le dfrac {q} {p^k} $. Esto da un límite en cada coeficiente.

Dado que $ p gt 1 $, esta inequación también da un límite para el grado de $ f $: $ 1 le a_n le dfrac {q} {p^n} $ so $ n le dfrac { log ( q)} { log (p)} $.

Esto muestra que solo hay un número finito de polinomios candidatos. Luego puede enumerar todas las soluciones posibles. Primero calcule el máximo grado $ n $ de $ f $. Luego buce los posibles grados ($ N $ a $ 0 $). Para cada valor de grado $ m $, realice los valores posibles de $ a_m $; Para cada valor de $ a_m $, revise los valores posibles de $ a_ {m-1} $, y así sucesivamente. Mantenga las sumas parciales $ s_k = a_m p^m + ldots + a_k p^k $ y $ r_k = a_m + ldots + a_k $; Si alguna de estas sumas excede $ Q $ o $ P $ respectivamente, aborta esta rama del árbol. Cuando llega a $ k = 0 $, las restricciones en $ f $ son $ s_1 + a_0 = q $ y $ r_1 + a_0 = p $, así que verifique si $ s_1 - r_1 = q - p $.

No tengo idea de si este enfoque es práctico: puede haber un algoritmo significativamente más rápido que explote más la divisibilidad.

Answer 3

Necesita un polinomio tal que $ F (1) = P $ y $ F (P) = Q $. Esto se puede hacer hasta $ p neq 1 $, $ p, q> 0 $ y $ frac {qp} {p-1}> 0 $ (o $ p = q = 1 $). En todos los casos, un polinomio $ ax^n+b $ es suficiente. Aquí $ P^{n+1}> q $. Tenga en cuenta que no $ N $ es demasiado grande.