[Math] How do these primes jump

ds.dynamical-systemsnt.number-theoryprime numbers

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.

Best Answer

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

          t[2]
$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 \;. $$

Related Question