Why does this pattern of large primes appear in this series?

Question

I tried calculating the series $z_{n+1} = z_n^2 + 1/4$ using fractions to keep the values exact. There's little cancellation, so the resulting integers diverge quickly. But a surprising pattern emerged:

(This is Mathematica code but simple enough to read as pseudo-code)

    c = 1/4;
    z = 0;
    Do[
     z = z^2 + c;
     Print[FactorInteger[Numerator[z]]], {i, 1, 10}]

The output for each iteration is a {prime factor, exponent} list for z's numerator:

(*

{{1,1}}

{{5,1}}

{{89,1}}

{{5,1},{4861,1}}

{{101,1},{16479949,1}}

{{5,1},{89,1},{16589129306474069,1}}

{{29,1},{1549,1},{3106941419772552263731365858433609,1}}

{{5,1},{4861,1},{34469,1},{57804649748579254030495262238075339775807968204231935465462520396029,1}}

*)

Notice that all the exponents are 1, and there are always a small number of factors that includes VERY large primes. The denominators are all powers of 2, so it's not just that the small primes are getting cancelled. I can't imagine why a pattern like this would emerge, and I'm hoping someone can give a more insightful explanation than my officemate's "It just... DOES." :-)

Update: A similar pattern of large primes of power 1 emerges with all the other fractions I tried. The only small prime factors or higher exponents that appear are the ones in the original numerator; other than that, it's all large primes to power 1.

Answer 1

With some starting points and some $c$ you will get some numerators divisible by the square of a prime. Thus the numerator of $x_n$ is divisible by $3^2$ for all even $n$ if $c \equiv 8 \mod 9$ (this includes a fraction $a/b$ where $b$ is coprime to $3$ and $a +b$ is divisible by $9$) and $x_0 \equiv 0 \mod 3$. Or if you want to stick to $c = 1/4$, the numerator of $x_2$ will be divisible by $13^2$ if $x_0 \equiv \pm 44 \mod 13^2$.

EDIT: In general, for a given prime $p$, any $c$ and any starting point, the function $f(x) = x^2 + c \mod p$ on the integers mod $p$ has some fixed points and/or cycles, and with any starting point $x_0$ the iteration $x_{n+1} = f(x_n)$ will eventually (and in fact pretty soon, because the function is almost two-to-one), hit one of those fixed points or cycles, and thus is eventually constant or periodic. Usually there are only a few of these cycles or fixed points. The value $0$ may or may not be in a cycle (it won't be a fixed point unless $c \equiv 0 \mod p$). Thus if a small prime $p$ doesn't occur in the numerator in the first few iterations, it won't ever occur. This somewhat explains the prevalence of large primes. Similarly for $p^2$ instead of $p$.