Zeckendorf Representation

Description

Generates the Zeckendorf representation of an integer as a sum of Fibonacci numbers.

Usage

1
zeck(n)

Arguments

n

integer.

Details

According to Zeckendorfs theorem from 1972, each integer can be uniquely represented as a sum of Fibonacci numbers such that no two of these are consecutive in the Fibonacci sequence.

The computation is simply the greedy algorithm of finding the highest Fibonacci number below n, subtracting it and iterating.

Value

List with components fibs the Fibonacci numbers that add sum up to n, and inds their indices in the Fibonacci sequence.

Examples

1
2
3
zeck(  10)  #=> 2 + 8 = 10
zeck( 100)  #=> 3 + 8 + 89 = 100
zeck(1000)  #=> 13 + 987 = 1000