How do these primes jump?

Question

Update 2017.08.28: I am still looking for references. I have posted a request to https://cs.stackexchange.com/q/79971 which includes some literature references I found which are of interest but still miss the mark for this question. End Update.

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

I have several questions regarding the analysis, behaviour, and expression of a simple sieving algorithm which uses associative arrays. The pseudocode below assumes integer addition, string concatenation, checking that an index (key) exists in an array (so at the beginning, (n in c) is false for all n, but when c[m]=p is carried out, then (m in c) returns true), and sufficient memory. (Or set LIM to 100.)

for n = 2 to LIM
    p    = n
    if    (n in c)    p = c[n]
    m    = n + p
    while (m in c)    m = m + p
    c[m] = p
    t[p] = t[p] "," m

(Compare a similar algorithm which in part computes the list of distinct prime factors for each n, found here: https://mathoverflow.net/a/50691 .) When this loop is run, at the end c[m] contains a prime factor p of m for each composite number m at most LIM, as well as for some composite m greater than LIM. t contains for each p a comma-delimited string of indices m for which c[m] gets p. It is a nice exercise to show that (at the end of the loop body) p is a prime, that c has only composite indices m, that c[m] when defined is always a prime dividing m, and that t[p] encodes an increasing sequence of some multiples of p. When I simulate this by hand, I imagine the primes p jumping over occupied slots in c until they find an empty slot c[m] and land there.

Question 1: Does this sieve implementation (perhaps slightly modified) exist in the computer science or number theory literature?

I am aware of wheel sieving which is faster, but this algorithm is not too shabby, even if you have to write your own data structure to perform (n in c).

Question 2: What does t[2] look like? Calling the $j$th member $m_j$, how good an approximation can we get to $m_j$ in terms of $j$?

Here are the first few terms of t[2] and of t[3]:

4 8 12 16 24 30 32 40 50 64 78 90 104 108 128 140 156 176 192 208
6 9 15 18 27 36 48 54 63 72 81 96 105 126 144 162 180 189 210 231

I will make a different post with other questions related to this algorithm and variants. If you want to play with it, here is an (untested) version which saves memory by removing c[n] after it is used, and by not storing p values larger than LIM:

BEGIN{ LIM = 100; LIM2 = LIM*LIM

for ( n=1; LIM2 > n++; ) {
    if ((m=n) in c) { m += (p=c[n]);   delete c[n]
        while ( m in c )  m += p  }
    else  m += (p=n)
    if (p < LIM )  { c[m] = p;  t[p] = t[p] "," m  }
    }
for ( p=1; p < LIM; p++ )  if (p in t) print t[p]
}

Question 3: How much slower does t[2] grow ( as a function of LIM ) than the sequence above where all primes are "jumped"?

Gerhard "Is Awed By Elegant Simplicity" Paseman, 2016.07.01.

Answer 1

Just to confirm your list of $t[2]$ and extend it a bit, here is what those terms look like:

---

         

---

$t[2]=$ $$ 4,8,12,16,24,30,32,40,50,64,78,90,104,108,128,140,156,176,192,208,216,234,250,256,280,304,320,338,350,374,392,420,440,468,486,500,512,540,570,598,630,648,676,704,726,750,768,800,832,858,882,910,950,972,1008,1024,1056,1088,1122,1150,1176,1210,1248,1280,1296,1344,1372,1426,1458,1500,1536,1568,1584,1600,1632,1672,1694,1728,1760,1792,1824,1856,1904,1936,1976,2016 \;. $$

Answer 2

Here is some information on how the primes jump. It seems the trajectories are somewhat smooth. Skipping numbers seems to be a topic which is a tempting if not low-hanging fruit.

As a prime traverses through its multiples according to the algorithm, it will skip over some multiples because a different prime got there first. For a prime $p$ I define skip($p$) to be the smallest positive multiple of $p$ not in the trajectory of $p$. I will use aliases of $sk(p)$ or $sk$ when $p$ is understood. One can simulate the first few steps to note skip($2$) is $6$, skip($3$) is $12$, skip($5$) is $15$, and skip($7$) is $35$.

Tracking the value of skip($p$) for many primes $p$, I note that $p^2 \lt 3sk(p) \lt 39p^2/11$ for $11 \lt p \lt 4000$. How close can we get to proving such equalities for all primes $p$?

One approach is to show for a fixed integer $k$ which primes $p$ that have $kp$ in their trajectory also have $(k+1)p$ in that trajectory, or which $p$ jump from $k$ to $k+1$. For $k=1$, there are two simple proofs: a) note that $2$ jumps from $1$ to $2$, and note for an odd prime $p$ that there are more even numbers between $p$ and $2p$ than odd primes less than $p$, so there is an even number between $p$ and $2p$ to be part of the trajectory of $2$, giving $p$ a chance to jump to $2p$ before $2$ does, and b) between $p$ and $2p$ is a power of $2$, so $2$ must land somewhere above $p$ and less than or equal to that power of $2$, again leaving $2p$ available for odd $p$.

For $k=2$, jumping from $2$ to $3$ is straightforward if there is a power of $3$ between $2p$ and $3p$. When there isn't, one can use $3$-smooth numbers (numbers whose distinct prime factors are at most $3$) for sufficiently large $p$. In particular, if $r$ is the largest $3$-smooth number less than $2p$ and $r$ is a multiple of $6$, then $2p \lt 4r/3 \lt 3r/2 \lt 3p$ and so there is a place for both $2$ and $3$ to land strictly below $3p$. If $r$ is a power of $2$ at least $8$, then one can use $9r/8$ and $3r/2$ in a similar way, and if $r$ is a power of $3$ at least $27$ then one can use $32r/27$ and $4r/3$. So for all $p$ with $2p \gt 12$, we get a pair of places (which are $3$-smooth numbers) less than $3p$ for both $2$ and $3$ to land. This takes care of $p \gt 7$, while $p=3$ can be settled by hand, leaving $p=2$ and $5$ missing out on jumping from $2$ to $3$, which they do.

In general, jumping from $k$ to $k+1$ involves the set of distinct prime divisors of $k+1$, and one may have to throw in a few more small primes to pull the argument through. Namely, find a nice set $Q$ of primes such that $k+1$ is a $Q$-smooth number (all the prime divisors come from $Q$), and so that if $Q$ has $t$ distinct primes, then find those $p$ such that the interval $(kp, (k+1)p)$ contains at least $t$ $Q$-smooth numbers. Then when $kp$ is processed, all the primes in $Q$ are guaranteed a place to land above $kp$ and below $(k+1)p$, leaving the latter available for $p$.

A problem with this approach is that I don't know an estimate for $Q$-smooth numbers in an interval that has small enough error. A rough estimate, given that there are $t$ many primes $q$ in $Q$ , and involving logarithms to different prime bases $q$, is $$\big[\prod_{q \in Q} (1 + \lfloor\log_q((k+1)p)\rfloor) - \prod_{q \in Q} (1 + \lfloor\log_q(kp) \rfloor)\big]/t!, $$ but I think this is a bad approximation when $k$ and $p$ are close to the same size.

A different approach is to consider what primes would jump to a number between $kp$ and $(k+1)p$. Using the statistics above as a guide, this interval has labels from all the primes in the interval $(kp/2,(k+1)p/2)$, and in general from $(kp/i,(k+1)p/i)$ for $i$ up to some integer hopefully close to $k$. Again, I am unsure that the error in such an estimate is easy to control.

Suppose we are able to determine $G(k)$, a non-decreasing function so that for all $p \geq G(k)$ that $p$ jumps from $k$ to $k+1$. Then define $F(p)$ to be the largest $k$ such that $p \geq G(k)$, and we now have that $F(p)=k$ means the multiples $2p$ up to $(k+1)p$, or skip($p$) $\gt F(p)$. Now the goal is to show something like $G(k)=3k+1$.

In any case, we can give a rough description now of how the labels p are arranged in c. When $n$ is processed with label $p$ dividing $n$ (so c[n] has the value p), we have all the primes $q$ from $n/2$ up to $n$ have jumped to $2q$, and for many small $t$ each prime $q$ from $n/(t+1)$ up to $n/t$ has landed on $(t+1)q$, up to about $t \in O(\sqrt{n})$. This just leaves about $O(\sqrt{n})$ many primes whose location above $n$ is unknown, but are likely below $n + K{\sqrt{n}}^{1+\epsilon}$ for some given value of $\epsilon$ and some small value of $K$ depending only on $\epsilon$. This suggests that the trajectory for a prime grows irregularly but somewhat quadratically. (Since there are at most $O(n/\log(n))$ obstructions for a given prime, we should expect strictly subquadratic growth.) Also suggested is that if $n$ has label $p$ and $p$ is not the largest prime factor of $n$, then the largest prime factor of $n$ is not much bigger than $\sqrt{3n}$, which I suggest as a conjecture.

Additional question: does it make sense to define skip($n$) for composite $n$, and will that help in the trajectory analysis? (I can see the definition depending on the prime assigned to $n$ as well as depending on the set of distinct prime factors.)

Gerhard "More Answers Gives More Questions" Paseman, 2016.08.22.

Answer 3

I've made some headway on Question 3. It is related to my studies of Jacobsthal's function. Although a theory for general square free numbers $Q$ can be developed, I will take $Q=P_n$, the product of the first $n$ primes, for this post. Of course, $2$ can only make a jump of size at most $2n$, but it will rarely make a jump of that size for large $n$.

If I restrict the algorithm to primes dividing $Q$, the union of the trajectories are those numbers not coprime to $Q$, and as the system can be modeled as a finite state automaton, the trajectory of each prime will be periodic with a period related to a multiple of $Q$. More precisely, for a given prime $p$ dividing $Q$, one has that a positive number $m$ is in the trajectory if and only if $m+Q$ is in the trajectory. (Temporarily, I include $p$ in its own trajectory, contrary to the post above.)

To see this, note that $\gcd(Q,Q+p)=p$ for every prime divisor $p$ (and also every divisor) of $Q$. Thus, modulo $Q$, there is only one way to arrange the $n$ primes at the start ( the pattern of primes assigned to the indices in $[mQ+2, mQ+p_n]$ is independent of $m$), and thus the pattern of primes assigned to c repeats modulo $Q$ as well.

It is tempting to conjecture that c[$m$]$=$c[$Q-m$] for positive $m$ less than and not coprime to $Q$, but when $Q=30$ one has c[$12$]$=2$ and c[$18$]$=3$ (and similar examples exist for some larger $Q$). It is also tempting to conjecture that each prime $p$ does slightly less than $Q/p$ jumps in a range of length $Q$, with the difference related to inclusion-exclusion. Simulations show much smaller numbers than this prediction. Note that the longest jump is bounded above by the sum of the $n$ primes, and is likely to be much less. For small values of $n$ $(n\leq 9)$ I see the largest jump as less than $3p_n$. I would not be surprised if the largest jump were of the same order as $g(Q)$, the Jacobsthal function applied to $Q$, which would be conjectured at or near $p_n(\log p_n)^2$ but I would settle for strictly less than $O(n^2)$. In any case, it is apparent that the set of primes stay in a rather tight cluster not much larger than the largest prime as they jump according to the restricted version of the algorithm. How tight is hopefully less hard than various open questions regarding the distribution of prime numbers.

Gerhard "More Jumping Means More Excitement" Paseman, 2016.09.11.

Answer 4

I've decided to bust through my writer's block and post a partial result.

Of course when a prime $p$ jumps, it skims over multiples of $p$ occupied by other primes, and one question is how far a prime can jump from its location at $n$. The brief answer is that $p \cdot f_0(n/p)$ is a strict upper bound, and I am trying to tighten that to $f_0(n/p)$, maybe multiplied by a fractional power of $p$. Here $f_0(n)$ relates to the number $w$ of distinct prime factors of the product of integers in the interval $[n+1,n+k]$, and is the largest integer $k$ for which $w\geq k$. $f_0()$ (and also $f_2()$ which relates to Grimm's conjecture in another post) comes from a 1971 paper of Erdos and Selfridge.

The proof of this upper bound is clear: for each of the multiples of $p$ above $n$ which have a different prime divisor occupying that multiple, we run out of (a non repetitive pattern of) possible prime divisors when we hit $f_0(n/p)$ many such multiples. (Indeed we run out before encountering $1+f_2(n/p)$ many such multiples.) However, some of the primes $q$ involved may actually not be on a multiple of $p$, but occur on a smaller multiple of $q$ above $n$, and it is reasonable (but not well supported) to assume that about $1/p$ of these primes $q$ reside on multiples of $p$.

The nice thing is that the 1971 paper has a proof that $f_0(n)$ is $O(\sqrt{n/\log n})$, and $f_2(n)$ seems not much smaller. I hope to make a proof with explicit constants, and add it to a write-up. I also hope to get an inspiring idea for a lower bound on the length of a jump of $p$ from a large multiple of $p$. However, I find it interesting already that a trajectory of any prime is eventually smoother than somewhat smooth, and hope to use this in further analysis. Also, intriguing is how small the ratio skip(p)/p gets as p gets large.

Gerhard "Going For Block Busting Results" Paseman, 2017.07.05.