43 lines
1.2 KiB
Haskell
43 lines
1.2 KiB
Haskell
import Data.Set (Set, fromList, insert, isSubsetOf, member, size)
|
|
import Data.Bool (bool)
|
|
|
|
firstNRecamans :: Int -> [Int]
|
|
firstNRecamans n = reverse $ recamanUpto (\(_, i, _) -> n == i)
|
|
|
|
firstDuplicateR :: Int
|
|
firstDuplicateR = head $ recamanUpto (\(rs, _, set) -> size set /= length rs)
|
|
|
|
recamanSuperset :: Set Int -> [Int]
|
|
recamanSuperset setInts =
|
|
tail $ recamanUpto (\(_, _, setR) -> isSubsetOf setInts setR)
|
|
|
|
recamanUpto :: (([Int], Int, Set Int) -> Bool) -> [Int]
|
|
recamanUpto p = rs
|
|
where
|
|
(rs, _, _) =
|
|
until
|
|
p
|
|
(\(rs@(r:_), i, seen) ->
|
|
let n = nextR seen i r
|
|
in (n : rs, succ i, insert n seen))
|
|
([0], 1, fromList [0])
|
|
|
|
nextR :: Set Int -> Int -> Int -> Int
|
|
nextR seen i r =
|
|
let back = r - i
|
|
in bool back (r + i) (0 > back || member back seen)
|
|
|
|
-- TEST ---------------------------------------------------------------
|
|
main :: IO ()
|
|
main =
|
|
(putStrLn . unlines)
|
|
[ "First 15 Recamans:"
|
|
, show $ firstNRecamans 15
|
|
, []
|
|
, "First duplicated Recaman:"
|
|
, show firstDuplicateR
|
|
, []
|
|
, "Length of Recaman series required to include [0..1000]:"
|
|
, (show . length . recamanSuperset) $ fromList [0 .. 1000]
|
|
]
|