Funtastic Birthday with Haskell

Hey, it's my birthday today so I think it's good time for something less serious and just fun. Couple of folks asked me about my age today and since I anticipated the question I decided to answer with a small mathematical puzzle: my age is the smallest integer that is divisible by 11 and is a successor of a prime number. By successor of a number s I mean s+1.

I was curious though as to what is the next number that satisfies the above condition. So I decided to write a program in Haskell - my favorite functional language - to generate the sequence:

	isqrt = floor . sqrt . fromIntegral
	isPrime k = null [ n | n <- [2..isqrt k], k `mod` n == 0]
	birthdayNumbers = [ n | n <- [1..], n `mod` 11 == 0 && isPrime (n-1)]

view raw Fun.hs hosted with ❤ by GitHub

I won't dissect it too much - after all I promised this would be fun - so let me just point out one little fact about Haskell that I always find fascinating: it lets you define and use infinite sequences like the birthday numbers above. In fact, if you try to evaluate this sequence your machine will start producing the numbers but it would never stop - that is if it had unlimited amount of memory.

The beautiful trick is that once you have an infinite sequence, you can extract portions of it to get answers to finite questions, like my tiny age puzzle - which can be answered by taking the first element of the sequence:

So how optimistic would it be to hope to experience another birthday that satisfies the condition? According to wikipedia the highest verified age ever attained is 122 - so we can just check for "birthday" numbers up to this age:

*Fun> takeWhile (<=122) birthdayNumbers
[44,110]

As you can see, the answer is 'very optimistic' :-)
If you just simply want to see the first 10 numbers of the sequence you can do:

*Fun> take 10 birthdayNumbers
[44,110,132,198,242,264,308,374,440,462]

You may also be wondering, why not make the program even shorter by dropping the isqrt function and instead checking the divisors up to k-1? The reason is obvious: performance. I leave it to the inquiring reader to see the difference for themselves. This is how you can turn on the built-in profiling in the Haskell interpreter and calculate the gap between the consecutive birthday numbers:

*Fun> :set +s
*Fun> take 10 (zipWith (-) (tail birthdayNumbers) birthdayNumbers)
[66,22,66,44,22,44,66,66,22,110]
(0.02 secs, 3042172 bytes)

One final thought: there are actually two ways to solve the puzzle I've given to the curious inquirers:

1. exact: verify the predecessor primality for all multiples of 11 until you find the solution
2. heuristic: since I was giving the puzzle in a face-to-face talk it was much easier to estimate my age then compare it with the nearest multiples of 11 and rule out 33 and 55 as being too low / too high respectively.

Now which is the best way? It really depends - do you need to get the correct answer 100% of the time? Or do you need to be really fast while you can tolerate an occasional mistake? In computing, as in life, it's up to you to make your choices :-)