Dealing with unwanted sharing leads to discovery of wheels of coprimes

tme.hs

{-# OPTIONS_GHC -O2 -fno-cse #-}

module Main where

primesTME = 2 : gaps 3 (joinT [[p*p, p*p+2*p..] | p <- primes']) 
  where
    primes' = 3 : gaps 5 (joinT [[p*p, p*p+2*p..] | p <- primes'])   
 
joinT ((x:xs):t) = x : union xs (joinT (pairs t))  
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t 
gaps k s@(x:xs) | k<x  = k:gaps (k+2) s    -- equivalent to
                | True =   gaps (k+2) xs   --  [k,k+2..]`minus`s, when k<=head s

union (x:xs) (y:ys) = case (compare x y) of 
           LT -> x : union  xs  (y:ys)
           EQ -> x : union  xs     ys 
           GT -> y : union (x:xs)  ys

{-
primes' = 3 : gaps 5 (joinT                [[p*p, p*p+2*p..] | p <- primes']) 
 = (3 :) . gaps 5 . jointT $    [9,15..] : [[p*p, p*p+2*p..] | p <- tail primes']
 = ([3,5,7]++) . gaps 9 . (9:) $ union [15,21..] 
                            (joinT $ pairs [[p*p, p*p+2*p..] | p <- tail primes'])
 = ([3,5,7]++) . gaps 11 . union [15,21..] 
                         . joinT . pairs $ [[p*p, p*p+2*p..] | p <- tail primes']
 = ([3,5,7]++) . gapswx w6 11 
                         . joinT . pairs $ [[p*p, p*p+2*p..] | p <- tail primes']
 = ([3,5,7]++) . gapswx w6 11 . joinT . pairs $ 
                                  [map (*p) $ scanl (+) p w2 | p <- tail primes']
 = ([3,5,7]++) . gapsw w6 11 . joinT . pairs $ 
                             [map (*p) $ scanl (+) p $ w6p p | p <- tail primes']
-}

w2 = 2:w2

-- 5 7 11 13 15 17 19 21 23 25 27 29 31 33 35
--           15       21       27       33        39    45    51    57    63   69   75
-- 5 7 11 13    17 19    23 25    29 31    35  37  41  43 47 49 53 55 59 61            -- xs ***
--  2 4  2    4   2    4   2    4   2    4    2

w6 = 2:4:w6

gapswx (w:ws) k s@(x:xs)          -- gapswx w2 == gaps
  | k<x  = k:gapswx ws (k+w) s    
  | k>x  =   gapswx(w:ws) k  xs   -- eXtra input out of sync: (xs `minus` (45:_))      -- ***
  | True =   gapswx ws (k+w) xs  

w6p p = if rem p 6 == 5 then w6 else tail w6 

gapsw (w:ws) k s@(x:xs)          -- gapsw w2 == gaps  -- on sync'ed input --
  | k<x  = k:gapsw ws (k+w) s    
  | True =   gapsw ws (k+w) xs   

-------------------------------------------------------------------
primesTME_w6 = ([2,3]++) . gapsw w6 5 . joinT . pairs $
                 [scanl (\a x->a+x*p) (p*p) $ w6p p | p <- primes']
  where
    primes' = (5:) . gapsw (tail w6) 7 . joinT $    
                    [map (p*) $ scanl (+) p $ w6p p | p <- primes']
-------------------------------------------------------------------
-------------------------------------------------------------------
primesTME_w2 = 2 : gaps 3 (joinT [[p*p, p*p+2*p..] | p <- primes']) 
  where
    primes' = 3 : gaps 5 (joinT 
                        [map (p*) $ scanl (+) p w2 | p <- primes'])
-------------------------------------------------------------------