euler.hs

module Main where

import Data.List
import Data.Array
import Data.Char

s 0 = 0
s x = x `mod` 10 + s (x `div` 10)

b2r 0 = "0"
b2r 1 = "1"
b2r x = (head $ show $ x `mod` 2) : b2r (x `div` 2)

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
p25 = [x | (x, y) <- zip [0..] fibs, (length $ show y) == 1000]

divisors n = [x | x <- [1 .. n `div` 2], n `mod` x == 0]
divsum = sum . divisors
divsumarr = array (1, 10000) $ zip [1..10000] (map divsum [1..10000])
amic n = [x:[y] | x <- [1 .. n - 1], y <- [x + 1 .. n], divsumarr ! x == y && divsumarr ! y == x]
p21 n = sum $ nub $ concat $ amic n

p8 (x1:x2:x3:x4:x5:xs) = product (map (subtract 48.ord) [x1, x2, x3, x4, x5]) : (p8 ([x2, x3, x4, x5] ++ xs))
p8 _ = []

triang = map (\x -> x * (x + 1) `div` 2) [1..]

p12 = filter (\x -> fst x >= 500) $ zip (map length (map divisors triang)) triang

merge xs@(x:xt) ys@(y:yt) = case compare x y of
    LT -> x : (merge xt ys)
    EQ -> x : (merge xt yt)
    GT -> y : (merge xs yt)
    
diff  xs@(x:xt) ys@(y:yt) = case compare x y of
    LT -> x : (diff xt ys)
    EQ -> diff xt yt
    GT -> diff xs yt
 
primes    = [2,3,5] ++ (diff [7,9..] nonprimes) 
nonprimes = foldr1 f . map g $ tail primes
    where f (x:xt) ys = x : (merge xt ys)
          g p = [ n*p | n <- [p,p+2..]]

fact 1 _ = []
--fact n s = let f = head $ filter (\x -> n `mod` x == 0) primes in f : fact (n `div` f) f
--ndiv n = product $ map (\x -> length x + 1) $ group $ fact n 2
--fdiv n = head $ filter (\x -> n `mod` x == 0) primes

--p187' n = if fd == 1 || r == 1 then False else fd * sd == n where
--	fd = fdiv n
--	r = n `div` fd
--	sd = fdiv r

p187 n = length div == 2 && n == product div
	where div = take 2 $ fact n 2

oisect _ [] = []
oisect [] _ = []
oisect (x:xs) (y:ys) =
  if x == y 
    then x : oisect xs ys
    else 
      if x < y then oisect xs (y:ys)
               else oisect (x:xs) ys

pan n = 9 == length (nub (show n))
perm :: Integer -> [String]
perm 1 = ["1"]
perm n = [t | k <- perm (n - 1), p <- [0..n - 1], let t = (take (fromInteger p) k) ++ ((head (show n)) : (drop (fromInteger p) k))]
perm' :: Integer -> [Integer]
perm' n = map read $ perm n
p41 = (oisect (takeWhile (<= 987654321) primes) $ concat $ map perm' [1..9])

main = print $ p41

--main' = print $ filter (\x -> snd x >= 500) $ zip [1..] $ map ndiv $ map (\x -> x * (x + 1) `div` 2) [1..]
--main''  = print $ length $ filter p187 [2..10^6]
--main''' = print $ length $ takeWhile (<= 10^8) primes