algorithm - Is it possible to generate the wheel lazily? -

on the genuine sieve of erastosthenes paper, author uses wheel of finite size skip checking multiples of first n primes on sieve construction. example, in order avoid checking multiples of 2, 3, can begin @ 5, , alternately add 2 , 4. wheel 2 below:

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

her wheel generated on startup of sieving process. presents tradeoff, since larger wheels require more memory. find underlying mechanism behind wheel generation interesting itself, though. given repetitive nature, wonder if possible create "infinite wheel" which, sieve, presented stream? stream be, guess, limit of sequence of lists [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... - , work implementation of primes itself.

as bakuriu says, wheel sequence has no limit. there no such thing "infinite wheel", i'll try demonstrate why.

if know first prime numbers p_1,...,p_n, need search next ones among numbers coprime them :

iscoprime :: [int] -> int -> bool iscoprime ps x = (\p -> x `mod` p /= 0) ps  

the set coprime(p_1,...,p_n) (p_1...p_n)-periodic (x inside if , if x + p_1...p_n inside it), call wheel.

you're asking limit of coprime set, take more , more prime numbers p_i. however, number in coprime(p_1,...,p_n) below p_n 1. prove this, observe prime factor of such number 1 of p_i.

so number of primes tends infinity, coprime(p_1,...,p_n) leaves huge empty hole between 1 , p_n. limit can think of therefore empty set : there no infinite wheel.