Pattern to indexes of deletions in a seive.

[Stephen Tashi]

One way to think about the seive of Eratosthenes is to imagine that after each pass, the non-deleted numbers are defined to be a sequence \{a_k\} wherek indexes the kth non-deleted number instead of a number equal to k.

As we perform the next pass and delete multiples of the next prime, is there a simple pattern to the indexes of numbers that are deleted?

In particular, is there a periodic pattern to the jumps in these indexes?

An inconclusive example:
I used a C program to compute the results for a few passes over the natural numbers less than 2000. In the output, the "Deltas" refer to the jumps between the indexes of a deleted number and the next deleted number.



---------------
Striking multiples of p == 2
001 (0002), 003 (0004), 005 (0006), 007 (0008), 009 (0010), 011 (0012), 013 (0014), 015 (0016),
<snip>
Deltas:
2,2,2,2,2,2,2,2,
<snip>
---------------
Striking multiples of p == 3
001 (0003), 004 (0009), 007 (0015), 010 (0021), 013 (0027), 016 (0033), 019 (0039), 022 (0045),
<snip>
Deltas:
3,3,3,3,3,3,3,3,
<snip>
---------------
Striking multiples of p == 5
001 (0005), 008 (0025), 011 (0035), 018 (0055), 021 (0065), 028 (0085), 031 (0095), 038 (0115),
041 (0125), 048 (0145), 051 (0155), 058 (0175), 061 (0185), 068 (0205), 071 (0215), 078 (0235),
<snip>
Deltas:
7,3,7,3,7,3,7,3,
7,3,7,3,7,3,7,3,
<snip>
---------------
Striking multiples of p == 7
001 (0007), 013 (0049), 020 (0077), 024 (0091), 031 (0119), 035 (0133), 042 (0161), 054 (0203),
057 (0217), 069 (0259), 076 (0287), 080 (0301), 087 (0329), 091 (0343), 098 (0371), 110 (0413),
<snip>
Deltas:
12,7,4,7,4,7,12,3,
12,7,4,7,4,7,12,3,
<snip>
---------------
Striking multiples of p == 11
001 (0011), 027 (0121), 032 (0143), 042 (0187), 047 (0209), 058 (0253), 073 (0319), 077 (0341),
093 (0407), 103 (0451), 108 (0473), 117 (0517), 132 (0583), 148 (0649), 153 (0671), 168 (0737),
178 (0781), 183 (0803), 198 (0869), 209 (0913), 223 (0979), 243 (1067), 254 (1111), 259 (1133),
268 (1177), 273 (1199), 284 (1243), 304 (1331), 318 (1397), 329 (1441), 344 (1507), 349 (1529),
359 (1573), 374 (1639), 379 (1661), 395 (1727), 410 (1793), 419 (1837), 424 (1859), 434 (1903),
450 (1969), 454 (1991),
Deltas:
26,5,10,5,11,15,4,16,
10,5,9,15,16,5,15,10,
5,15,11,14,20,11,5,9,
5,11,20,14,11,15,5,10,
15,5,16,15,9,5,10,16,
4,
---------------
Striking multiples of p == 13
001 (0013), 035 (0169), 044 (0221), 051 (0247), 062 (0299), 077 (0377), 084 (0403), 099 (0481),
110 (0533), 115 (0559), 126 (0611), 142 (0689), 158 (0767), 163 (0793), 180 (0871), 191 (0923),
197 (0949), 213 (1027), 224 (1079), 240 (1157), 261 (1261), 273 (1313), 278 (1339), 289 (1391),
294 (1417), 305 (1469), 343 (1651), 354 (1703), 370 (1781), 375 (1807), 403 (1937), 409 (1963),
Deltas:
34,9,7,11,15,7,15,11,
5,11,16,16,5,17,11,6,
16,11,16,21,12,5,11,5,
11,38,11,16,5,28,6
---------------
Striking multiples of p == 17
001 (0017), 056 (0289), 062 (0323), 075 (0391), 094 (0493), 100 (0527), 119 (0629), 132 (0697),
139 (0731), 151 (0799), 172 (0901), 190 (1003), 198 (1037), 217 (1139), 229 (1207), 237 (1241),
256 (1343), 269 (1411), 289 (1513), 316 (1649), 329 (1717), 336 (1751), 348 (1819), 355 (1853),
369 (1921),
Deltas:
55,6,13,19,6,19,13,7,
12,21,18,8,19,12,8,19,
13,20,27,13,7,12,7,14,

[baric]

I thought there might have been a non-predictive pattern but it fell apart at 11.

Because the primes are a result of a negating process (a sieve), my gut feeling has always been that there's not going to be a general predictive algorithm for the primality of any particular integer.

[epsi00]

I spent a lot of time trying to find a pattern of deletion like you call it in my sieve here

http://www.physicsforums.com/showthread.php?t=486150

but I was never able to find a general pattern of the indexing of either composite numbers or that of primes. However, it does not mean it does not exist. I found many patterns related to this problem and I will be posting my finding here sometime in the next few weeks.