Essays/Fibonacci Sums

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
)

Essays/Fibonacci Sums

See also