Blade.hs

module Blade where

import qualified Data.Set as S

-- Implemented the inclusion-exclusion algorithm:
-- <https://stackoverflow.com/a/27248971>

-- (∑ Aj) in the formula
-- These all the numbers we've counted more than once
doubleCounts :: [Int]
doubleCounts = S.toList $ S.map slcm subsets
  where
    subsets :: S.Set (S.Set Int)
    subsets = S.filter (not . (== 1) . S.size) $
              S.filter (not . S.null) $
              S.filter (\s -> S.isProperSubsetOf s caterpillars) $
              S.powerSet caterpillars

--------------------------------------------------------------------------------

slcm :: S.Set Int -> Int
slcm = S.foldr lcm 1

caterpillars :: S.Set Int
caterpillars = S.fromList [2,3,5,7,11,13]

limit :: Int
limit = 2 * (10 ^ 9)

main = limit - (a + b - c)
  where
    a = sum $ S.map (quot limit) caterpillars
    b = quot limit $ slcm caterpillars
    c = sum $ map (quot limit) doubleCounts

-- 931468558