Editing Euler problems/151 to 160 (section)

== [http://projecteuler.net/index.php?section=problems&id=160 Problem 160] ==
Factorial trailing digits

We use the following two facts:

Fact 1: <hask>(2^(d + 4*5^(d-1)) - 2^d) `mod` 10^d == 0</hask>

Fact 2: <hask>product [n | n <- [0..10^d], gcd n 10 == 1] `mod` 10^d == 1</hask>

We really only need these two facts for the special case of
<hask>d == 5</hask>, and we can verify that directly by
evaluating the above two Haskell expressions.

More generally:

Fact 1 follows from the fact that the group of invertible elements
of the ring of integers modulo <hask>5^d</hask> has
<hask>4*5^(d-1)</hask> elements.

Fact 2 follows from the fact that the group of invertible elements
of the ring of integers modulo <hask>10^d</hask> is isomorphic to the product
of a cyclic group of order 2 and another cyclic group.

Solution:
<haskell>
problem_160 = trailingFactorialDigits 5 (10^12)

trailingFactorialDigits d n = twos `times` odds
  where
    base = 10 ^ d
    x `times` y = (x * y) `mod` base
    multiply = foldl' times 1
    x `toPower` k = multiply $ genericReplicate n x
    e = facFactors 2 n - facFactors 5 n
    twos
     | e <= d    = 2 `toPower` e
     | otherwise = 2 `toPower` (d + (e - d) `mod` (4 * 5 ^ (d - 1)))
    odds = multiply [odd | a <- takeWhile (<= n) $ iterate (* 2) 1,
                           b <- takeWhile (<= n) $ iterate (* 5) a,
                           odd <- [3, 5 .. n `div` b `mod` base],
                           odd `mod` 5 /= 0]

-- The number of factors of the prime p in n!
facFactors p = sum . zipWith (*) (iterate (\x -> p * x + 1) 1) .
               tail . radix p

-- The digits of n in base b representation
radix p = map snd . takeWhile (/= (0, 0)) .
          iterate ((`divMod` p) . fst) . (`divMod` p)
</haskell>
it have another fast way to do this .

Solution:
<haskell>
import Data.List
mulMod :: Integral a => a -> a -> a -> a
mulMod a b c= (b * c) `rem` a
squareMod :: Integral a => a -> a -> a
squareMod a b = (b * b) `rem` a
pow' :: (Num a, Integral b) => (a -> a -> a) -> (a -> a) -> a -> b -> a
pow' _ _ _ 0 = 1
pow' mul sq x' n' = f x' n' 1
    where
    f x n y
        | n == 1 = x `mul` y
        | r == 0 = f x2 q y
        | otherwise = f x2 q (x `mul` y)
        where
            (q,r) = quotRem n 2
            x2 = sq x
powMod :: Integral a => a -> a -> a -> a
powMod m = pow' (mulMod m) (squareMod m)
 
productMod =foldl (mulMod (10^5)) 1
hFacial 0=1
hFacial a
    |gcd a 5==1=(a*hFacial(a-1)) `mod` (5^5)
    |otherwise=hFacial(a-1)
fastFacial a= hFacial $a `mod` 6250
numPrime x p=takeWhile(>0) [x `div` (p^a)|a<-[1..]]
p160 x=mulMod t5 a b
    where
    t5=10^5
    lst=numPrime x 5
    a=powMod t5 1563 $c `mod` 2500
    b=productMod  c6 
    c=sum lst
    c6=map fastFacial $x:lst
problem_160 = p160 (10^12)

</haskell>