A comment in A007018 a(n) = a(n-1)^2 + a(n-1), a(0)=1 claims

Subsequence of squarefree numbers (A005117). - Reinhard Zumkeller, Nov 15 2004

Is that really so?

As far as I know, it is an open problem if a polynomial $f \in \mathbb{Z[x]}$ of degree $\ge 5$ can be squarefree infinitely often (some sources require $f$ to be irreducible).

If the OEIS comment is correct, the sequence will give an infinite family of (irreducible) polynomials which are squarefree infinitely often.

Denote by $a_n$ the terms of OEIS A007018. Set $a_n = x$ and $$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}$ will be squarefree infinitely often (including the irreducible degree 8 factor) and iterating $x \mapsto x^2+x$ will produce an infinite family of polynomials with this property.

Added For references of squarefree values of polynomials, the search terms are square free values of polynomials. E.g. here p.1 and here "11. Squarefree values of polynomials".

  • 7
    $\begingroup$ As noticed here: mathworld.wolfram.com/SylvestersSequence.html, it is not known whether all of them are square-free. $\endgroup$ – Ilya Bogdanov Jan 4 '13 at 13:15
  • 7
    $\begingroup$ Sylvester’s sequence is your $a(n)+1$. Since $a(n)=a(n-1)(a(n-1)+1)$, your sequence consists of squarefree numbers if and only if Sylvester’s sequence does. $\endgroup$ – Emil Jeřábek Jan 4 '13 at 13:35
  • 3
    $\begingroup$ For the first 100 primes, the sequence becomes periodic modulo $p^2$ without passing through $0$. $\endgroup$ – David E Speyer Jan 4 '13 at 13:39
  • 3
    $\begingroup$ Hm, Mathworld only says that the sequence is squarefree for the first 10e15... $\endgroup$ – Per Alexandersson Jan 4 '13 at 14:09
  • 1
    $\begingroup$ You can't ping two people in one comment, joro – only the first person gets notified when you try to do that. $\endgroup$ – Gerry Myerson Jan 15 '18 at 18:30

Prime factors below $10^{10}$ of $a_n$ can be found in OEIS A007996, and I've tested that none of them divides $a_n$ when squared. Same was reported by Andersen earlier for primes below $2^{32}$.

In fact, the divisibility by $p^2$ can be quickly disproved for many primes $p$ if one tries to unroll the sequence backwards starting with $a_n \equiv 0\pmod{p^2}$ for the smallest index $n$, thus giving $a_{n-1}\equiv -1\pmod{p^2}$. While this leads to solving a quadratic equation modulo $p^2$ with respect to $a_{n-2}$ and potentially can give two roots, in roughly half of the cases the equation will have no solutions. Then we solve a quadratic equation for $a_{n-3}$ and so on. On average this process stops within a constant number of steps without reaching $a_1\equiv 2\pmod{p^2}$ (meaning that $p^2$ cannot divide $a_n$).

Since solving quadratic equation (via computing square roots) modulo $p^2$ is relatively time-consuming, for "persistent" primes $p$ that survived a certain number of square-root computations it's worth to switch to direct computation of $a_n$ modulo $p^2$ until the zero residue or the period is encountered. I used the threshold of 100 square-root computations for this purpose. With this mixed strategy the search for prime divisors can be easily extended beyond $10^{10}$ if needed.

  • $\begingroup$ The roots modulo p^2 are 0 and p^2-1, right? $\endgroup$ – joro Jul 10 at 8:49
  • $\begingroup$ @joro: Yes, but zero is dropped if we assume that $n$ is the smallest index giving divisibility by $p^2$. $\endgroup$ – Max Alekseyev Jul 10 at 13:29
  • $\begingroup$ @joro: I've clarified this issue in the answer. In fact, I worked directly with the Sylvester sequence $a_n+1=a_{n+1}/a_n$, where all terms are co-prime. $\endgroup$ – Max Alekseyev Jul 10 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.