Does $2^n-n$ have infinitely often a prime divisor greater than $n$?

Question

I think the question in the title is clear.
Let $n\in \mathbb{N}$. It is a nice exercise to show that every prime number divides infinitely many terms of the sequence $2^n-n$. (For example take $n=(p-1)^{2m} , m\in \mathbb{N}$)
I would like to show that there are infinitely many primes for which $2^n\equiv n\pmod{p}$ is actually satisfied for some $0<n<p$ which is equivalent to the question already existing in the title.
Any ideas?

Answer 1

The answer is positive.

For natural $N$, let $n=2^N$. We are interested in large prime factors of $2^{2^N}-2^N=2^N(2^{2^N-N}-1)$.

The second factor is of the form $2^k-1$ where $k=2^N-N$ is not necessarily prime. These numbers are called Mersenne numbers (different definition requires $k$ to be prime, we do not use it).

According to this paper, p.1, Schinzel showed that the largest prime factor $p$ of $2^k-1$ satisfies $p \ge 2k+1$ for $k > 12$.

So for $N$ large enough, we have infinitely often $2 \cdot (2^N-N) +1 > 2^N=n$.

Answer 2

Let's try some elementary counting. On one hand, $\sum_{n=1}^N\log(2^n-n)\ge cN^2$. On the other hand, if we assume that no prime in the prime factorization of $2^n-n$, $n\le N$ is greater than $N$, then this sum can be rewritten as $\sum_{p\le N}\sum_{\ell\ge 1}Q(p,\ell)\log p$ where $Q(p,\ell)$ is the number of $n\in[1,N]$ such that $p^\ell$ divides $2^n-n$. It remains to get some reasonable bounds for $Q(p,\ell)$.

The first key observation is that if $m<n$ are such that $k=n-m<p$ and $p$ divides both $2^m-m$ and $2^n-n$, then $p$ divides $(2^k-1)m-k$, so $m$ is determined by $k$ modulo $p$. This implies that in every interval of integers of length $p$ there may be at most $C\sqrt p$ numbers $n$ such that $p$ divides $2^n-n$ (otherwise there would be two different pairs with the same difference) and we get the first "nontrivial" bound $$ Q(p,\ell)\le C\frac{N}{\sqrt p} $$ This is quite good as long as small $\ell$ are concerned. Indeed, for the range of summation $\ell\le N^{1/3}$, say, we get only $$ N\cdot N^{1/3}\log N\sum_{p\le N}\frac 1{\sqrt p}=O(N^{11/6}\log N)\,. $$

Now we need to improve this bound for $\ell>N^{1/3}$. Note that in this case $p^\ell$ is huge compared to any fixed power of $N$. Thus we can try the same argument with arbitrary $m<n<N$ such that $p^\ell$ divides both $2^n-n$ and $2^m-m$ and notice that $k$ determines $m$ modulo $p^{\ell-\ell_p}$ where $p^{\ell_p-1}<N\le p^{\ell_p}$. But this number is still greater than $N$, so each difference is unique. This gives us the estimate $Q(p,\ell)\le C\sqrt N$, but this is not quite enough, so we now look at the differences.

If $p^\ell$ divides both $2^{k'}m'-n'$ and $2^{k''}m''-n''$ with $k''=k'+k$, then it also divides $2^km''n'-m'n''$, so $k\ge \ell\log_2p-2\log_2N\ge c\ell\log p$. This separation of the differences improves the bound to $$ Q(p,\ell)\le C\sqrt {\frac N{\ell\log p}}\,. $$ Taking into account that we need to sum in $\ell$ just up to $N/\log_2 p$, we finally get that large $\ell$ can contribute only $N\pi(N)=o(N^2)$.

Small morning edit To ensure that $2^km''n'-m'n''\ne 0$ in the last part of the argument, just consider odd $n$ only in the whole story.

Answer 3

Let $m>1$ be a natural number, and $p$ be a prime divisor of $(m+1)2^m+1$. Then $n=p-m-1$ does the trick.

EDIT: On second thought, there is a catch. As Ofir Gorodetsky suggested, it is not difficult to show that infinitely many primes may be obtained this way. But I do not know how to show that infinitely many of them will satisfy the inequality $p>m+1$. (Of course, actually there is a lot of them, but this may be tricky to prove.)