Programming Praxis – Zeckendorf Representation

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
About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: