diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | LICENSE | 21 | ||||
| -rw-r--r-- | README.md | 13 | ||||
| -rw-r--r-- | collatz.hs | 39 |
4 files changed, 74 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..4967dc2 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +/collatz @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2019 Timo Wilken + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..df96978 --- /dev/null +++ b/README.md @@ -0,0 +1,13 @@ +# Playing with the Collatz conjecture + +This program prints at least `SETSIZE` (its only command-line argument) numbers +known to collapse to 1 for the Collatz conjecture. If the program loops +infinitely, the number doesn't reach 1! This is obviously not a practical way of +trying to prove the conjecture. + +## Try it + +```{sh} +$ ghc -O2 -dynamic collatz +$ ./collatz 100 +``` diff --git a/collatz.hs b/collatz.hs new file mode 100644 index 0000000..ff7e8dd --- /dev/null +++ b/collatz.hs @@ -0,0 +1,39 @@ +module Main where + +import System.Environment +import Data.Foldable +import qualified Data.Set as S + +collatz :: Integral a => a -> a +collatz n = case n `mod` 2 of 0 -> n `div` 2 + 1 -> 3*n + 1 + +chain :: Integral a => a -> [a] +chain = takeWhile (/= 1) . iterate collatz + +chainUntilKnown :: Integral a => S.Set a -> a -> [a] +chainUntilKnown known start + | collatz start `elem` known = [start] + | otherwise = start : chainUntilKnown known (collatz start) + +checkNextUnknown :: Integral a => S.Set a -> S.Set a +checkNextUnknown knownToCollapse = S.union knownToCollapse newKnown + where firstUnknown = head $ filter (`notElem` knownToCollapse) [1..] + newKnown = S.fromList $ chainUntilKnown knownToCollapse firstUnknown + +checkAll :: Integral a => [S.Set a] +checkAll = iterate checkNextUnknown $ S.singleton 1 + +data Args = Args Int + +handleArgs :: [String] -> Args +handleArgs [] = Args 10 +handleArgs [setSize] = Args (read setSize :: Int) +handleArgs _ = error "usage: collatz [SETSIZE=10]" + +main :: IO () +main = do + args <- getArgs + let Args wantedSize = handleArgs args + wantedSet = head . dropWhile ((< wantedSize) . S.size) $ checkAll + traverse_ print $ S.toAscList wantedSet |