Programming Praxis – Polite Numbers

In today’s Programming Praxis exercise, our task is to list all the ways that a number can be written as the sum of a consecutive series of integers. Let’s get started, shall we?

Some imports:

import Data.List
import Data.Numbers.Primes

We need a function to calculate the divisors of a number, which we recycle from a previous exercise:

divisors :: Integral a => a -> [a]
divisors = nub . sort . map product . subsequences . primeFactors

We use a somewhat more compact version of the algorithm than the Scheme solution. The main savings are replacing the if statement with simply taking the maximum of the two numbers and not including an explicit check for powers of two, since the basic algorithm already produces the correct answer and powers of 2 are rare enough that in my opinion the extra algorithm size is not warranted.

polites :: Integral a => a -> [[a]]
polites n = [ [max (d//2 - n//d + 1) (n//d - d//2)..n//d + d//2]
            | d <- tail $ divisors n, odd d, let (//) = div]

Thanks to laziness we don’t have to duplicate code when calculating the politeness of a number (the length of the result set). The result sets themselves are never evaluated, so all this does is count the odd divisors.

politeness :: Integral a => a -> Int
politeness = length . polites

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ polites 15 == [[4..6],[1..5],[7,8]]
          print $ politeness 15 == 3
          print $ polites 28 == [[1..7]]
          print $ politeness 28 == 1
          print $ polites 33 == [[10..12],[3..8],[16,17]]
          print $ politeness 33 == 3
          print . all (null . polites) . take 10 $ iterate (* 2) 1

Looks like it is.