# My Weblog

## Project Euler Problem 381

Project Euler Problem 381 is easy problem. Using Wilson theorem
$1\cdot 2\cdots ( p - 1 )\ \equiv\ -1\ \pmod{p}$
$1\cdot 2\cdots ( p - 2 )\ \equiv\ \frac{-1}{p-1} \pmod{p}$
$1\cdot 2\cdots ( p - 3 )\ \equiv\ \frac{-1}{( p-1) (p-2)} \pmod{p}$
$1\cdot 2\cdots ( p - 4 )\ \equiv\ \frac{-1}{( p-1) (p-2)(p-3)} \pmod{p}$
$1\cdot 2\cdots ( p - 5 )\ \equiv\ \frac{-1}{( p-1) (p-2)(p-3) ( p-4 )} \pmod{p}$

import Data.List
import Data.Numbers.Primes
import GHC.Conc.Sync

--use wilson theorem ( p - 1 ) ! = -1 mod p

prime = drop 2 . takeWhile ( < 10 ^ 8 ) $primes extendedGcd :: Int -> Int -> ( Int , Int ) extendedGcd a b | b == 0 = ( 1 , 0 ) | otherwise = ( t , s - q * t ) where ( q , r ) = quotRem a b ( s , t ) = extendedGcd b r modInv :: Int -> Int -> Int modInv a b | gcd a b /= 1 = error " gcd is not 1 " | otherwise = d where d = until ( > 0 ) ( + b ) . fst.extendedGcd a$ b

computeFinal :: Int -> Int
computeFinal p = computeS ( p - 1 ) 0 1 where
computeS inv ret cnt
| cnt >= 5 = mod ( ret + inv ) p
| otherwise = computeS ( mod ( inv * inv' ) p  )  ( mod ( ret + inv ) p )  ( cnt + 1 )   where
inv' = modInv ( p - cnt ) p

chunk :: [ Int ] -> Int -> [ [ Int ] ]
chunk xs n = ret where
tot = numCapabilities
brk = div n tot
ret = unfoldr fun ( xs , 1 ) where
fun ( xs' , cnt )
| null xs' = Nothing
| cnt >= tot = Just ( xs' , ( [] , cnt ) )
| otherwise = Just ( a , ( b , cnt + 1 ) ) where
( a , b ) = splitAt brk xs'

ans =   ret'  where
ret = runPar $parMap ( map computeFinal ) ( chunk prime len ) len = length prime ret' = sum . map sum$ ret

main = do
print ans


Compile it “ghc-7.4.1 -O2 -rtsopts -threaded -fforce-recomp Euler_381.hs” and run it with as many cores you have. My run time is
[mukesh@user Euler]\$ time ./Euler_381 +RTS -A16M -H2G -N8 -RTS
139602943319822

real 0m28.473s
user 0m58.204s
sys 0m21.713s

April 28, 2012