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
Just as the Collatz conjecture can be considered as dealing with a discrete dynamical system having number theoretic overtones, so too can the following process (based on algorithm S) be considered. One purpose of this post is to advertise this process so that others can simulate it and generate a lot of data and some other conjectures. The main purpose is to ask for references and some ideas about approaching the conjectures below. I hope the narrative style is tolerable. I continue the narrative with two main ingredients.
Ingredient one: In the MathOverflow Question How Do These Primes Jump? I consider a basic algorithm S which is a resource-constrained Sieve of Eratosthenes. Follow the link for the details; the idea is to process the positive numbers greater than 1 in increasing order so that for every prime (uncovered number), one acquires a new stone labelled with that prime, and places the stone (covers) on the next uncovered multiple of that prime (which can be proved to be twice that prime), and so that for every composite (a covered number) one picks up the stone that covers the composite and has label p on it, and move it the least multiple of p distance greater than the composite to a number that is not covered. The question considers trajectories of stones given the constraints that no number ever gets covered by more than one stone, and that the numbers are processed serially in increasing order. One result of this is a mapping from natural numbers n greater than 1 to primes $q_n$ such that $q_n$ divides n. There is an answer which is a partial analysis of the behaviour of the trajectories.
Ingredient two: Grimm conjectured that for every positive integer n, there was an injective map from the interval of integers $(p_n, p_{n+1})$ (the composites between two consecutive primes) to the set of primes Q so that each prime divided the number mapping to it: for every pair $s,t$ in the interval, $q_s | s$ and $q_t | t$ and $q_s=q_t$ implies $s=t$. I call such a map an injective divisor map. There are some natural extension of this conjecture and obvious restrictions of the conjecture. As an example, if P is a set of $k$-many distinct primes, and an interval contains $k+1$ P-smooth numbers, then there is no injective divisor map from that interval.
(Rhetorical question): Wouldn't it be great if algorithm S provided the injective maps of Grimm's conjecture?
Unfortunately S doesn't do this for all intervals. However, it comes tantalizingly close, and the next few paragraphs motivate the study and the questions to follow.
Let us look at some failures. $S(n)$ is the prime that algorithm S uses to cover the number $n$, so $S(n)|n$. I restrict myself to those intervals between two consecutive primes, containing $k = p_{n+1} - p_n - 1$ composite numbers. One can show the existence of an injective divsor map when $k \lt 4$ easily, so assume there are $k \gt 4$ many composites in the interval. (One can also show this existence for larger values of $k$, but for $k=5$ it is more complicated, and seems to grow exponentially when $k$ has 2 added to it.) Further, if $S(n)\geq k$, there will be no other number in that interval with the value $S(n)$, so that only those $n$ in the interval with $S(n)\lt k$ are of interest.
The first failure occurs in the interval (113,127). The small values of $S(n)$ that occur for $n$ = 117,120,121,125,126 are 13,5,11,5,3, respectively. Notice that 2 does not appear in this range (its trajectory goes from 108 to 128), so we can "fix" this map simply by having 120 map to the divisor 2. Many of the failures can be fixed by replacing $S(n)$ by 2. I come to the first part of the Grimm machine:
Case I: If the interval has just two numbers $n$ and $m$ with $S(n)=S(m)$ (and otherwise $S(n)$ is injective on the interval) and one of $n$ and $m$ (say it is $n$)is even, and 2 is not in the image of the interval, "fix" the map by replacing $S(n)$ with 2, and one gets the desired map of Grimm for this interval.
The next failure occurs in the interval (523,541). This one is a little embarrassing, so I will save it for later.
The next failure occurs with S(868)=S(875)=7. This is also a case I failure, fixed by sending 868 to 2. (The other small values of S on the interval are 3 and 5. That 868 could also be assigned to 31 is a fix that is discussed below.)
The next failure occurs with S(2040)=S(2048)=2. 2 is the only small value of S occurring in this interval, so this time the repair is to take any nonsmall prime divisor of 2040, although any odd prime divisor of 2040 will do for this interval. Since the interval is small ($k=$ 13), sending 2040 to 17 fixes this map as well, and gives us the next case.
Case II: If the interval has members $n$ which break the map $S(n)$ being injective, and $n$ has a nonsmall divisor $q$, fix the map by replacing $S(n)$ by $q$.
Since $q$ is nonsmall (so $q \geq k$), there will be at most one multiple of $q$ in that interval, and such a fix goes toward making the map injective. Notice that we could not repair the problem with S(120) and S(125) this way: S(125) can only be 5 and S(120) can only be 2 or 3. We could try altering more values of $S(n)$ for other values of $n$ in the same interval to get an injective map, but the fixes represented by Case I and Case II are small and easy.
The next failure occurs with S(3146)=S(3159)=13. This is reparable by case I.
The next failure occurs with S(9975)=S(10000)=5. This is not reparable by case I, since the interval has S(9984)=2. It is not reparable by case II at present, since the prime factors of 9975 are 3,5,7, and 19 (so neither 9975 nor 10000 have a nonsmall divisor $q$). However, 3,7 and 19 are not images of S in this interval, so let us pick one of those and replace it, using a rewrite:
Case II (revised): if the interval has members $n$ which break the map $S(n)$ being injective, and $n$ has a divisor $q$ that is not an image of the interval, fix the map by replacing one of the $S(n)$ by $q$. (Pick $q$ nonsmall if you can).
Now (with one exception), all of the failures above can be fixed with an application of Case II. Case I is a streamlined version when 2 is not in the image. If there are more than two values in conflict, more cases may need to be considered.
The next failure occurs with S(12987)=S(13000)=13. 37 is a nonsmall factor of 12987, so that is an (old-style) case II fix.
To tabulate the rest:
- S(28880)=S(28899)=19. Case I, using 2
- S(30600)=S(30625)=5. Case II revised, using 3 or 17
- S(531432)=S(531441)=3. Case II revised, using 11 or 61
- S(962370)=S(962407)=37. Case I, using 2
- S(1419840)=S(1419857)=17. Case I, using 2
- S(29360088)=S(29360128)=2. Case II, using 83 or 17
- S(43046640)=S(43046721)=3. Case I, using 2
- S(86968700)=S(86968750)=5. Case II old style, using either number and nonsmall 503 or 307 or both.
- S(139147995)=S(139148064)=3. Case II using 197 or 5 or others
So far algorithm S has been pretty good at providing Grimm maps below $4*10^8$, with only 15 examples of failure, 14 of which are easily repaired.
Let us return to the embarrassing case: S(528)=S(539)=11. The factors of 528 are 11, 2, and 3, and 11 and 7 for 539. We have S(540)=2, S(525)=3, and S(532)=7. Fortunately 5 is not in the image of this interval, and so we can make two changes: 528 gets sent to 3 and 525 gets sent to 5, and this modification now gives an injective divisor map on the interval. This is the most challenging case, which I suggest below:
Case III: If there are $t$ many primes less than $k$, and at most $t$ many $k$-smooth numbers $n$ in the interval, believe in the power of Grimm and find a 1-1 assignment from the $k$-smooth numbers to their divisors.
(Another way to approach the embarrassing example is to note 532 can be assigned to nonsmall divisor 19 and then assign 539 to 7.)
It is possible to find small intervals having many P-smooth numbers, but Grimm's conjecture suggests that all such intervals have enough primes separating these numbers.
I now present to you the Grimm Machine: Run algorithm S, and accept the output interval map or repair the map according to case I or case II. If neither Case I nor case II apply, cross your fingers and turn to case III. Here are the questions.
A. Are there any references (in addition to the brief Bibliography) which address Grimm's conjecture or small intervals of smooth numbers in such an algorithmic way?
(I am still going through the literature. If you know one of the items addresses these questions, please speak up.)
B. All of the examples found so far of troublesome intervals have exactly two numbers in the interval with the same S-value. Is this luck or the phenomenon of small numbers? Can one show that any interval in a prime gap has at most two numbers with the same S-value?
C. Except for the troublesome interval, there have been few $k$-smooth numbers in any interval. For example, the small S values for the interval containing 43046721 are 3,19,67,101, and 113, giving at most 6 113-smooth numbers in that interval (probably fewer, as I did not factorize the corresponding multiples $n$.) Even the troublesome interval had few enough $k$-smooth numbers, and they lent themselves to an injective divisor mapping.
Can one show that such smooth numbers occur not too frequently in prime gap intervals, giving a hope that Grimm's conjecture can be satisfied? What bounds can be given?
(Note that S can potentially provide an upper bound on the count of k-smooth numbers in an interval, but sometimes assigns a small divisor less than k to n even though n is not k-smooth.)
D. Is it reasonable to expect such success out of algorithm S? After all, there are more than 15,000,000 prime gap intervals with $k \gt 6$ and endpoints less than $4*10^8$, and S provides a Grimm map for all but 14 of them. And then, S wasn't intended to produce injective maps anyway. Can we hope that Case I, II, or III are needed only finitely many times? Or do we need examples out to $10^{100}$ before forming conjectures? (This is essentially a call to analyze the trajectories of S; if the gaps between occurrences of 2 or any other prime grow faster than prime gaps, then this points to an approach at answering Grimm's conjecture affirmatively.)
I'm not going to wait: I conjecture that if there are infinitely many exceptions (intervals where S does not provide a Grimm map), that Case I resolves a positive density of them and that old (not revised) case II handles almost all of the rest, with a finite number or zero-density of revised case II's needed and only 1 instance (which we've already seen) where case III is needed.
E. Can S be tweaked (as in the other question, where some stones can be delayed being placed until they land on $p^2$, or some multiple of $p$ close to and less than $p^2$) and if needed other cases added, to produce G, an algorithm and a different machine which gives Grimm maps for all prime gap intervals?
F. What other statisitics and easily proved results can be had to give light on the distribution of smooth numbers and injective divisor maps?
G. Can S be analyzed to provide information on the length of "extra-Grimm" intervals, where there are injective divisor maps even though these larger intervals may contain one or more primes?
H. Much as I like to consider S and its variations, another divisor map to consider is L(n), the largest prime factor of an integer n. Of course, this has its own problems in constructing Grimm maps, but the major one arises from consecutive smooth numbers (indeed, the first failure is 3=L(3*8)=L(3*9)). Is there a blend of L and S that can produce G?
While I want all the questions to be considered, it is enough if question A. is answered.
Bibliography:
Richard Guy, Unsolved Problems In Number Theory problem B32
Gerhard "Matchmaker, Make Me A Match" Paseman, 2016.08.22
