On 5/15/08, Steve Witham <sw@tiac.net> wrote:

In OEIS terms, is this sequence interesting? I guess "nonn" and "easy". Is it "nice"?

Name(?): Smallest term in Zeckendorf representation of n http://en.wikipedia.org/wiki/Zeckendorf's_theorem ...

I made heavy use of this "Fib-adic" representation when investigating the Penrose tiling in the 1970's, though I didn't associate it with the name Zeckendorf. The analogy with positional (binary, etc) notation is easier to appreciate if the F_n are detached and only their coefficients retained --- e.g. in base-10, 20 = 13+5+2 = F_7 + F_5 + F_3 = 101010 in base-F [the final digit corresponding to F_2]. Each half-kite or half-dart in the tiling has a base-F coordinate associated (very nearly uniquely) with it, so that "inflation" of faces corresponds to shifting coordinates left two places, then appending 00, 01 or 10 (kite only) for respective subfaces. The Wikipedia page makes heavy weather of uniqueness, obvious by induction: given natural x with F_n <= x <= F_{n+1}, assume every natural y < F_n is uniquely representable as a sum of non-consecutive F_k with 1 < k < n; note that no y >= F_n is so representable; apply assumption to y = x - F_n. [x = 0 is trivially the empty sum.] Also mentioned there is a "Fibonacci product", defined by analogy with binary product: with x = \sum_i a_i F_i, y = \sum_j b_j F_j, x(*)y = \sum_{i,j} a_i b_j F_{i+j} . Knuth reputedly proved this operation to be associative, which Wikipedia finds surprising. Apparently it follows immediately from the basic result F_n = ((tau)^n - (taubar)^n)/sqrt5 where (sqrt5)^2 = 5, tau = (1 + sqrt5)/2 is the usual golden section number, and taubar = (1 - sqrt5)/2 is its conjugate. Substituting into the definition, x(*)y = (1/5)\sum_{i,j} a_i b_j tau^{i+j} + ... = f_1(x,y) + ... + f_4(x,y), where each of the functions f_k(x,y) is trivially associative. Finally, note that the sum of associative functions is also associative. But this reasoning has a gap: supposing x(*)y or y(*)z within x(*)y(*)z is first reduced again to canonical form, will the final product have the same value as when not so reduced? Relaxing the uniqueness constraint to the extreme, we could set a_2 = x, a_i = 0 for i > 2; then x(*)y evaluates to 3 x y, which is certainly not correct --- so after all, Knuth's theorem is surprising! Fred Lunnon