---------------------------------------------------------------------
--
-- sieves.hs -- Haskell functions for sieves.
--
-- Coded by Antti Karttunen, May 2005
--
-- See http://www.haskell.org/
--     http://www.iki.fi/~kartturi/
--
-- Load as :load karttu/sieves.hs
--
--
---------------------------------------------------------------------


module Sieves() where

drop_multiples_of  ::  Integer -> [Integer] -> [Integer]
drop_multiples_of n xw = drop_multiples_aux n n xw

drop_multiples_aux ::  Integer -> Integer -> [Integer] -> [Integer]
drop_multiples_aux n i xw@(x:xs)
                   | (x == i)   = (drop_multiples_aux n (i+n) xs)
                   | (x < i)    = (x : drop_multiples_aux n i xs)
                   | otherwise  = (drop_multiples_aux n (i+n) xw)




drop_by_first :: [Integer] -> [Integer]
drop_by_first a = drop_every_nth_aux (head a) a 0


-- One-based:
drop_by_nth   :: Int -> [Integer] -> [Integer]
drop_by_nth n a = drop_every_nth_aux (nthelem1 n a) a 1


drop_every_nth :: Integer -> [Integer] -> [Integer]
drop_every_nth n a = drop_every_nth_aux n a 1

drop_every_nth_aux ::  Integer -> [Integer] -> Integer -> [Integer]
drop_every_nth_aux n (x:xs) i
                   | (n == i)   = (drop_every_nth_aux n xs 1)
                   | otherwise  = (x : drop_every_nth_aux n xs (i+1))



take_by_first :: [Integer] -> [Integer]
take_by_first a = take_every_nth_aux (head a) a 0

take_every_nth_aux ::  Integer -> [Integer] -> Integer -> [Integer]
take_every_nth_aux n (x:xs) i
                   | (0 == i)   = (x : take_every_nth_aux n xs (n-1))
                   | otherwise  = (take_every_nth_aux n xs (i-1))



seq_diff :: [Integer] -> [Integer] -> [Integer]
seq_diff xw@(x:xs) yw@(y:ys)
          | (x == y)  = seq_diff xs ys
          | (x < y)   = (x : seq_diff xs yw)
          | otherwise = seq_diff xw ys



fib :: [Integer]
fib@(_:tfib) = 1 : 1 : [ a+b | (a,b) <- zip fib tfib ]


-- Primes themselves:
crowsA000040 :: [[Integer]]
crowsA000040 = ([2..] : map (\s -> drop_multiples_of (head s) s) crowsA000040)
seqA000040 :: [Integer]
seqA000040 = [head s | s <- crowsA000040]


nthelem :: Int -> [a] -> a
nthelem n lista = (head (drop n lista))

nthelem1 :: Int -> [a] -> a
nthelem1 n lista = nthelem (n-1) lista


-- Lucky numbers:
-- A000959 = 1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79,87,93,99,

-- Delete every 2nd number (of naturals),
--   leaving 1 3 5 7 ...;
-- the 2nd number remaining is 3, so delete every 3rd number,
--   leaving 1 3 7 9 13 15 ...;
-- now delete every 7th number,
--   leaving 1 3 7 9 13 ...;
-- now delete every 9th number; etc.

crowsA000959 :: [[Integer]]
crowsA000959 = ([(2*a)+1 | a <- [0..]] : [(drop_by_nth (n+2) (nthelem n crowsA000959)) | n <- [0..]])

seqA000959 :: [Integer]
seqA000959 = [(nthelem n (nthelem n crowsA000959)) | n <- [0..]]



crowsA003309 :: [[Integer]]
crowsA003309 = ([2..] : map drop_by_first crowsA003309)

-- Tee se hankalasti:
crowsA003309v2 :: [[Integer]]
crowsA003309v2 = ([2..] : map (\s -> seq_diff s (take_by_first s)) crowsA003309)


crowA003309 :: Int -> [Integer]
crowA003309 n = head (drop (n-1) crowsA003309)

-- crowA003309 1 = 2 : [a+1 | a <- (crowA003309 0)]
-- crowA003309 n = seq_diff (crowA003309 (n-1)) (take_by_first (crowA003309 (n-1)))


-- Ludic numbers:
-- A003309 = 2,3,5,7,11,13,17,23,25,29,37,41,43,47,53,61,67,71,77,83,89,91,97,

seqA003309 :: [Integer]
seqA003309 = [head s | s <- crowsA003309]


-- Note:
-- take 20 (seq_diff seqA003309 seqA000040)
-- [25,77,91,115,119,121,143,161,175,209,221,235,247,265,287,301,329,341,361,377]