Is it possible to generate the wheel lazily?

Question

On the The Genuine Sieve of Erastosthenes paper, the author uses a wheel of finite size to skip checking multiples of the first N primes on the sieve construction. For example, in order to avoid checking multiples of 2, 3, you can begin at 5, and alternately add 2 and 4. This is the wheel 2 below:

-- wheel 0 = ([2],[1])
-- wheel 1 = ([3,2],[2])
-- wheel 2 = ([5,3,2],[2,4]) -- "start at 5, add 2, 4, 2, 4..."
-- wheel 3 = ([7,5,3,2],[4,2,4,2,4,6,2,6])

Her wheel is fully generated on the startup of the sieving process. This presents a tradeoff, since larger wheels require more memory. I find the underlying mechanism behind the wheel generation interesting by itself, though. Given its clearly repetitive nature, I wonder if it would be possible to create an "infinite wheel" which, like the sieve, presented itself as a stream? This stream would be, I guess, the limit of the sequence of lists [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... - and probably work as an implementation of primes itself.

Answer 1

As Bakuriu says, the wheel sequence has no limit. There is no such thing as the "infinite wheel", I'll try to demonstrate why.

If we know the first prime numbers p_1,...,p_n, we only need to search the next ones among the numbers that are coprime to them :

isCoprime :: [Int] -> Int -> Bool
isCoprime ps x = all (\p -> x `mod` p /= 0) ps 

The set Coprime(p_1,...,p_n) is (p_1...p_n)-periodic (x is inside it if and only if x + p_1...p_n is inside it), so we call it a wheel.

You're asking for the limit of this Coprime set, as we take more and more prime numbers p_i. However, the only number in Coprime(p_1,...,p_n) below p_n is 1. To prove this, observe that a prime factor of such a number would be one of the p_i.

So as the number of primes tends to infinity, Coprime(p_1,...,p_n) leaves a huge empty hole between 1 and p_n. The only limit you can think of is therefore the empty set : there is no infinite wheel.