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,3

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]

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

Example

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;

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 *)

Prog

(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
(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

Crossrefs

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

Sequence in context: A352686 A154722 A194760 * A099471 A243574 A121775

Adjacent sequences: A035514 A035515 A035516 * A035518 A035519 A035520

Keyword

nonn,easy,tabf,nice,look

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Dec 13 1999

Status

approved