Skip to content

Instantly share code, notes, and snippets.

@AdeelK93
Created December 12, 2017 06:34
Show Gist options
  • Save AdeelK93/4845d5f5d9308e61628c11bd66f451f6 to your computer and use it in GitHub Desktop.
Save AdeelK93/4845d5f5d9308e61628c11bd66f451f6 to your computer and use it in GitHub Desktop.
Lowest common denominator within a list of numbers
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