Control.Monad.Reader

Everything About Mathematics, Functional Programming, and Haskell

Archive for July 2009

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 , , ,