pozorvlak (pozorvlak) wrote,

The struggle for knowledge...

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.]
Tags: computers, haskell, maths

  • PSA: Working Effectively With Legacy Code by Michael Feathers

    I am only about a hundred pages into this book, but it had paid for itself after fifty. I wish I'd read it ten years ago. Actually, I wish I'd read…

  • Srelipmoc ni esruoc tsrif a

    If I ever design a first course in compilers, I'll do it backwards: we'll start with code generation, move on to static analysis, then parse a token…

  • Commuting

    Quaffing the last of my quickening cup, I chuck fair Josie, my predatory protégée, behind her ear. Into my knapsack I place fell Destruction, my…

  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.