¿Es OEIS A007018 realmente una subsecuencia de números libres de cuadrados?

Question

Un comentario en A007018 a(n) = a(n-1)^2 + a(n-1), a(0)=1 reclamaciones

Subsecuencia de números libres de cuadrado (A005117). - Reinhard Zumkeller, Nov 15 2004

¿Es realmente así?

Hasta donde yo sé, es un problema abierto si un polinomio $f \in \mathbb{Z[x]}$ de grado $\ge 5$ puede ser cuadrado infinitamente a menudo (algunas fuentes requieren $f$ sea irreducible).

Si el comentario de la OEIS es correcto, la secuencia dará una familia infinita de polinomios (irreducibles) que son libres de cuadrados infinitas veces.

Denote por $a_n$ los términos de la OEIS A007018. Consulte $a_n = x$ y $$f(x)=a_{n+4}=x \cdot (x + 1) \cdot (x^{2} + x + 1) \cdot (x^{4} + 2 x^{3} + 2 x^{2} + x + 1) \\\\ \cdot (x^{8} + 4 x^{7} + 8 x^{6} + 10 x^{5} + 9 x^{4} + 6 x^{3} + 3 x^{2} + x + 1)$$

$f(a_n)=a_{n+4}$ será libre de cuadrados infinitas veces (incluyendo el factor irreducible de grado 8) e iterando $x \mapsto x^2+x$ producirá una familia infinita de polinomios con esta propiedad.

Añadido Para las referencias de valores libres de cuadrado de polinomios, los términos de búsqueda son valores libres cuadrados de polinomios . Ej. aquí p.1 y aquí "11. Valores cuadráticos de polinomios".

Answer 1

Factores primos inferiores $10^{10}$ de $a_n$ en OEIS A007996 y he comprobado que ninguno de ellos divide $a_n$ al cuadrado. Lo mismo fue informado por Andersen antes para primos inferiores a $2^{32}$ .

De hecho, la divisibilidad por $p^2$ se puede refutar rápidamente para muchos primos $p$ si se intenta desenrollar la secuencia hacia atrás empezando por $a_n \equiv 0\pmod{p^2}$ para el índice más pequeño $n$ dando así $a_{n-1}\equiv -1\pmod{p^2}$ . Aunque esto lleva a resolver una ecuación cuadrática módulo $p^2$ con respecto a $a_{n-2}$ y potencialmente puede dar dos raíces, en aproximadamente la mitad de los casos la ecuación no tendrá soluciones. Entonces resolvemos una ecuación cuadrática para $a_{n-3}$ etc. Por término medio, este proceso se detiene en un número constante de pasos sin alcanzar $a_1\equiv 2\pmod{p^2}$ (lo que significa que $p^2$ no puede dividir $a_n$ ).

Dado que la resolución de ecuaciones cuadráticas (mediante el cálculo de raíces cuadradas) módulo $p^2$ es relativamente lento, para primos "persistentes" $p$ que tras un cierto número de cálculos de la raíz cuadrada vale la pena pasar al cálculo directo de $a_n$ modulo $p^2$ hasta encontrar el residuo cero o el punto. Para ello, he utilizado el umbral de 100 cálculos de raíz cuadrada. Con esta estrategia mixta, la búsqueda de divisores primos puede ampliarse fácilmente más allá de $10^{10}$ si es necesario.