{- |
<http://www.luschny.de/math/seq/ZumkellerNumbers.html>

<http://www.research.att.com/~njas/sequences/A083207>

A positive integer n is said to be a Zumkeller number [A083207]
if the positive factors of n can be partitioned into two disjoint parts
so that the sums of the two parts are equal.
We shall call such a partition a Zumkeller partition.
(K.P.S. Bhaskara Rao, Yuejian Peng, On Zumkeller Numbers.)
-}
module Zumkeller where

import Data.List.HT (splitEverywhere, )
import Data.Tuple.HT (mapPair, )


divisors :: Int -> [Int]
divisors n =
   filter (\x -> mod n x == 0) [1..n]


partitions :: Int -> [([Int], [Int])]
partitions n =
   let divs = divisors n
       sumDivs = sum divs
       recourse s0 remDivs =
          case compare (2*s0) sumDivs of
             LT ->
               do (l,d,r) <- splitEverywhere remDivs
                  (pl,pr) <- recourse (s0+d) r
                  return (d:pl, l++pr)
             EQ -> [([], remDivs)]
             GT -> []
   in  {-
       1 is always in the first list in order to avoid duplicate partitions.

       We reverse in order to start with big divisors.
       This way we can cut branches earlier.
       -}
       case divs of
          [] -> []
          one:rd ->
             if mod sumDivs 2 /= 0
               then []
               else
                 map (mapPair ((one:) . reverse, reverse)) $
                 recourse one (reverse rd)


main :: IO ()
main =
   mapM_ (\n ->
      case partitions n of
         [] -> return ()
         (l,r):_ ->
            putStrLn (show n ++ "   " ++ show l ++ "   " ++ show r))
   [1..4000]