A035517 Triangular array read by rows, formed from Zeckendorf expansion of integers: repeatedly subtract the largest Fibonacci number you can until nothing remains. Row n give Z. expansion of n.

0, 1, 2, 3, 1, 3, 5, 1, 5, 2, 5, 8, 1, 8, 2, 8, 3, 8, 1, 3, 8, 13, 1, 13, 2, 13, 3, 13, 1, 3, 13, 5, 13, 1, 5, 13, 2, 5, 13, 21, 1, 21, 2, 21, 3, 21, 1, 3, 21, 5, 21, 1, 5, 21, 2, 5, 21, 8, 21, 1, 8, 21, 2, 8, 21, 3, 8, 21, 1, 3, 8, 21, 34, 1, 34, 2, 34, 3, 34, 1, 3, 34, 5, 34, 1, 5, 34, 2, 5, 34

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• tabf
• nice
• look

Comments

Row n has A007895(n) terms.

With the 2nd Maple program, B(n) yields the number of terms in the Zeckendorf expansion of n, while Z(n) yields the expansion itself. For example, B(100)=3 and Z(100)=3, 8, 89. [Emeric Deutsch, Jul 05 2010]

Examples

			0=0; 1=1; 2=2; 3=3; 4=1+3; 5=5; 6=1+5; 7=2+5; 8=8; 9=1+8; 10=2+8; ... so triangle begins
  0;
  1;
  2;
  3;
  1, 3;
  5;
  1, 5;
  2, 5;
  8;
  1, 8;
  2, 8;
  3, 8;
  1, 3, 8;
		

References

• Zeckendorf, E., Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

Links

• T. D. Noe, Rows n = 0..1000 of triangle, flattened
• D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.
• N. J. A. Sloane, Classic Sequences

Crossrefs

Cf. A014417, A007895, A035514, A035515, A035516.

Programs

Haskell

a035517 n k = a035517_tabf !! n !! k
a035517_row n = a035517_tabf !! n
a035517_tabf = map reverse a035516_tabf
-- Reinhard Zumkeller, Mar 10 2013

Maple

with(combinat): B := proc (n) local A, ct, m, j: A := proc (n) local i: for i while fibonacci(i) <= n do n-fibonacci(i) end do end proc: ct := 0: m := n: for j while 0 < A(m) do ct := ct+1: m := A(m) end do: ct+1 end proc: F := proc (n) local i: for i while fibonacci(i) <= n do fibonacci(i) end do end proc: Z := proc (n) local j, z: for j to B(n) do z[j] := F(n-add(z[i], i = 1 .. j-1)) end do: seq(z[B(n)+1-k], k = 1 .. B(n)) end proc: for n to 25 do Z(n) end do;
# Emeric Deutsch, Jul 05 2010
# yields sequence in triangular form; end of this Maple program

Mathematica

f[n_] := (k=1; ff={}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff,1]); ro[n_] := If[n == 0, 0, r = n; s = {}; fr = f[n];
While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr,-1]]; s]; Flatten[ro /@ Range[0, 42]] (* Jean-François Alcover, Jul 23 2011 *)

Python

zeck, fib = [], [0, 1]
from itertools import count, islice
def agen(): # generator of terms
    for r in count(0):
        while fib[-1] < r:
            fib.append(fib[-2] + fib[-1])
        i = 1
        while fib[-i] > r: i += 1
        bigfib = fib[-i]
        zeck.append( ([] if r == bigfib else zeck[r-bigfib]) + [bigfib] )
        yield from zeck[r]  # row r of the triangle
print(list(islice(agen(), 90))) # Michael S. Branicky, Apr 04 2022

Extensions

More terms from James Sellers, Dec 13 1999