Essays/Fibonacci Sums
< Essays
Jump to navigation
Jump to search
Every positive integer can be uniquely expressed as the sum of distinct, non-consecutive Fibonacci numbers. This is known as Zeckendorf's Theorem, and such a sum a Zeckendorf representation. We derive the computation of such sums.
From the Fibonacci Index page, we get the following verbs: fib n produces the n-th Fibonacci number, and n=:fi y satisfies ((fib n)<:y) *. y<fib n+1 .
fib=: 3 : 0 " 0
mp=. +/ .*
{.{: mp/ mp~^:(I.|.#:y) 2 2$0 1 1 1x
)
phi=: -:1+%:5
fi =: 3 : 'n - y<fib n=. 0>.(1=y)-~>.(phi^.%:5)+phi^.y'
The Fibonacci sum derives by choosing the largest Fibonacci number m less than or equal to y , then applying the same thing to y-m , and so on until the difference is 3 or less.
fsum=: 3 : 0
z=. 0$r=. y
while. 3<r do.
m=. fib fi r
z=. z,m
r=. r-m
end.
z,r$~(*r)+.0=y
)
fsum 100
89 8 3
fsum 200
144 55 1
fsum&.> i.10 5
┌──────┬────────┬──────┬────────┬───────┐
│0 │1 │2 │3 │3 1 │
├──────┼────────┼──────┼────────┼───────┤
│5 │5 1 │5 2 │8 │8 1 │
├──────┼────────┼──────┼────────┼───────┤
│8 2 │8 3 │8 3 1 │13 │13 1 │
├──────┼────────┼──────┼────────┼───────┤
│13 2 │13 3 │13 3 1│13 5 │13 5 1 │
├──────┼────────┼──────┼────────┼───────┤
│13 5 2│21 │21 1 │21 2 │21 3 │
├──────┼────────┼──────┼────────┼───────┤
│21 3 1│21 5 │21 5 1│21 5 2 │21 8 │
├──────┼────────┼──────┼────────┼───────┤
│21 8 1│21 8 2 │21 8 3│21 8 3 1│34 │
├──────┼────────┼──────┼────────┼───────┤
│34 1 │34 2 │34 3 │34 3 1 │34 5 │
├──────┼────────┼──────┼────────┼───────┤
│34 5 1│34 5 2 │34 8 │34 8 1 │34 8 2 │
├──────┼────────┼──────┼────────┼───────┤
│34 8 3│34 8 3 1│34 13 │34 13 1 │34 13 2│
└──────┴────────┴──────┴────────┴───────┘
$ fsum 2^60x
25
5 5 $ fsum 2^60x
1100087778366101931 37889062373143906 14472334024676221 308061521170129 117669030460994
44945570212853 1548008755920 86267571272 12586269025 4807526976
1836311903 165580141 39088169 9227465 514229
196418 28657 6765 2584 987
377 34 13 5 2
fsumcheck has the same argument and result as fsum , but incorporates checks:
fsumcheck=: 3 : 0 z=. fsum y assert. y = +/z assert. z -: \:~ z assert. (z-:fib j) *. 1<2-/\j=. fi z )
See also
Contributed by Roger Hui.