Posts Tagged ‘prime’

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 – Fractran

July 6, 2012

In today’s Programming Praxis exercise, our goal is to write an interpreter for the esotreric programming language Fractran and use it to execute a program that generates prime numbers. Let’s get started, shall we?

A quick import:

import Data.List

The fractran interpreter itself is pretty simple. We use tuples to represent the fractions rather than Ratios since this made for slightly more elegant code. Unfortunately the Prelude doesn’t have a function to swap the values of a tuple, or I could’ve use divMod rather than having to repeat the multiplication.

fractran :: [(Integer, Integer)] -> Integer -> [Integer]
fractran xs = unfoldr (\m -> fmap ((,) m) . lookup 0 $
    map (\(n,d) -> (mod (m*n) d, div (m*n) d)) xs)

Since we’re using tuples, we represent the primegame program as a zip.

primegame :: [(Integer, Integer)]
primegame = zip [17,78,19,23,29,77,95,77, 1,11,13,15,15,55]
                [91,85,51,38,33,29,23,19,17,13,11,14, 2, 1]

Finding the primes is a matter of finding the terms in the output of fractran primegame 2 that are powers of two.

primes :: [(Integer, Integer)]
primes = [(i,e) | (i,n) <- zip [1..] $ fractran primegame 2
                , let e = round $ log (fromIntegral n) / log 2, 2^e == n]

A test to see if everything is working properly:

main :: IO ()
main = mapM_ print $ take 26 primes

Programming Praxis – Miscellanea

April 26, 2011

In today’s Programming Praxis exercise, our goal is to write three fucntions: FizzBuzz, a function to determine if a base 36 number is prime and one to split a list down the middle while going through the list only once. Let’s get started, shall we?

Some imports:

import Data.Foldable (toList)
import Data.Numbers.Primes
import Data.Sequence (ViewL(..), (|>), fromList, viewl, empty)

First up we have the classic FizzBuzz interview question. There are plenty of ways to solve it, but I’m partial to this one.

fizzbuzz :: Integral a => a -> IO ()
fizzbuzz n = mapM_ (putStrLn . f) [1..n] where
    f n = case (mod n 3, mod n 5) of (0, 0) -> "FizzBuzz"
                                     (0, _) -> "Fizz"
                                     (_, 0) -> "Buzz"
                                     _      -> show n

To determine if a word is prime we convert it from base 36 to base 10 and then determine if it’s prime.

isPrimeWord :: String -> Bool
isPrimeWord = isPrime . sum . zipWith (*) (iterate (* 36) 1) . reverse .
    map (\c -> maybe 0 id . lookup c $ zip (['0'..'9'] ++ ['A'..'Z']) [0..])

For splitting the list, the tortoise and hare algorithm seems dubious to me given the requirement that the list is only scanned once, since both of them scan the list (albeit looking only at half of the elements each). I’ve gone with a different approach. We start with two empty lists, which are balanced. If the lists are balanced, the next element will be added to the right one, which unbalances the list. If they are not balanced, the left element of the right list is added to the end of the left list.

splitList :: [a] -> ([a], [a])
splitList = f True (empty, empty) where
    f _     (l,r) [] = (toList l, toList r)
    f True  (l,r) (x:xs) = f False (l, r |> x) xs
    f False (l,r) (x:xs) = f True ((\(h :< t) -> (l |> h, t |> x)) $ viewl r) xs

Some tests to see if everything is working correctly:

main :: IO ()
main = do fizzbuzz 20
          print . not $ isPrimeWord "PRAXIS"
          print $ isPrimeWord "LISP"
          print $ splitList [] == ([],[] :: [Int])
          print $ splitList [1..4] == ([1,2],[3,4])
          print $ splitList [1..5] == ([1,2],[3,4,5])

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.

Programming Praxis – Fibonacci Primes

October 29, 2010

Today’s Programming Praxis exercise comes from the same challenge as the longest palindrome exercise from two weeks ago. The goal is to write a function that calculates the sum of the factors of 1 plus the first prime fibonacci number higher than the input number. Let’s get started, shall we?

To generate the fibonacci numbers, we use the well-known one-liner.

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Getting the factors of a number is done via simple trial division. Unlike the Scheme solution, we don’t repeat factors, since the original challenge says not to.

factors :: Integer -> [Integer]
factors = f 2 where
    f d n | n < d        = []
          | mod n d == 0 = d : f (d + 1) (div n d)
          | otherwise    = f (d + 1) n

We could write some fancy algorithm to check primality, but since we already have a function to calculate factors, why bother? Since the only factor of a prime number will be itself, we can just use that as a check. Initally I just used the isPrime function from Data.Numbers.Primes for this, but looking through the source code I realized I could replace it with this version. Obviously this won’t work too well on large numbers, but for our test case it’s fast enough.

isPrime :: Integer -> Bool
isPrime n = factors n == [n]

The top-level function does what it says on the tin: look through the fibonacci numbers to find one that’s greater than n and prime, add one and return the sum of the factors.

greplin :: Integer -> Integer
greplin n = head [sum $ factors (f + 1) | f <- fibs, f > n, isPrime f]

All that’s left is to apply it to the test number:

main :: IO ()
main = print $ greplin 227000

As expected, we get 352 as a result. And, in the spirit of the contest, which is to do these challenges quickly, I think this one took me about 20 minutes.

Programming Praxis – Proving Primality

February 2, 2010

In today’s Programming Praxis exercise we have to implement an algorithm to prove the primality of a number. Let’s get started, shall we?

Some imports:

import Data.Bits
import Data.List

the tdFactors and expm functions have both been featured in previous exercises.

tdFactors :: Integer -> [Integer]
tdFactors n = f n [2..floor . sqrt $ fromIntegral n] where
    f _ []     = []
    f r (x:xs) | mod r x == 0 = x : f (div r x) (x:xs)
               | otherwise    = f r xs

expm :: Integer -> Integer -> Integer -> Integer
expm b e m = foldl' (\r (b', _) -> mod (r * b') m) 1 .
             filter (flip testBit 0 . snd) .
             zip (iterate (flip mod m . (^ 2)) b) .
             takeWhile (> 0) $ iterate (`shiftR` 1) e

Unfortunately, these math-heavy problems typically resist shortening, so this is pretty similar to the Scheme solution.

isPrime :: Integer -> Bool
isPrime n = f 2 $ tdFactors (n - 1) where
    f _ []     = False
    f b (q:qs) | expm b (n - 1)         n /= 1 = f (b + 1) (q:qs)
               | expm b (n - 1 `div` q) n /= 1 = True
               | otherwise                     = f b qs

All that’s left is a quick test:

main :: IO ()
main = print . isPrime $ 2^89 - 1