I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one this one, using Euler's Pentagonal Number Theorem:
I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem:
I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem:
Calculating the count of integer partitions of a number, in Haskell (uses stateful vectors internally)
Code below, also here in a gistGist
{-# LANGUAGE BangPatterns #-}
import Control.Monad (when, forM_, forM)
import Data.STRef
import Control.Monad.ST
import qualified Data.Vector.Generic.Mutable as GM
import Data.Vector.Generic.Mutable ( write )
import qualified Data.Vector.Mutable as VM
main :: IO ()
main = do
print $ part 60000
fint :: (Num b, Integral a) => a -> b
fint = fromIntegral
part :: Int -> Integer
part n = runST $ do
vec <- VM.replicate (n+1) (-3)
write vec 0 1
result <- newSTRef (-1)
forM_ [1..n] $ \i' -> do
let i = ((fromIntegral i') :: Integer)
!sR <- newSTRef 0
let -- loop :: Integer -> ST s ()
loop k = do
let f = (fint (i - k * (3 * k - 1) `div` 2))
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f)
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
let f = (fint (i - k * (3 * k + 1) `div` 2))
let xx = f :: Int
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f )
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
loop (k + 1)
loop 1 -- k starts at 1
!s <- readSTRef sR
write vec i' s
when (i' == n) $
writeSTRef result s
readSTRef result
Calculating the count of integer partitions of a number, in Haskell (uses stateful vectors internally)
Code below, also here in a gist
{-# LANGUAGE BangPatterns #-}
import Control.Monad (when, forM_, forM)
import Data.STRef
import Control.Monad.ST
import qualified Data.Vector.Generic.Mutable as GM
import Data.Vector.Generic.Mutable ( write )
import qualified Data.Vector.Mutable as VM
main :: IO ()
main = do
print $ part 60000
fint :: (Num b, Integral a) => a -> b
fint = fromIntegral
part :: Int -> Integer
part n = runST $ do
vec <- VM.replicate (n+1) (-3)
write vec 0 1
result <- newSTRef (-1)
forM_ [1..n] $ \i' -> do
let i = ((fromIntegral i') :: Integer)
!sR <- newSTRef 0
let -- loop :: Integer -> ST s ()
loop k = do
let f = (fint (i - k * (3 * k - 1) `div` 2))
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f)
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
let f = (fint (i - k * (3 * k + 1) `div` 2))
let xx = f :: Int
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f )
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
loop (k + 1)
loop 1 -- k starts at 1
!s <- readSTRef sR
write vec i' s
when (i' == n) $
writeSTRef result s
readSTRef result
Calculating the count of integer partitions of a number (uses stateful vectors internally)
{-# LANGUAGE BangPatterns #-}
import Control.Monad (when, forM_, forM)
import Data.STRef
import Control.Monad.ST
import qualified Data.Vector.Generic.Mutable as GM
import Data.Vector.Generic.Mutable ( write )
import qualified Data.Vector.Mutable as VM
main :: IO ()
main = do
print $ part 60000
fint :: (Num b, Integral a) => a -> b
fint = fromIntegral
part :: Int -> Integer
part n = runST $ do
vec <- VM.replicate (n+1) (-3)
write vec 0 1
result <- newSTRef (-1)
forM_ [1..n] $ \i' -> do
let i = ((fromIntegral i') :: Integer)
!sR <- newSTRef 0
let -- loop :: Integer -> ST s ()
loop k = do
let f = (fint (i - k * (3 * k - 1) `div` 2))
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f)
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
let f = (fint (i - k * (3 * k + 1) `div` 2))
let xx = f :: Int
when (not (f < 0)) $ do
if k `mod` 2 /= 0
then do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s + vec_f )
else do vec_f <- GM.read vec f
modifySTRef' sR (\s -> s - vec_f)
loop (k + 1)
loop 1 -- k starts at 1
!s <- readSTRef sR
write vec i' s
when (i' == n) $
writeSTRef result s
readSTRef result
I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem .:
$$P(n) = \sum_{k=1}^n (-1)^{k+1} \left[ P\left( n - \frac{k\left(3k-1\right)}{2} \right) + P\left( n - \frac{k\left(3k+1\right)}{2} \right) \right]$$
I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem .
I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem :
$$P(n) = \sum_{k=1}^n (-1)^{k+1} \left[ P\left( n - \frac{k\left(3k-1\right)}{2} \right) + P\left( n - \frac{k\left(3k+1\right)}{2} \right) \right]$$