fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
--fib x = fibs !! x
fibs2 = helpFib 0 1
helpFib x y = x : helpFib y (x + y)
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)
fibs3 = map fib [0..]
fibs4 = [fib x | x <- [0..]]
fibs5 = map fst $ iterate (\(x,y) -> (y,x+y)) (0,1)
--merge [] ys = ys
--merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
merge xs ys = xs ++ ys
primes :: [Integer]
primes = sieve [2..]
sieve :: [Integer] -> [Integer]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]
--primepowers 0 = []
--primepowers n = merge [p^n | p <- primes] (primepowers (n-1))
primepowers n = foldl merge [] [ map (^i) primes | i <- [1..n] ]
intersect :: (Ord t) => [t] -> [t] -> [t]
intersect (x:xs) (y:ys)
| x == y = x : intersect xs ys
| x < y = intersect xs (y:ys)
| otherwise = intersect (x:xs) ys
intersect _ _ = []
intersectAll :: (Ord t) => [[t]] -> [t]
--intersectAll (x:y:xs) = intersect x (intersectAll (y:xs))
--intersectAll [x] = x
--intersectAll [] = []
--intersectAll (x:xs) = foldr intersect x xs
intersectAll xs = foldr1 intersect xs
--intersectAll xs = foldr intersect [1..] xs
--commonMultiples = [105,210..]
-- where x = intersectAll [[1..]]
--commonMultiples a b c = intersectAll [map (*a) [1..], map (*b) [1..], map (*c) [1..]]
--commonMultiples a b c = intersectAll [[a,2*a..], [b,2*b..], [c,2*c..]]
commonMultiples a b c = intersectAll [ [n*k | k <- [1..]] | n <- [a,b,c] ]
random :: Integer
random = 3
rand :: [Integer]
--rand = 32 : map (\x -> (a * x + b) `mod` m) rand
-- where m = 2 ^ 16
-- a = 25173
-- b = 13849
rand = iterate (\x -> (a * x + b) `mod` m) x0
where m = 2 ^ 16
a = 25173
b = 13849
x0 = 32
toCoin :: [Integer] -> [Bool]
--toCoin xs = map even xs
toCoin xs = map (> 2^15) xs
neumann :: [Bool] -> [Bool]
neumann (x:y:xs)
| x == y = neumann xs
| otherwise = x : neumann xs
bias :: [Bool] -> [Bool]
bias (x:y:xs) = (x && y) : bias xs
-- length $ filter id $ take 1000 $ neumann $ bias $ bias $ bias $ toCoin rand