Posts Tagged ‘zeckendorf’

Programming Praxis – Zeckendorf Representation

July 24, 2012

In today’s Programming Praxis exercise, our goal is to find a series of non-consecutive fibonacci numbers that sum up to a given number. Let’s get started, shall we?

First, we define the fibonacci sequence:

fibs :: [Integer]
fibs = 1 : scanl (+) 1 fibs

The algorithm to find the numbers is pretty trivial as well: take the largest fibonacci number less than or equal to the target value and repeat on the remainder.

zeck :: Integer -> [Integer]
zeck 0 = []
zeck n = f : zeck (n - f) where f = last $ takeWhile (<= n) fibs

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ zeck 100 == [89,8,3]
          print $ zeck (3^15) == [9227465, 3524578, 1346269,
                                  196418, 46368, 6765, 987, 55, 2]
          print $ zeck $ 10^100