Editing Prime numbers (section)

=== Wheeled list representation ===

The situation can be somewhat improved using a different list representation, for generating lists not from a last element and an increment, but rather a last span and an increment, which entails a set of helpful equivalences:
<haskell>
{- fromElt (x,i) = x : fromElt (x + i,i)
                       === iterate  (+ i) x
     [n..]             === fromElt  (n,1) 
                       === fromSpan ([n],1) 
     [n,n+2..]         === fromElt  (n,2)    
                       === fromSpan ([n,n+2],4)     -}

fromSpan (xs,i)  = xs ++ fromSpan (map (+ i) xs,i)

{-                   === concat $ iterate (map (+ i)) xs
   fromSpan (p:xt,i) === p : fromSpan (xt ++ [p + i], i)  
   fromSpan (xs,i) `minus` fromSpan (ys,i) 
                     === fromSpan (xs `minus` ys, i)  
   map (p*) (fromSpan (xs,i)) 
                     === fromSpan (map (p*) xs, p*i)
   fromSpan (xs,i)   === forall (p > 0).
     fromSpan (concat $ take p $ iterate (map (+ i)) xs, p*i) -}

spanSpecs = iterate eulerStep ([2],1)
eulerStep (xs@(p:_), i) = 
       ( (tail . concat . take p . iterate (map (+ i))) xs
          `minus` map (p*) xs, p*i )

{- > mapM_ print $ take 4 spanSpecs 
     ([2],1)
     ([3],2)
     ([5,7],6)
     ([7,11,13,17,19,23,29,31],30)  -}
</haskell>

Generating a list from a span specification is like rolling a ''[[#Prime_Wheels|wheel]]'' as its pattern gets repeated over and over again. For each span specification <code>w@((p:_),_)</code> produced by <code>eulerStep</code>, the numbers in <code>(fromSpan w)</code> up to <math>{p^2}</math> are all primes too, so that

<haskell>
eulerPrimesTo m = if m > 1 then go ([2],1) else []
    where
      go w@((p:_), _) 
         | m < p*p = takeWhile (<= m) (fromSpan w)
         | True    = p : go (eulerStep w)
</haskell>

This runs at about <math>O(n^{1.5..1.8})</math> complexity, for <code>n</code> primes produced, and also suffers from a severe space leak problem (IOW its memory usage is also very high).