Generates the Zeckendorf representation of an integer as a sum of Fibonacci numbers.
zeck(n)
integer.
List with components fibs
the Fibonacci numbers that add sum up to
n
, and inds
their indices in the Fibonacci sequence.
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.
# NOT RUN {
zeck( 10) #=> 2 + 8 = 10
zeck( 100) #=> 3 + 8 + 89 = 100
zeck(1000) #=> 13 + 987 = 1000
# }
Run the code above in your browser using DataLab