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.

8more comments