For which composite $s$ does $p^k - s$ hit a prime for small prime $p$ and integer $k\ge 1$?
问题内容
Let $s \ge 4$ be a composite integer with $s \ne 0 \pmod3$. Computationally, for every such $s \le 2000$, I can find a prime $p$ and integer $k \ge 1$ such that $p^k - s$ is prime (usually with $p \in \{2,3\}$ and small $k$).
Heuristically this seems unsurprising: for fixed small $p$, the values $p^k - s$ for $k = 1,\dots,20$ give many candidates, each prime with probability $\sim\frac{1}{\log(p^k - s)}$ by PNT, so the expected number of hits is large.
My question: Is this a known/named result, or a straightforward consequence of an existing theorem (e.g. related to Bateman–Horn-type heuristics for exponential sequences, or sieve methods)? I haven't found a reference for primality in sequences of the form $({p^k - s})_k$ for fixed $p$, only for polynomial families. Any pointers to relevant literature would be appreciated.
What I've tried: exhaustive verification for $s \le 2000$, and a robustness check (no counterexamples) using digit sums of primes up to $1.5×10^{11}$, though this doesn't extend the range of $s$ tested since digit sums grow only like $O(\log P)$.
回答 (2)
I don't think this follows from any known theorem. Bateman–Horn is about polynomial values, not exponential sequences like $p^k-s$, so it does not apply here.
Your heuristic is the standard one. For fixed $p$, $p^k-s$ has size about $$p^k$$, so by the prime number theorem $\Pr(p^k-s\text{ is prime})\approx 1/\log(p^k)=1/(k\log p)$. Since $\sum_k 1/(k\log p)$ diverges, one heuristically expects infinitely many prime values (after excluding obvious local congruence obstructions), which is much stronger than asking for a single hit.
Unfortunately, nothing close to this is known unconditionally. Even proving infinitely many primes of the form $2^k-1$ is open, so current methods are far from establishing primality in general exponential sequences. I am not aware of any theorem guaranteeing that for every composite $$s\not\equiv0\pmod3$$ there exist a prime $p$ and $k\ge1$ with $p^k-s$ prime.
The statement is false, even if “small prime” is replaced by “any prime.”
Consider $s=12000697=179\cdot67043$. This is composite, and $s\equiv1\pmod3$. I claim that $p^k-s$ is never prime for any prime $p$ and any $k\geq1$.
First suppose that $p$ is odd. Since both $p^k$ and $s$ are odd, $p^k-s$ is even. If it were prime, it would have to equal $2$, so $p^k=s+2$.
But $s+2=12000699=3^2\cdot1333411$, and $3\nmid1333411$. Thus $s+2$ has two distinct prime divisors and is not a prime power. Hence no odd prime $p$ works.
It remains to consider $p=2$. The following congruence classes cover every integer $k$, as one can check modulo $36$:
- if $k\equiv0\pmod2$, use $q=3$;
- if $k\equiv1\pmod4$, use $q=5$;
- if $k\equiv1\pmod3$, use $q=7$;
- if $k\equiv11\pmod{12}$, use $q=13$;
- if $k\equiv15\pmod{18}$, use $q=19$;
- if $k\equiv27\pmod{36}$, use $q=37$;
- if $k\equiv3\pmod9$, use $q=73$.
Our choice of $s$ satisfies $s\equiv1,2,2,7,12,6,8\pmod{3,5,7,13,19,37,73}$, respectively. These are exactly the corresponding residues of $2^k$ in the seven cases above. Therefore, for every $k\geq1$, the number $2^k-s$ is divisible by at least one of $3,5,7,13,19,37,73$.
Finally, $2^{23}<s<2^{24}$ and $2^{24}-s=4776519>73$. Thus $2^k-s\leq0$ for $k\leq23$, while for $k\geq24$ it is positive and larger than its divisor from the covering. Hence it is composite.
So $p^k-12000697$ is never prime for any prime $p$ and any $k\geq1$.
This also explains the failure of the heuristic. The numbers $p^k-s$ do not behave like independent random integers: powers of $p$ are periodic modulo every fixed prime, and finitely many such divisibility conditions can cover all exponents.
This is a covering-congruence argument, closely related to the constructions used for Sierpiński and Riesel numbers. Bateman--Horn is not directly applicable, since it concerns polynomial values, while $p^k-s$ is exponential in $k$.
For background on shifted exponential sequences, see Järviniemi and Teräväinen, Composite values of shifted exponentials.