- #1
- 7,861
- 1,598
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 [itex] \{a_k\}[/itex] where[itex]k[/itex] 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,
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,