Discussion on: Daily Challenge #7 - Factorial Decomposition

[cloudyhug]

Haskell

import Data.List
import qualified Data.Map.Strict as Map

primes :: [Int]
primes = filterPrime [2..]
  where filterPrime (p : xs) = p : filterPrime [x | x <- xs, x `mod` p /= 0]

decomp :: Int -> Map.Map Int Int
decomp n =
  if n == 1 || n `elem` lowerPrimes then Map.singleton n 1
  else Map.filter (/= 0) $ divide Nothing 0 n lowerPrimes Map.empty
  where
    lowerPrimes = takeWhile (<= n) primes
    divide Nothing             _     1 _             factors = factors
    divide (Just current)      count 1 _             factors = Map.insert current count factors
    divide Nothing             _     n (p : ps)      factors = divide (Just p) 0 n ps factors
    divide curr@(Just current) count n prim@(p : ps) factors =
      case n `divMod` current of
        (q, 0) -> divide curr (count + 1) q prim factors
        _      -> divide (Just p) 0 n ps (Map.insert current count factors)

decompFactorial :: Int -> String
decompFactorial n = toString $ foldl1 (Map.unionWith (+)) $ map decomp [2..n]
 where toString = intercalate " + " . Map.foldlWithKey (\acc k v -> (show k ++ "^" ++ show v) : acc) []

The decomp function creates a (factor, power) map describing the decomposition of an integer. The decompFactorial function creates this decomposition for all integers from 2 to n, then merges the maps summing the values for each key. The result is then pretty printed.