Sigma Notation with Index

Question

I've been trying to solve a problem that requires Sigma Notation (Or at least I think), but every implementation of Sigma Notation in Haskell i've come across doesn't use the index variable in its function. The particular formula i've been trying to replicate is:

It's used in calculating the number of trailing zeros in n!, but the best i've got is:

 sigma :: (Enum a, Num b) => a -> a -> (a -> b) -> b
 sigma i k fn = sum . map fn $ [i..k]

 zeros :: Int -> Int
 zeros n = sigma 1 n (???)

I'm trying to also create a general sigma function, that works with an index variable in f. This works, but for 100!, it gives -11 trailing zeros. Overflow?

zeros :: Int -> Int
zeros n = sigma 1 n (\i -> n `div` 5 ^ i)
        where sigma i k fn = sum $ map fn [i..k]

P.S. Im on an in-browser IDE that limits compile time. (So speed counts)

Answer 1

Your troubles are just coming from type mismatches. You want to do the truncate at the very end and use fractional arithmetic for the division, exponentiation, and summation, and then truncate the result at the end. Because of this, you'll need a bit more than just zeros n = sigma 1 n something:

zeros :: Integral a => a -> a
zeros n = truncate $ sigma 1 n (\i -> fromIntegral n / 5 ^ i)

The details here you need to worry about are the fromIntegral n, which converts n from an Integral a => a to a Num b => b, the ^ operator allows Integral a => a arguments as the exponent, so we don't need conversion there, and then truncate will convert back to an Integral. We could make this signature even more general and return a different Integral that we inputted, but that's not really useful in practice.

So now we can input either Int or Integer, depending on how big of a number you need to input to this function (since you mentioned 100!), but be warned that making a list of 100! elements is going to seriously eat up RAM and CPU time.

If you're really wanting to compute the trailing zeros of a large number, it's probably going to be a lot easier to convert it to a string, as in:

zeros :: (Show a, Integral a) => a -> Int
zeros = length . takeWhile (== '0') . reverse . show