We say that a natural number is

**polite**if it can be expressed as the sum of two or more consecutive natural numbers. For instance, 7 = 3 + 4 is polite, as is 12 = 3 + 4 + 5. A natural number is

**impolite**otherwise. Find the first impolite number greater than 50.

The guy who told me this problem said that he'd written a program to solve it, but the program he described was horrifyingly naive: he looped over numbers

*n*greater than 50, each time starting with one and adding consecutive numbers until he exceeded

*n*, then started adding consecutive numbers starting with 2, and so on. Surely I can do better than that, I thought.

So I did:

-- Thm (Gauss): a + (a+1) + ... + (a+k-1) = k*a + k*(k-1)/2 -- Numbers of the form 1 + 2 + ... + n are called "triangle" numbers. --triangle :: Int -> Int triangle n = n*(n-1) `div` 2 triangles = map triangle [2..] --isPolite :: Int -> Bool isPolite n = (politesse n) /= [] --politesse :: Int -> [(Int, Int)] politesse n = filter (\ (k,t) -> ((n-t) `mod` k) == 0) $ zip [2..] $ takeWhile (<n) triangles answer = take 1 $ filter (not.isPolite) [50 .. ]That was written away from a computer, and worked almost first time - I'd previously had

`triangles`in place of

`$ takeWhile (<n) triangles`, which obviously led to an infinite loop.

But anyway, calling

`answer`gave the result 64. Hurrah. But it seemed a bit surprising to have 14 polite numbers in a row - how dense are these things, anyway? So I asked Hugs to give me

`take 10 $ filter (not.isPolite) [2..]`and got the answer

`[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]`

All powers of 2. Now that's

*weird*. I wondered if that pattern continues? Letting the calculation run for a longer time showed that the only impolite numbers up to 2^26 were powers of 2 (if you're going to run that experiment yourself, you may wish to uncomment the type declarations: machine-integer arithmetic is a

*lot*faster than bignum arithmetic). Another experiment showed that all powers of 2 up to 2^35 were impolite. So it seemed clear: a natural number is impolite iff it's a power of two.

A little thought (and talking the problem over with my supervisor) yielded a proof that all numbers fitting this pattern were indeed impolite, and what we thought was a proof that every number

*not*fitting this pattern was polite. But on closer examination this second proof doesn't quite work: it shows that every non-pattern-fitting number is the sum of two or more consecutive

*integers*(which can be negative), but not necessarily two or more natural numbers (which can't). Owing to the limitations of cuts, I'll post the proof in a separate article, behind a cut so you can have a go yourselves.

[

**UPDATE**: I have now seen how to complete my proof. You'll find it behind the cut in the next post.]