This blog post is a rehash of the Problem #1 in Richard Bird’s excellent book “Pearls of Functional Algorithm Design”. The title of the chapter is “The smallest free number”. Most of the book refers to Haskell, I will try and provide Scala implementations. Either way, the book is highly recommended.

Problem definition: Find the smallest number n not in a given set X of natural numbers.