Yesterday, I discovered a rather fascinating result (though it was certainly known before). Unfortunately, it had absolutely nothing to do with my thesis project. The problem I was given was as follows:
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.] |