Posts Tagged ‘factors’

Programming Praxis – Prime Partitions

October 19, 2012

In today’s Programming Praxis exercise, our goal is to calculate the number of prime partitions for a given number. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.Map as M
import Data.Numbers.Primes

First we need to calculate the sum of the unique prime factors of a given number. The trivial way is to to take the list of prime factors, filter out the unique numbers and sum those. In the provided solution this is marked as the wrong way since there is a more efficient solution. On the other hand, we only need to this once each for the numbers 1 through 1000, so it’s not like it’s a massive performance bottleneck. Since performance doesn’t matter much, I personally prefer the straightforward, easy to understand implementation.

sopf :: Integer -> Integer
sopf = sum . nub . primeFactors

At first glance, the algorithm for the amount of prime partitions bears some resemblance to the Fibonacci function. The difference here is that each term refers to all of its predecessors instead of a fixed number, which means the typical zipWith solution won’t work. Instead, we build op a dictionary where for each number we store sopf(n) and k(n) so we don’t have to recalculate them.

k :: Integer -> Integer
k n = snd $ foldl' calc M.empty [1..n] M.! n where
    calc dict i = M.insert i (s, div (s + sum (map (\j -> (fst $ dict M.! j) *
        (snd $ dict M.! (i - j))) [1..i-1])) i) dict where s = sopf i

A test to see if everything is working properly:

:: IO ()
main = print $ k 1000 == 48278613741845757

Programming Praxis – Two Factoring Games

February 18, 2011

In today’s Programming Praxis exercise, our goal is to implement two algorithms related to prime factors; one to calculate the home prime of a number and one to generate the Euclid-Mullin sequence. Let’s get started, shall we?

Some imports:

import Data.List
import Data.Numbers.Primes

To calculate the home prime we repeatedly concatenate the digits of the prime factors until the number is prime.

homePrime :: Integer -> Integer
homePrime = head . filter isPrime .
            iterate (read . concatMap show . primeFactors)

The Eulic-Mullin sequence can be written as a basic unfold.

euclidMullin :: [Integer]
euclidMullin = unfoldr (\p -> let a = head (primeFactors $ p + 1)
                              in  Just (a, p * a)) 1

Naturally, we need to test if we did everything correctly:

main :: IO ()
main = do print $ homePrime 99 == 71143
          print $ take 10 euclidMullin ==
                  [2,3,7,43,13,53,5,6221671,38709183810571,139]

Looks like everything is working properly.