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

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, fibonacci, Haskell, kata, praxis, programming, zeckendorf

This entry was posted on July 24, 2012 at 1:35 pm and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply