numbers (version 0.8-5)

zeck: Zeckendorf Representation

Description

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

Usage

zeck(n)

Value

List with components fibs the Fibonacci numbers that add sum up to

n, and inds their indices in the Fibonacci sequence.

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.

Examples

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