I'm writing practice code, and I just did types oriented around generating true/false primality results (starting from 2, of course). I did two types based on the Sieve of Eratosthenes. On its Wikipedia page, I saw links to several other prime sieves. Now I'm wanting to try out the Sieve of Sundaram. I see the basic way to make the program, but I'm wondering how to generate the i/j forbidden indices. Looking at the first few entries, in i then j order:
- (1, 1) → 4
- (1, 2) → 7
- (2, 2) → 12
- (1, 3) → 10
- (2, 3) → 17
- (3, 3) → 24
- (1, 4) → 13
I can't just loop on j then i, because that causes backtracking (for example: 12 to 10 and 24 to 13), and I'm going for streaming generation instead of a fixed n. Right now, I'm thinking of keeping multiple j rows and extracting the smallest value each round, dumping a row once I exhaust it, and creating a new one every three rounds (at 4, 7, 10, 13, 16, etc.)
Then my research came across this article from Plus Magazine. It has a doubly-infinite array of arithmetic progressions that is the i/j chart. The format looks like the proof of rationals being countable grid, so I'm wondering if there's a snaking path through the i/j chart that will reach each number in order (eventually).
A simple snaking like the rational chart probably won't work, looking at the 10/13/16/17 intersections on the top and left. I don't mind a snaking that hits equal or lesser values than the latest, as long as the next greater value is the immediately greater value.