A Question About Erasthmus' Sieve

Students of Mathematics are familiar with Erasthmus' Sieve.

2    x

3        x            

4     x

5            x

6    x    x

7

8    x

9        x

10     x        x

11

12    x    x

13

14    x

15        x    x

16    x

17

18    x    x

19

20    x        x

21        x

22    x

23

First, we strike all multiples of 2 up to the square root (5.) Then all multiples of 3, then all multiples of 5, etc.


I wrote a digital implementation of the Sieve, and used the index creatively, to keep track of the multiples. To "strike" an integer, I set the value of the relevant array entry to 2.

In writing the code, I soon observed that as I asked the machine not to look at 2's, the first prime was an obstacle. To overcome this, I wrote a separate loop for 2's, and then began from three, only using the "strike array entry" function only on non-2 array entries.

This was very satisfactory, and I was able to develop a list of all primes < 2 ** 29, in 287 seconds on my overclocked Core i5 9600 computer.

In bragging to a friend, I attempted to reduce the size of my code, and mistakenly took out the loop that struck 2's. This should have resulted in chaos, but the algorithm picked up 4 as a non-2, and struck every fourth entry. This removed all multiples of 2 that were not multiples of another prime, and I accidentally improved the efficiency of my code - not only did it not do a separate 2 loop, but when it ran the required loop, it took steps by 4, reducing the number of iterations by half.

I didn't even notice, at first, because on the output loop, I output 2 literal, and began at 3, only outputting odd-indexed array entries, so the 4 was never officially output as a "prime."

But I was only a fool for a day. I soon inspected the entire list, (on a small number {101},) observed the 4, and was able to account for it.

This reduced the runtime to develop a list of primes < 2 ** 29, down to 204 seconds.

Troubled by memory constraints, I proceeded with a bit of a mad-cap experiment. I built a list as follows, using only odd integers, with grim determination to use integer division and off-sets to account for the disagreement between indexing and array contents. I began working it out on paper, with the following results:

Index | Array contents:

00      | 3    |    x    |

01      | 5    |          |    x    |

02      | 7    |          |          |    x    |

03      | 9    |    x    |

04      | 11    |

05      | 13    |

06      | 15    |    x    |    x    |

07      | 17    |

08      | 19    |

09      | 21    |    x    |          |    x    |

10      | 23    |

11      | 25    |          |    x    |

12      | 27    |     x    |

13      | 29    |

14      | 31    |

15      | 33    |    x    |

16      | 35    |          |    x    |    x    |

17      | 37    |

18      | 39    |    x    |

19      | 41    |

20      | 43    |

21      | 45    |    x    |    x    |

22      | 47    |

23      | 49    |          |    x    |

24      | 51    |    x    |

25      | 53    |

26      | 55    |          |    x    |

27      | 57    |    x    |

28      | 59    |

29      | 61    |

30      | 63    |    x    |         |    x    |

31      | 65    |          |    x    |

32      | 67    |

33      | 69    |    x    |

34      | 71    |

35      | 73    |

36      | 75    |    x    |    x    |

37      | 77    |          |          |    x    |

38      | 79    |

39      | 81    |    x    |

40      | 83    |

41      | 85    |          |    x    |

42      | 87    |    x    |

43      | 89    |

44      | 91    |          |          |    x    |

45      | 93    |    x    |

46      | 95    |          |    x    |

47      | 97    |

48      | 99    |    x    |

49     | 101   |

To my great surprise, the contents of the array were exactly multiples of the original offset. That is to say, I was blindly accepting the array index value as a variable, and incrementing by the contents of the array, and the  resulting index content was a multiple of the integer!

Is this still Erasthmus' Sieve?

I had great success with the python3 program, and proceeded to develop a list of all primes < 2 ** 30, using 21.8 GB of RAM (within my 32GB limit,) and requiring a runtime of 361 seconds! 

Comments

Post a Comment

Popular posts from this blog

A Cryptographically Sound Vigenere.

In middle school, I learned a version of the Vigenere Cipher from a paperback by a German author. It was a 25 x 25 grid, with the letters of the alphabet across, up to "y," and dropping the "z," for column headings and rows. The grid was constructed by writing the rows as the entire 26 letter alphabet, beginning with the letter "a," and pushing the columns over one column to the right, every row. The next row began with , "z," and the rest of the rows followed suit. I recall that there was supposed to be a way to implement a Salt in the book, but I am unable to duplicate it. I learned of lossless Vigenere from Simon Singh's book, "The Code Book." My early experiment was to double encrypt with various passwords in an attempt to increase the Unicity distance, although I did not know the term. By experimentation, I found that the Unicity distance was equal to the product of the unique prime factors of the password lengths. This is triv
Read more

Notice of corrupted results: Vigenere may yet be found to be a "group."

Retraction: It is with regret that I do not delete the previous post. I am an individual, not an organization, and I failed to adequately double-check my results, but I am leaving the post to maintain some accountability. I am able to definitively say that the script for 2chars_from_file.py DOES NOT yield an exhaustive list. It develops the ciphertext for all 2 Char combinations of the FIRST 10, three character ciphertexts. This is not due to a logic error, but rather there is a virus that corrupts the indentation of the two write statements.  This may be verified by downloading the relevant code, and examining it, and running it if needed, against the relevant datafile. It is difficult to be exhaustively correct about ALL of the scripts. This calls ALL of my results in question, with regard to the qualification of a mathematical group. If Vigenere IS a group, the resulting substitution is still valid, but there exist 6 Char passwords that will accomplish the same encryption in ONE STE
Read more