Zeckendorf decomposition

Silly story: I was eating some chips and noticed that there were 21 left on my plate—a Fibonacci number. I realized pretty quickly that I could divide this collection into any number of subsets, each of which had a unique cardinality that was itself a lesser Fibonacci. That wasn't much of a revelation. I then got to wondering if a non-Fibonacci cardinality, like 20 chips, could still be divided into these unique sets. It could: {13, 5, 2}. I tried in vain arriving at a counter-example, eventually concluding that I didn't have enough chips to know one way or the other.

Dr. Zeckendorf had the answer though. Any positive integer can be broken down into a sum of non-consecutive Fibonacci numbers. Maybe this is obvious as well, but at first glance I find it very cool. It's like I'm 17 and spinning Lateralus again. This entry is truly just a note; I have no interesting application to provide. Just wanted to jot it down as code to revisit later.

(define FIBS (reverse 
  '(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)))

(define (z n fibs)
  (cond ((= 0 n) '())
        ((>= n (car fibs)) (cons (car fibs) (z (- n (car fibs)) (cdr fibs))))
        (else (z n (cdr fibs)))))

This will break if n is much greater than 4,181, but it wouldn't be prohibitive to store all Fibonaccis under UINT_MAX in memory. I hope the code is simple enough, but the gist of the approach is:

  1. Start with the largest Fibonacci in your (finite sub-)sequence: Fm
  2. If n ≥ Fm, then cons Fm to your Zeckendorf decomposition, subtract Fm from n, and recurse with this new value against the next lowest Fibonacci: Fm-1.
  3. If n < Fm, then recurse with an unchanged n against Fm-1.
  4. If you are greedy with big Fibonaccis like this, the sequence should always terminate with unique numbers.

For close values of n, differences only reveal themselves at the end.

(z 10000 FIBS)
  (4181 2584 1597 987 610 34 5 2)

(z 9999 FIBS)
  (4181 2584 1597 987 610 34 5 1)

(z 9998 FIBS)
  (4181 2584 1597 987 610 34 5)

(z 9997 FIBS)
  (4181 2584 1597 987 610 34 3 1)

The sequences are rather short, so I was tempted to do multiple passes over the result arrays: Zeckendorfing the Zeckendorfs to an arbitrary depth, but this resulted in profoundly uninteresting patterns due to how small the non-Fibonacci remainder is with this canonical greedy approach.

(define (zz n limit fibs)
  (foldr (lambda (x acc)
           (if (> x limit) `(,@(zz x limit (cdr fibs)) ,@acc)
                           `(,x ,@acc)))
         '()
         (z n fibs)))

limit need not be a Fibonacci itself—it doesn't seem to matter too much one way or the other.

(zz 9999 50 FIBS)
  (34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 21 34 34 21 34 21 34 34 21 34 21 34 34 5 1)

It's like this for just about every number and every depth; raising or lowering these values only changes the 2 or 3 integers you oscillate between.

Possible musical applications

I firmly believe that "generative music" is a fool's errand. As much as I respect Mr. Eno as a glamrocker and Fripp collaborator, I think he's been dead wrong on this front. Just about every algorithmic work I've heard has been horrifically boring—very much "a work" rather than some actual fucking music. Even if I jazzed up these sequences with some kind of weighted probability that occasionally escaped oscillation, it would not justify any standalone piece.

Still, the miniscule set of possible values caught my eye. With many processes there is a danger in producing a signal so chaotic and long-running that it's effectively noise. This one snaps to known numbers in a descending pattern and exits politely. Does anything fun arise from that?

  1. The slight differences at the ends of sequences 10,000 … 9,997 might be a way to suggest flourishes on a repeating motif, but this seems trivial to implement manually.
  2. The overall decay of all these sequences is too similar to differentiate between if it were used as an envelope or wave shape.
  3. There could be quirky rhythms encoded in the binary representation of a sequence.
  4. Since Robert Fripp has already been mentioned, the difference in cardinalities between 9,999 and 9,998 brings to mind some of the most memorable riffs on Discipline, where Fripp and Belew played otherwise identical sequences, but one dropped a beat.
  5. The binary form of a number could also serve as a "drawbar", engaging a specific harmonic for each set bit. I think the familiar decay pattern would bore again though—this time on the frequency spectrum.

All of this brainstorming suggests a solution in search of a problem. I think I just wanted to capture a cool little fact. I still like Lateralus for what it's worth.