Control.Monad.Reader

Everything About Mathematics, Functional Programming, and Haskell

Archive for the ‘Algorithm’ Category

Partition An Integer n to an arithmetic series

leave a comment »

Give a positive integer n, generate all partition of n to an arithmetic series with common difference 1.

First, a straightforward solution:

import Data.List (find)
import Data.Maybe (catMaybes)

-- partition positive integer n to an arithmetic series
partitionToArithmetic0 n = catMaybes $ map partition [1..(n-2)]
    where
        partition x = let ys = [x..(n-1)] in
            case find (p x) ys of
                Just y  -> Just (x, y)
                Nothing -> Nothing

        p x y
            | (x+y) * (y-x+1) == 2 *n = True
            | otherwise               = False

Second, a not so straightforward solution, but much more effective than the first:

partitionToArithmetic1 n = catMaybes $ map partition [2..hh]
    where
        hh = floor $ sqrt $ fromIntegral $ 2*n

        partition h
            | not $ s > d = Nothing
            | not $ or [ hr /= 0 && nh == 0, hr == 0 && 2*nh == h] = Nothing
            | otherwise = Just (s-d, s+d1)
          where
            s = n `div` h
            d = (h-1) `div` 2
            d1 = d + (if even h then 1 else 0)
            hr = h `rem` 2
            nh = n `rem` h

You can check these two solutions are equal (upto n) by

test u = and $ map (\n -> (reverse $ partitionToArithmetic0 n) == partitionToArithmetic1 n) [1..u]

Exercise: Prove solution two is right.
Answer:
Let hight (or length) of an arithmetic series partition of a positive integer n is h, and

    s  = n/h - (n % h)
    d  = floor( (h-1) / 2)
    d1 = d + (if even h then 1 else 0)

We’ll prove it by three steps.

Step 1, [s-d .. s+d1] is an arithmetic series partition of the positive integer n.

    (s-d + s+d+[even h]) (s+d+[even h] - (s-d) + 1) / 2
    = (2*s + [even h]) (2*d + [even h] + 1) /2
    = (2*s + [even h]) * h / 2
    = n - (n % h) + [even h] * h / 2

    If [even h] * h = 2 * (n % h), we have sum [s-d .. s+d1] = n.
    ([even h] = if even h then 1 else 0)

Step 2, an arithmetic series partition of the positive integer n can be write as [s-d .. s+d1].

To prove this, we only need to prove that s = n/h – (n%h)/h.

    (s-d + s+d+[even h]) (s+d+[even h] - (s-d) + 1) / 2 = n

so

    s = n/h - [even h]/2

Because [even h] * h = 2 * (n % h), so we have s = n/h – (n % h)/h.

Step 3, h <= sqrt (2*n).

For partition n = h + (h-1) + … + 2 + 1, h get maximum value.

    (2 + (h-1)) * h / 2 >= n

so

    h * (h+1) >= 2*n

If h = sqrt (2*n), h * (h + 1) = 2*n + sqrt (2*n) > 2*n.

Written by Lee Duhem

July 12, 2009 at 4:15 am

Posted in Algorithm, Haskell, Mathematics

Tagged with , , ,

Sieve of Eratosthenes In Haskell

leave a comment »

Algorithm description, see Sieve of Eratosthenes

module Main where

import System.Environment

isPrime p (x:xs)
	| x*x > p	 = True
	| p `mod` x == 0 = False
	| otherwise	 = isPrime p xs

primes = 2 : oprimes
	where oprimes = 3 : [ p | p <- [5,7..], isPrime p oprimes]

main = do
	args <- getArgs
	let	n = read $ args !! 0
		x = takeWhile (< n) primes
	print $ length x
	print x

There is a HackageDB package called primes which provides an efficient lazy wheel sieve for prime generation.

This version looks nicer, but less effective:

sieve (x:xs) = x : sieve xs'
	where xs' = filter (\y -> y `mod` x /= 0) xs

primes = 2 : sieve [3,5..]

See also The Genuine Sieve of Eratosthenes

Written by Lee Duhem

May 20, 2009 at 5:12 pm

Posted in Algorithm, Haskell, Mathematics

Tagged with , , ,