|
%I #30 Nov 15 2021 02:46:52
%S 1,1,0,1,0,0,1,0,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,
%T 1,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,1,
%U 0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0,1,0,1
%N Zeckendorf representation of natural numbers.
%C The row lengths sequence of this array is A072649(n), n >= 1.
%C Note that the Fibonacci numbers F(0)=0 and F(1)=1 are not used in this unique representation of n >= 1. No neighboring Fibonacci numbers are allowed (no 1,1, subsequence in any row n).
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., 1994, Addison-Wesley, Reading MA, pp. 295-296.
%D E. Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41.3-4 (1972) 179-182 (with the proof from 1939).
%H Reinhard Zumkeller, <a href="/A189920/b189920.txt">Rows n = 1..1000 of triangle, flattened</a>
%F n = Sum_{m=1..rl(n)} a(n,m)*F(rl(n) + 2 - m), n >= 1, with rl(n):=A072649(n)(row length) and F(n):=A000045(n) (Fibonacci numbers).
%F T(n,k) = A213676(n, A072649(n, k)-1) for k = 1..A072649(k). - _Reinhard Zumkeller_, Mar 10 2013
%e n=1: 1;
%e n=2: 1, 0;
%e n=3: 1, 0, 0;
%e n=4: 1, 0, 1;
%e n=5: 1, 0, 0, 0;
%e n=6: 1, 0, 0, 1;
%e n=7: 1, 0, 1, 0;
%e n=8: 1, 0, 0, 0, 0;
%e n=9: 1, 0, 0, 0, 1;
%e n=10: 1, 0, 0, 1, 0;
%e n=11: 1, 0, 1, 0, 0;
%e n=12: 1, 0, 1, 0, 1;
%e n=13: 1, 0, 0, 0, 0, 0;
%e ...
%e 1 = F(2),
%e 6 = F(5) + F(2),
%e 11 = F(6) + F(4).
%t f[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); a[n_] := (fn = f[n]; xx = Array[x, Length[fn]]; r = xx /. {ToRules[ Reduce[ And @@ (0 <= # <= 1 & ) /@ xx && fn . xx == n, xx, Integers]]}; Reverse[ First[ Select[ r, FreeQ[ Split[#], {1, 1, ___}] & ]]]); Flatten[ Table[ a[n], {n, 1, 25}]] (* _Jean-François Alcover_, Sep 29 2011 *)
%o (Haskell)
%o a189920 n k = a189920_row n !! k
%o a189920_row n = z n $ reverse $ takeWhile (<= n) $ tail a000045_list where
%o z x (f:fs'@(_:fs)) | f == 1 = if x == 1 then [1] else []
%o | f == x = 1 : replicate (length fs) 0
%o | f < x = 1 : 0 : z (x - f) fs
%o | f > x = 0 : z x fs'
%o a189920_tabf = map a189920_row [1..]
%o -- _Reinhard Zumkeller_, Mar 10 2013
%Y Cf. A035517, A014417.
%K nonn,easy,tabf,base
%O 1
%A _Wolfdieter Lang_, Jun 12 2011
|
