I am writing a paper to accompany a Short Communication I plan to give in Rio this August. The paper regards work on jumping primes, a project on which Jose Brox has been working with me. I was going to offer the following conjecture for interested ICM attendees to ponder when I realized that there is no reason to keep the fun to myself. As an additional incentive, I offer a Starbucks card or equivalent (value around 25 USD) for its resolution, as well as any mention I can make in Rio. I state the conjecture, and then present the background to understand and approach it.
Conjecture: In computing $S$, a prime $p$ that starts from a multiple $n (=kp)$ and skips the next multiple $((k+1)p)$ will land on a multiple $lp$ no further than $4\sqrt{n}$ away ($(lp - kp)^2 \lt 16kp$).
Background: $S$ is the name of an algorithm I have been looking at since 2016 in relation to Grimm's conjecture. Start with On comparing two almost injective divisor maps on injective divisor maps and work your way back through the links (or check out my user page for the questions on this) for the specifics; simulations up to $n=10^{12}$ give evidence supporting the conjecture, and it appears confirmed for all $n$ at most $10^{11}$.
Most of the time, $S[n]=p$ where $p$ is a large prime divisor of $n$ (roughly log 2, or about 69%, of numbers $m$ below $n$ have their largest prime divisor satisfy $p*p \gt m$), and in most of these cases, the algorithm jumps $p$ ("starting from $n$", although there are better verbs than 'starting') to $n+p$, so $p$ jumps but does not skip a multiple of $p$. Here $p \gt 4\sqrt{n}$ often, so the conjecture ignores the cases when $p$ does not skip.
Some of the time $S[n]=p$ where $p$ is a small prime. Much time is spent by me thinking about the right definition of small, but when $p=2, p$ goes from smooth number to smooth number, where here the largest prime factor of the landing spot $m=lp$ is often at most about $n^{0.4}$ (roughly), and for slightly larger primes than 2, the smoothness pattern holds (once $p$ gets far enough away from its square, that is). In any case, the right intuition is that small primes skip from smooth number to smooth number because 1) the non-smooth multiples of $p$ already have large primes occupying them, and 2) these smooth numbers are usually not adjacent multiples, so $p$ has to skip a multiple to get to the next smooth number. While these small primes skip a lot, they usually do not skip even as far as $\sqrt{n}$, so the conjecture ignores these small primes (or rather, says that most non-large primes behave like small primes in not skipping too far).
The case when small $p$ make short jumps is of interest too. Grimm's conjecture implies that smooth numbers do not bunch together without including big primes, and $S$ not making short jumps often lends support to the truth of Grimm's conjecture, but the conjecture above addresses something different.
Primes larger than $\sqrt{n}$ avoid each other in this dynamic, because the potential collision points are bigger than $2\sqrt{n}$ away from $n$ (think twin primes and $p(p+2)$). One can extend this a little to primes slightly less than $\sqrt{n}$, but even if the bigger prime skips for whatever reason, it has to skip at least one more multiple or more to land past $4\sqrt{n}$, which is unlikely if a smaller prime has not skipped far.
Indeed, a recent simulation up to $10^{11}$ has shown that the largest skips (with a few exceptions below $n=1000$) made up to a number $n$ have been by a prime $p$ with $p^2 \lt 4n \leq 4p^2$. One is tempted to say this is because $p$ skips over $pq$ where $q$ is a prime about a fourth the size of $p$, but this is not always the case. One of the first (but not most extreme) examples of this is 13 skipping over 78 because 2 got there (from 65-1) first. Another is 43 skipping over 645 because of 3.
Because of the relative density of small primes, we have 17 skip from 289 to 340 and 29 skip from 841 to 928. These are the largest cases observed of a maximal skip length being a multiple of 3; all the larger skips observed are twice a prime, and are less than $4\sqrt{n}$. A large example is 40499 jumping from 422323572 skipping over (10429*40499). Another is given by 95763014340 1190638 595319, with the middle number being the jump length.
This conjecture has practical consequences, the most immediate being that we can improve resource usage of programs simulating $S$ quickly. I think it also represents a key fact in the theory of $S$, and is a nice step on the way to new results on the distribution of both smooth and prime numbers. If proven on this forum soon enough, it will serve as a success story and can serve as a good advertisement for MathOverflow.
Gerhard "Fame And Almost Free Coffee" Paseman, 2018.04.13.
