FORMULAS

Next

The initial multiple-of-3 exclusions are done by adding either 2 or 4 alternately to the candidate return value

value += (increment ^= 6)     # increment=2 or 4 alternately

Further multiple-of-N exclusions are applied by a table of remaining counts, starting from multiple-of-7. For example when up to considering value=55,

# about to consider value=55
multiple     7   9   13   15  ...
remaining    3   2   11    1  ...

This means multiple-of-7 exclusion is 3 values away. The candidate value=55 is passed and the counter decreases to 2. Likewise multiple-of-9 and multiple-of-13 decrement. But the multiple-of-15 is down to 1 left, which means value=55 is excluded and the counter resets to 15 again.

# after value=55 excluded
multiple     7   9   13   15   21
remaining    2   1   10   15    7

As an optimization, it's not necessary to keep the counters of all previously generated values, only up to the first which not yet excluded anything. In this example the full set of counters up to the value=51 previously generated would have been

# after value=55 excluded, full set of counters
multiple     7   9   13   15   21   25  31  33  37  43  49  51
remaining    2   1   10   15    7   11  17  19  23  29  35  37

Notice that from multiple-of-21 onwards the remaining counts are always increasing. That's because for example a multiple-of-25 will not exclude anything until multiple-of-21 does.

At value=55 the multiple-of-15 reached zero for the first time. So at that point multiple-of-21 is appended. Its initial value is 21-(15-1) because the multiple-of-15 has passed 15-1=14 previous values, so they are subtracted from the initial multiple-of-21 count. In general a new counter is appended whenever the end-most counter reaches zero.

When appending a new counter there's no need to save all the values generated to know what multiple it should be, instead maintain a sub-table of multiples and remainders to generate the sequence values at that point. A single sub-level like this is enough because within that sub-level the top-level "multiples" list is long enough to take the new multiples counts appended in the sub-level.

After generating i many values the array length satisfies ith(len)=i, ie. value_to_ith(i). As noted above values increase like the primes x/log(x) and the array is roughly

len = i/log(i) * 1.04       after generating i many values

In practice means roughly 1/6 to 1/8 of what the full set of values would have been. The smaller array is much faster to run through and decrement when considering a candidate return value.