Edit 2018.08.08 This answer https://mathoverflow.net/a/307881 will be updated to give recent information about S, especially a forthcoming preprint. End Edit 2018.08.08

In an introductory post on Grimm Machines, I give a narrative to suggest why the following link between a given algorithm S and Grimm's conjecture should be studied. In this post, I give a summary (as suggested by Wlodzimierz Holsztynski) as well as new information and a new technical question.

Let a map $f$ on natural numbers greater than 1 be called a divisor map if for every $n$ one has $f(n)$ divides $n$. This post looks at divisor maps which take on prime values. For such maps $f(2)=f(4)=2$, so $f$ is not injective, not even when restricted to the interval $[2,4]$.

This post looks at maximal prime-free intervals, i.e. for each pair of consecutive primes $p$ and $q$, let $I=(p,q)$. If for every such $I$, $f$ restricted to $I$ is injective, then I call $f$ an injective divisor map, and Grimm's conjecture effectively asks if such a map exists. (Technically, Grimm asked about subintervals of such $I$ as well. By Bertrand's postulate or other results, a map for $(p,q)$ implies one for $[p,q]$ and possibly larger intervals.)

The algorithm S has been described in detail elsewhere. Briefly, consider at the start $n=2$ and the natural numbers $\geq n$ having a stone on each prime $p$ labeled with that prime, then find $n+kp \gt n$ least without a stone and move that stone there; now repeat with $n+1$. Each number gets paired with exactly one stone, and the map from numbers to the labels gives a divisor map $S(n)$, which is almost an injective divisor map. The other post discusses where $S(n)$ is known not to be injective, and how to modify it to be injective on the known portion.

A different map is given by $L(n)$, the largest prime divisor of $n$. Below $4*10^8$ it has over three hundred failures of injectivity; each failed interval with one exception (with smooth $n,L(n)$ pairs 265635,17, 264639,41, 265650,23, 265680, 41, and 265696,23) has precisely one point of failure, and the largest number of smooth $n$ in a failed interval which contains another multiple of $L(n)$ in that interval is 7, giving much room for fixing the map. Further, most of the intervals yield to an obvious Case II fix. I counted those intervals where a potential conflict might arise (is $L(m)$ a non-largest prime factor of $n$ for smooth $m$ and $n$ in the interval) and found less than twenty such intervals. Since most such failures are resolved by $S(n)$, I did not bother to find resolutions for these potential conflicts.

Of course more references are wanted, and questions regarding S in the other post can be asked about $L$ here. However, I point out a few specific questions about $L$ and the statistics gathered.

Why does $L$ do a much worse job than S in providing a Grimm mapping? Can we estimate how much worse?

Notice the embarrassing example (523,541) has a Case II (even Case I) fix now. Are all the failures fixable by case II?

Suppose we just look for improvements. Can we find a natural definition of a divisor map which (for the first $10^9$ intervals) does better than $L$? Better than S?

A combination (pick $L$ or S, which ever gives an injective map) leaves only 6 intervals all less than 1,000,000 in doubt, and each of those 6 is easily fixed, most of them by case I. However, this is not as natural a method as I would hope.

After browsing through papers of Erdos, Laisham and Murty, and Zhang, I found some generalizations of Grimm's conjecture being considered. I recommend the Laisham and Murty paper for an overview, where is mentioned that Grimm's conjecture implies the existence of a prime between consecutive squares. Grimm's conjecture along with a conjecture on smooth numbers implies a bound on prime gaps eventually strictly smaller than $p^\epsilon$ for every fixed real $\epsilon \gt 0$.

The literature shows connections to smooth numbers, prime gaps, number of factors of binomial coefficients and so on, and has a connection to another MathOverflow question Prime divisors of the respectively minimal binomial coefficients

• http://arxiv.org/abs/1306.0765 Laisham, Murty: Grimm's Conjecture and Smooth Numbers

• http://arxiv.org/abs/0811.0966 Shaohua Zhang : A Refinement of the function g(m) on Grimm conjecture

Edit 2016.08.24 At W.H.'s polite request, I revised the title. I ran computations for $L$ out to $1.6*10^9$ and found about 100 additional intervals on which $L$ is not injective. I will try a modified version that combines S and $L$ and report back. It seems many (maybe all but one?) of the $L$ intervals have a Case I fix, because there are very few smooth numbers between consecutive primes, and powers of 2 seem to avoid most of the problematic intervals. Until another natural divisor map suggests itself to me as being a good candidate for a Grimm map, I am going with a modified version which runs S and $L$ and uses S unless $L$ works better.

I have a part of an idea which suggests why S works better. Every jump of a prime $p$ for a distance $kp$ requires that its target $n+kp$ have its largest prime factor at most $kp$. Thus small primes tend to skip over nonsmooth numbers in a fashion where I am trying to quantify nonsmooth. In any case, $L$ fails to be injective through multiples of many pairs of consecutive or nearby pairs of smooth numbers, while $S$ fails to be injective due to short jumps of a prime when longer jumps might normally be expected. END Edit 2016.08.24.

Gerhard "Matchmaker Find Me A Find" Paseman, 2016.08.23.