Created
December 12, 2017 06:34
-
-
Save AdeelK93/4845d5f5d9308e61628c11bd66f451f6 to your computer and use it in GitHub Desktop.
Lowest common denominator within a list of numbers
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module Lcd where | |
import Data.List | |
import Control.Arrow | |
-- Integer square root | |
isqrt :: Integer -> Integer | |
isqrt = floor . sqrt . fromIntegral | |
-- Either a list of factors or the number itself (if prime) | |
primefactors :: Integer -> [Integer] | |
primefactors n = if null factor then [n] else head factor : primefactors (div n $ head factor) | |
where factor = filter (\x -> mod n x == 0) [2..(isqrt n)] | |
-- Our tallying type for counting each integer | |
type TallyInt = (Integer, Int) | |
-- Given an integer, how many of each prime shows up? | |
tallyprimes :: Integer -> [TallyInt] | |
tallyprimes p = map (head &&& length) (group $ primefactors p) | |
tallySort :: [TallyInt] -> [TallyInt] | |
tallySort = sortBy (\a b -> if fst a > fst b then GT else LT) | |
-- Groups together tallies with the same integer | |
tallyGroup :: [TallyInt] -> [[TallyInt]] | |
tallyGroup t = groupBy (\a b -> fst a == fst b) $ tallySort t | |
-- Tally with the highest count for each integer | |
tallyMax :: [[TallyInt]] -> [TallyInt] | |
tallyMax = map $ maximumBy (\a b -> if snd a > snd b then GT else LT) | |
-- All factors raised to their highest count, multiplied together | |
tallyProd :: [TallyInt] -> Integer | |
tallyProd = foldr (\t acc -> fst t ^ toInteger (snd t) * acc) 1 | |
-- Lowest common denominator within a list of numbers | |
lcd :: [Integer] -> Integer | |
lcd n = tallyProd . tallyMax $ tallyGroup (concatMap tallyprimes n) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment