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.