cp's OEIS Frontend

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.

%I A035517 #46 Jul 02 2025 16:01:56
%S A035517 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,
%T A035517 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,
%U A035517 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
%N 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.
%C A035517 Row n has A007895(n) terms.
%C A035517 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]
%D A035517 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.
%H A035517 T. D. Noe, <a href="/A035517/b035517.txt">Rows n = 0..1000 of triangle, flattened</a>
%H A035517 D. E. Knuth, <a href="http://dx.doi.org/10.1016/0893-9659(88)90176-0">Fibonacci multiplication</a>, Appl. Math. Lett. 1 (1988), 57-60.
%H A035517 N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>
%e A035517 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
%e A035517   0;
%e A035517   1;
%e A035517   2;
%e A035517   3;
%e A035517   1, 3;
%e A035517   5;
%e A035517   1, 5;
%e A035517   2, 5;
%e A035517   8;
%e A035517   1, 8;
%e A035517   2, 8;
%e A035517   3, 8;
%e A035517   1, 3, 8;
%p A035517 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;
%p A035517 # _Emeric Deutsch_, Jul 05 2010
%p A035517 # yields sequence in triangular form; end of this Maple program
%t A035517 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];
%t A035517 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 *)
%o A035517 (Haskell)
%o A035517 a035517 n k = a035517_tabf !! n !! k
%o A035517 a035517_row n = a035517_tabf !! n
%o A035517 a035517_tabf = map reverse a035516_tabf
%o A035517 -- _Reinhard Zumkeller_, Mar 10 2013
%o A035517 (Python)
%o A035517 zeck, fib = [], [0, 1]
%o A035517 from itertools import count, islice
%o A035517 def agen(): # generator of terms
%o A035517     for r in count(0):
%o A035517         while fib[-1] < r:
%o A035517             fib.append(fib[-2] + fib[-1])
%o A035517         i = 1
%o A035517         while fib[-i] > r: i += 1
%o A035517         bigfib = fib[-i]
%o A035517         zeck.append( ([] if r == bigfib else zeck[r-bigfib]) + [bigfib] )
%o A035517         yield from zeck[r]  # row r of the triangle
%o A035517 print(list(islice(agen(), 90))) # _Michael S. Branicky_, Apr 04 2022
%Y A035517 Cf. A014417, A007895, A035514, A035515, A035516.
%K A035517 nonn,easy,tabf,nice,look
%O A035517 0,3
%A A035517 _N. J. A. Sloane_
%E A035517 More terms from _James Sellers_, Dec 13 1999