# Iterations of $2^{n-1}+5$: the strong law of small numbers, or something bigger?

I've discovered what I believe is a quite remarkable sequence (A318970), defined by $$n_1 = 3,\qquad n_{k+1} = 2^{n_k-1}+5\quad(k\geq 1).$$ Here are the first four terms with their prime factorizations: $$\begin{split} n_1 &= 3,\\ n_2 &= 2^2 + 5 = 9 = 3^2,\\ n_3 &= 2^8 + 5 = 261 = 3^2\cdot 29, \\ n_4 &= 2^{260} + 5 = 3^2\cdot 29\cdot p_{76}, \end{split}$$ where $$p_{76}$$ is a 76-digit prime.

The remarkable property of this sequence is that $$n_k\mid n_{k+1}$$ for $$k=1,2,3,4$$. And I'm truly puzzled if this divisibility holds for all positive $$k$$ (in other words, if this sequence is a subsequence of A245594).

Here are some properties that I can prove:

• $$(n_k-n_{k-1})\mid (n_{k+1}-n_k)$$ for all $$k\geq 2$$;
• If $$n_k\mid n_{k+1}$$, then $$n_k\mid n_{k+t}$$ for all integer $$t\geq 0$$.
• If $$n_k\mid n_{k+1}$$ and $$\frac{n_{k+1}}{n_k}$$ is a prime, then $$n_{k+1}\mid n_{k+2}$$.

The last property seems to explain why we have the observed divisibility: $$\frac{n_2}{n_1} = 3$$, $$\frac{n_3}{n_2}=29$$, and $$\frac{n_4}{n_3} = p_{76}$$ are all primes. However, it is still possible that something bigger is going on, and I've not yet convinced myself in favor of either of the two possible outcomes:

Outcome #1. It's an instance of the strong law of small numbers, and we just got lucky to get the divisibility for $$k\leq 4$$. To disprove it for larger $$k$$, we need simply to find a prime factor of $$n_5$$ that does not divide $$n_6$$ (more generally, we need a prime factor of $$n_k$$ that does not divide $$n_{k+1}$$). The trouble here is that $$n_5$$ is really huge, and we can only hope to discover its small factors.

Outcome #2. The divisibility holds for all $$k$$ because this sequence is very special and satisfies some additional (yet unknown) property.

Here is an analogy with numbers $$m$$ such that $$m\mid (2^m+2)$$ (see A006517). In general, iterations of $$2^x+2$$ do not preserve this property (e.g., $$946$$ belongs to A006517, but $$2^{946}+2$$ does not). However, if we additionaly require that $$(m-1)\mid (2^m + 1)$$, then $$2^x+2$$ starts to "magically" preserve both properties, and thus delivers an infinite subsequence A219037 of A006517.

Does anybody have a clue what's going on here?

UPDATE #1 (Oct 11 2016). Seeing here and there erroneous attempts to compute $$n_k$$ modulo primes for large $$k$$, I'd like to make some remarks.

To compute $$n_k\bmod m$$, one needs to represent $$m=2^s\cdot t$$ with $$t$$ being odd, compute $$n_k\bmod 2^s$$ and $$n_k\bmod t$$, and combine these residues using CRT. For the former, we have $$n_k\bmod 2^s = 5$$ provided that $$n_{k-1}>s$$ (for $$k\geq 4$$, this holds for all $$m<2^{260}$$), while for $$k\leq 4$$ we can take as an answer $$n_k$$ itself. Computing $$n_k\bmod t$$ reduces to computing $$n_{k-1}$$ modulo Euler totient $$\varphi(t)$$: $$n_k \equiv 2^{(n_{k-1}-1)\bmod \varphi(t)} + 5 \pmod{t}.$$ These observations allow one to compute $$n_k\bmod m$$ recursively.

In the described recursive process, we can start rolling back as soon as we reach modulus $$1$$, modulo which the answer is always $$0$$. Reaching 1 happens within A227944$$(m) \leq \log_2(m)$$ iterations. An implication of this observation is that the sequence $$n_k\bmod m$$ stabilizes within first $$\log_2(m)$$ terms.

Here is an important consequence: if a prime $$p$$ does not divide any of the first $$\log_2(p)$$ terms, then it never divides any terms. This partially explains why it is so hard to find prime factors of the terms of this sequence.

UPDATE #2 (Nov 04 2016). Let me state some statements that are equivalent to $$n_k\mid n_{k+1}$$:

• $$n_k\mid n_{k+1}$$
• $$2^{n_k-1}\equiv -5\pmod{n_k}$$ or $$2^{n_k}\equiv -10\pmod{n_k}$$ (both congruences hold modulo $$n_{k+1}$$ by definition)
• $$2^{n_k}\equiv 2^{n_{k-1}}\pmod{n_k}$$ or $$2^{n_k-n_{k-1}}\equiv 1\pmod{n_k}$$ (both congruences hold modulo $$n_{k+1}-n_k$$)
• $$n_k\mid (n_{k+1}-n_k)$$
• $$10^{\frac{n_{k}-n_{k-1}}{n_{k-1}}}\equiv 1\pmod{n_k}$$, provided that $$n_{k-1}\mid n_k$$ (via Pietro Majer)

UPDATE #3 (Jan 24 2018). As explained in UPDATE #1 above, for every prime $$p$$, one can compute the set of indices $$k$$ such that $$p\mid n_k$$. This set is either finite (possibly empty), or includes all large enough integers.

Recently I've tested all primes below $$10^{13}$$ and found that the only primes in this range that ever divide $$n_k$$ are $$3$$, $$29$$, and $$31821709567$$. The last prime divides $$n_k$$ for all $$k\geq 8$$, and so it does not help to resolve the question in favor of either outcome.

UPDATE #4 (Oct 25 2018). I've extended the search for prime factors to $$10^{14}$$ and found only one more prime 28480625878963, which divides $$n_k$$ for all $$k\geq 11$$. The known prime factors are now listed in the sequence A318971.

• This question is also on math.SE, posted by someone else. Oct 9 '16 at 12:59
• Just for the record: dxdy.ru/topic111861.html artofproblemsolving.com/community/q1h1316016p7069861 Oct 9 '16 at 13:09
• @MaxAlekseyev This reminds me of the sequence of repeated Mersenne primes: 2^2-1=3, 2^3-1=7, 2^7-1=127, 2^127-1=big prime P, 2^P-1= who knows! The guess there is similar to your "Outcome #1", this is probably just the law of small(ish) numbers. Oct 11 '16 at 20:24
• A further observation (trying to reduce $n_{k+1}$ modulo $n_k$). Assume $a$ divides $b:=2^{a-1}+5$. Then $b$ divides $2^{b-1}+5$ if and only if $b$ divides $10^{\frac{b-a}{a}}-1$. For instance, to check that $n_3$ divides $n_4\sim 2\cdot10^{78}$ it is sufficient to check that it divides $10^{28}-1$. Oct 12 '16 at 12:18
• A small comment that may speed up your search for prime factors of $n_5$ (though only by a factor of 2): for any such factor $p$, $-5$ must be a quadratic residue, so by reciprocity we must have $p=1,3,7,9 \hbox{ mod } 20$. Nov 5 '16 at 21:31

I spent some time working this problem and discovered the following generalization. There's no new information here about the $2^{x-1}+5$ problem, so this is not much of an answer to that specifically. But we can say some similar things about some similar functions.

Let $F(x)$ be a composition of functions $x$, $c$, $c^\square$, $\square + \square$, $\square \cdot \square$, and $\square!$. For example, we might have $F(x) = 2^{6^x + x^2} + (x !)^2 + 3^x \cdot x - 3$, but not $F(x) = x^x$. Let $F^k(x)$ denote the $k^\text{th}$ iterate of $F$, so for example $F^2(x) = F(F(x))$.

Lemma: $F^k(x) ~\text{mod}~ m$ is eventually periodic in $k$.

Proof: First re-write $F(x)$ so that all the bases are factored into primes, for example $F(x) = 2^{6^x} = 2^{2^x \cdot 3^x}$. Now with $m = p^a \cdot b$ and $(p,b) = 1$, define $g_p(m) = \text{ord}_b(p)$, and observe that $p^{a+x} \equiv p^{(a + x) ~\text{mod}~ g_p(m)} ~\text{mod}~ m$. Assume as an inductive hypothesis that $F^k(x) ~\text{mod}~ n$ is eventually periodic in $k$ for all $1 \leq n < m$. By taking all the exponents $\text{mod}$ an appropriate composition of $g$ functions we get a function $G$ such that for sufficiently large $x$, $F(x) \equiv G(x) ~\text{mod}~ m$ — for example, if $F(x) = 2^{3^x+x}+x^7$, consider $G(x) = 2^{3^{x ~\text{mod}~ g_3(g_2(m))} + x ~\text{mod}~ g_2(m)} + x^7$ — then for sufficiently large $k$ we have $F^{k+1}(x) \equiv G(F^k(x)) ~\text{mod}~ m$ and combined with the inductive hypothesis and $g_p(m) < m$ this implies $F^k(x) ~\text{mod}~ m$ is an eventually periodic function of $k$. Factorials are allowed too since they are eventually equal to $0 ~\text{mod}~ m$ and we can remove them from the expression, but I'm not sure how to handle general $\square^\square$ power compositions or primorials.

$\square$

Corollary: If $x$ never occurs outside of an exponent in the expression defining $F(x)$, like $F(x) = 2^{x-1} + 5$ and $F(x) = 2^{7^x+x}\cdot 5^x +3$, but not like $F(x) = 2^x + x$ or $F(x) = 2^x \cdot x$, call it restricted. Then $F^k(x) ~\text{mod}~ m$ is eventually fixed (periodic with period $1$) for all $m$ if and only if $F$ is restricted. However, this doesn't really explain why it should be that $F^k(x) ~\vert~ F^{k+1}(x)$ as requested. It's simply a generalization of the observations in Update #1, but it applies to a much wider class of functions than I originally suspected.

Corollary: For all $x, m \in \mathbb{N}$, there exists a $q \in \mathbb{Q}$ such that for all $k \in \mathbb{N}$, $F^k(x) \equiv \lfloor q \cdot m^k \rfloor ~\text{mod}~ m$. If $F$ is restricted then $q$ has a denominator of the form $m^z \cdot (m-1)$.

An idea I have is to compute some of these rationals for various $F, m, x$ and find cases with the same $m$ and two different functions $F$ and $G$ where the corresponding rationals have some of the same base-$m$ digits at the same positions. Since it is impossible to evaluate iterates of $F$ and $G$ beyond small arguments, if there is no obvious reason for this relationship, then determining for exactly which $k$ is it the case that $m ~\vert~ F^k(x) - G^k(y)$ may turn out to be a good puzzle problem requiring essentially the argument above plus calculations.