Is it possible to generate a wheel lazily?

Question

In The Original Sieve of Erastosthenes, the author uses a finite-size wheel to skip the control multiples of the first N primes on the trellis. For example, to avoid checking for multiples of 2, 3 , you can start at 5 and alternately add 2 and 4. This is 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]) 

Its wheel is fully generated at the start of the screening process. This is a compromise since larger wheels require more memory. However, I believe that the underlying wheel generation mechanism is interesting in itself. Given its clearly repeating nature, I ask myself, is it possible to create an “endless wheel” that, like a sieve, presented itself as a stream? This stream would, I think, be the limit of the sequence of lists [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... - and probably worked as an implementation of primes itself.

Answer 1

According to Bakuriu, the sequence of wheels has no limit. There is no such thing as an “endless wheel,” I will try to show why.

If we know the first primes p_1, ..., p_n, we need to look only for the following numbers among the numbers that are coprime:

 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 inside it if and only if x + p_1 ... p_n is inside it), therefore we call it a wheel.

You are requesting a limit for this Coprime set as we accept more and more p_i primes. However, the only number in Coprime (p_1, ..., p_n) below p_n is 1. To prove this, we note that a prime factor of such a number will be one of p_i.

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 that you can think of is thus an empty set: there is no infinite circle.