50
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This question is also on math.SE, posted by someone else. $\endgroup$ – Julian Rosen Oct 9 '16 at 12:59
  • 7
    $\begingroup$ Just for the record: dxdy.ru/topic111861.html artofproblemsolving.com/community/q1h1316016p7069861 $\endgroup$ – Max Alekseyev Oct 9 '16 at 13:09
  • 3
    $\begingroup$ @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. $\endgroup$ – Pace Nielsen Oct 11 '16 at 20:24
  • 2
    $\begingroup$ 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$. $\endgroup$ – Pietro Majer Oct 12 '16 at 12:18
  • 2
    $\begingroup$ 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$. $\endgroup$ – Terry Tao Nov 5 '16 at 21:31
1
$\begingroup$

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.

$\endgroup$

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.