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.

About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: