If $ \pi (x) $ := number of primes $ \leq x $, the operation

$T(x_{n+1}) = x_{n+1} - \pi(x_{n+1}) = x_n$

gives a sequence whose elements are those for which repeated application of T gives the preceding elements of the sequence. For example:

$s(n) = \{1,2,4,8,14,22,33,48,66,...\}$. The next term is 90, because T(90) = 66. This does not adequately define the sequence.

Explicitly, I constructed the sequence as follows. I applied T to n = 1,2,3,..., until there was a repetition:















The first element which results in an increase in the number of elements of the sequence is the one I included. For example, 1 is the first element for which the length of T is 1 (before repetitions). 4 is the first element to which T can be applied 2 times. 8 is the first element which T can be applied 3 times. And so on.

My question is whether first differences between successive elements cannot be shown to be strictly increasing. This need not be the case. It might be that the only primes less than $x_{n+1}$ are those less than $x_n$, so $\pi(x_{n+1}) = \pi(x_n)$. Then the next element after 90 might be 114, so while the sequence is strictly increasing, if there was (for the sake of argument) no prime between 90 and 114, so the difference 114 - 90 would equal to 90 - 66. It's obviously not true for the example, but in general I don't think it's obviously true.

I think equivalently: can we show there is a prime between each element of the sequence as defined?

Hopefully this is well-defined with the additional note. Thanks for any insight.


If $\pi(x_{n+1})=\pi(x_n)$ then there are no primes between $x_n$ and $x_n+\pi(x_n)$ which is to say, roughly, (and writing $m$ for $x_n$) no prime between $m$ and $m+{m\over\log m}$. Now it is widely believed that there is always a prime between $m$ and $m+2(\log m)^2$; if we could prove the Riemann Hypothesis, we would know that there is always a prime between $m$ and something like $m+\sqrt m\log m$; both of these are much shorter gaps than that between $m+{m\over\log m}$ (at least, for large $m$).

I don't know offhand what the best unconditional bound is for gaps between primes (but you could probably find it by searching for some term like "gaps between primes"), but I think there's a number $c$ strictly between 1/2 and 1 such that it's known that there's always a prime between $m$ and $m+m^c$ for $m$ sufficiently large. That's enough to show that there are at most finitely many places where your first differences are not strictly increasing, maybe even to bring it within computational range to prove there are no such examples. And since the known results about prime gaps are so much weaker than the conjectured ones, I'd be confident that there are no examples at all.


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.