## Posts Tagged ‘**Algorithm**’

## Partition An Integer n to an arithmetic series

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.

## Sieve of Eratosthenes In Haskell

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