|
%I #157 Apr 15 2024 13:23:36
%S 0,1,1,1,2,1,2,2,1,2,2,2,3,1,2,2,2,3,2,3,3,1,2,2,2,3,2,3,3,2,3,3,3,4,
%T 1,2,2,2,3,2,3,3,2,3,3,3,4,2,3,3,3,4,3,4,4,1,2,2,2,3,2,3,3,2,3,3,3,4,
%U 2,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,3,4,4,4,5,1,2,2,2,3,2,3,3,2,3,3,3,4,2,3,3
%N Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).
%C Also number of 0's (or B's) in the Wythoff representation of n -- see the Reble link. See also A135817 for references and links for the Wythoff representation for n >= 1. - _Wolfdieter Lang_, Jan 21 2008; _N. J. A. Sloane_, Jun 28 2008
%C Or, a(n) is the number of applications of Wythoff's B sequence A001950 needed in the unique Wythoff representation of n >= 1. E.g., 16 = A(B(A(A(B(1))))) = ABAAB = `10110`, hence a(16) = 2. - _Wolfdieter Lang_, Jan 21 2008
%C Let M(0) = 0, M(1) = 1 and for i > 0, M(i+1) = f(concatenation of M(j), j from 0 to i - 1) where f is the morphism f(k) = k + 1. Then the sequence is the concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003
%C From _Joerg Arndt_, Nov 09 2012: (Start)
%C Let m be the number of parts in the listing of the compositions of n into odd parts as lists of parts in lexicographic order, a(k) = (n - length(composition(k)))/2 for all k < Fibonacci(n) and all n (see example).
%C Let m be the number of parts in the listing of the compositions of n into parts 1 and 2 as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < Fibonacci(n) and all n (see example).
%C A000120 gives the equivalent for (all) compositions. (End)
%C a(n) = A104324(n) - A213911(n); row lengths in A035516 and A035516. - _Reinhard Zumkeller_, Mar 10 2013
%C a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - _Alan Worley_, Apr 17 2015
%C This follows from the fact that the sequence is subadditive: a(n+m) <= a(n) + a(m) for nonnegative integers n,m. See Lemma 2.1 of the Stoll link. - _Robert Israel_, Apr 17 2015
%C From _Michel Dekking_, Mar 08 2020: (Start)
%C This sequence is a morphic sequence on an infinite alphabet, i.e., (a(n)) is a letter-to-letter projection of a fixed point of a morphism tau.
%C The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
%C tau((j,0)) = (j,0) (j+1,1),
%C tau((j,1)) = (j,0).
%C The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
%C To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
%C This implies that for all n and j one has
%C |tau^n(j,0)| = F(n+2),
%C where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
%C Secondly, we need the following simple, but crucial observation. Let the Zeckendorf representation of n be Z(n) = A014417(n). For example,
%C Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
%C From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
%C Z(F(n+1)+i) = 10...0 Z(i),
%C where zeros are added to Z(i) to give the total representation length n-1.
%C This gives for i = 0,1,...,F(n)-1 that
%C a(F(n+1)+i) = a(i) + 1.
%C From the first observation follows that the first F(n+1) letters of tau^n(j,0) are equal to tau^{n-1}(j,0), and the last F(n) letters of tau^n(j,0) are equal to tau^{n-1}(j+1,1) = tau^{n-2}(j+1,0).
%C Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
%C It is of course possible to obtain a morphism tau' on the natural numbers by changing the alphabet: (j,0)-> 2j (j,1)-> 2j+1, which yields the morphism
%C tau'(2j) = 2j, 2j+3, tau'(2j+1) = 2j.
%C The fixed point of tau' starting with 0 is
%C u = 03225254254472544747625...
%C The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
%C (End)
%D Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
%D F. Weinstein, The Fibonacci Partitions, preprint, 1995.
%D Édouard 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, 179-182, 1972.
%H T. D. Noe, <a href="/A007895/b007895.txt">Table of n, a(n) for n = 0..10000</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 754-756.
%H Paul Baird-Smith, Alyssa Epstein, Kristen Flint, and Steven J. Miller, <a href="https://arxiv.org/abs/1809.04881">The Zeckendorf Game</a>, arXiv:1809.04881 [math.NT], 2018.
%H D. E. Daykin, <a href="https://doi.org/10.1112/jlms/s1-35.2.143">Representation of natural numbers as sums of generalized Fibonacci numbers</a>, J. London Math. Soc. 35 (1960) 143-160.
%H Michel Dekking, <a href="https://arxiv.org/abs/2003.14125">Points of increase of the sum of digits function of the base phi expansion</a>, arXiv:2003.14125 [math.CO], 2020.
%H F. Michel Dekking, <a href="https://doi.org/10.1016/j.tcs.2021.01.011">The sum of digits functions of the Zeckendorf and the base phi expansions</a>, Theoretical Computer Science (2021) Vol. 859, 70-79.
%H Damien Jamet, Pierre Popoli, and Thomas Stoll, <a href="https://arxiv.org/abs/2106.09959">Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences</a>, arXiv:2106.09959 [math.NT], 2021, see p. 5.
%H C. G. Lekkerkerker, <a href="https://ir.cwi.nl/pub/6922">Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci</a>, Stichting Mathematisch Centrum, Zuivere Wiskunde, 1951.
%H I. Nemes, <a href="http://www.risc.uni-linz.ac.at/research/combinat/risc/publications/#inemes">Fibonacci representations of multiples of Fibonacci numbers</a>.
%H Don Reble, <a href="/A007895/a007895.pdf">Zeckendorf vs. Wythoff representations: Comments on A007895</a>.
%H Thomas Stoll, <a href="http://dx.doi.org/10.1007/s11139-012-9422-6">Combinatorial constructions for the Zeckendorf sum of digits of polynomial values</a>, The Ramanujan Journal November 2013, Volume 32, Issue 2, pp 227-243.
%H F. V. Weinstein, <a href="https://arxiv.org/abs/math/0307150">Notes on Fibonacci partitions</a>, arXiv:math/0307150 [math.NT], 2003-2018.
%F a(n) = A000120(A003714(n)). - _Reinhard Zumkeller_, May 05 2005
%F a(n) = A107015(n) + A107016(n). - _Reinhard Zumkeller_, May 09 2005
%F a(n) = A143299(n+1) - 1. - _Filip Zaludek_, Oct 31 2016
%F a(n) = A007953(A014417(n)). - _Amiram Eldar_, Oct 10 2023
%e a(46) = a(1 + 3 + 8 + 34) = 4.
%e From _Joerg Arndt_, Nov 09 2012: (Start)
%e Connection to the compositions of n into odd parts (see comment):
%e [ #]: a(n) composition into odd parts
%e [ 0] [ 0] 1 1 1 1 1 1 1 1
%e [ 1] [ 1] 1 1 1 1 1 3
%e [ 2] [ 1] 1 1 1 1 3 1
%e [ 3] [ 1] 1 1 1 3 1 1
%e [ 4] [ 2] 1 1 1 5
%e [ 5] [ 1] 1 1 3 1 1 1
%e [ 6] [ 2] 1 1 3 3
%e [ 7] [ 2] 1 1 5 1
%e [ 8] [ 1] 1 3 1 1 1 1
%e [ 9] [ 2] 1 3 1 3
%e [10] [ 2] 1 3 3 1
%e [11] [ 2] 1 5 1 1
%e [12] [ 3] 1 7
%e [13] [ 1] 3 1 1 1 1 1
%e [14] [ 2] 3 1 1 3
%e [15] [ 2] 3 1 3 1
%e [16] [ 2] 3 3 1 1
%e [17] [ 3] 3 5
%e [18] [ 2] 5 1 1 1
%e [19] [ 3] 5 3
%e [20] [ 3] 7 1
%e Connection to the compositions of n into parts 1 or 2 (see comment):
%e [ #]: a(n) composition into parts 1 and 2
%e [ 0] [0] 1 1 1 1 1 1 1
%e [ 1] [1] 1 1 1 1 1 2
%e [ 2] [1] 1 1 1 1 2 1
%e [ 3] [1] 1 1 1 2 1 1
%e [ 4] [2] 1 1 1 2 2
%e [ 5] [1] 1 1 2 1 1 1
%e [ 6] [2] 1 1 2 1 2
%e [ 7] [2] 1 1 2 2 1
%e [ 8] [1] 1 2 1 1 1 1
%e [ 9] [2] 1 2 1 1 2
%e [10] [2] 1 2 1 2 1
%e [11] [2] 1 2 2 1 1
%e [12] [3] 1 2 2 2
%e [13] [1] 2 1 1 1 1 1
%e [14] [2] 2 1 1 1 2
%e [15] [2] 2 1 1 2 1
%e [16] [2] 2 1 2 1 1
%e [17] [3] 2 1 2 2
%e [18] [2] 2 2 1 1 1
%e [19] [3] 2 2 1 2
%e [20] [3] 2 2 2 1
%e (End)
%e From _Michel Dekking_, Mar 08 2020: (Start)
%e The third iterate of the morphism tau generating this sequence:
%e tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
%e = (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)
%p # With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n.
%p 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: 0, seq(B(n), n = 1 .. 104);
%p # _Emeric Deutsch_, Jul 05 2010
%p N:= 1000: # to get a(n) for n <= N
%p m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)):
%p Z:= Vector(m):
%p a[0]:= 0:
%p for n from 1 to N do
%p if Z[1] = 0 then Z[1]:= 1; q:= 1;
%p else Z[2]:= 1; Z[1]:= 0; q:= 2;
%p fi;
%p while Z[q+1] = 1 do
%p Z[q]:= 0;
%p Z[q+1]:= 0;
%p Z[q+2]:= 1;
%p q:= q+2;
%p od:
%p a[n]:= add(Z[i],i=1..m);
%p od:
%p seq(a[n],n=0..N); # _Robert Israel_, Apr 17 2015
%p # alternative
%p read("transforms") :
%p A007895 := proc(n)
%p wt(A003714(n)) ;
%p end proc:
%p seq(A007895(n),n=0..10) ; # _R. J. Mathar_, Sep 22 2020
%t zf[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); zeckRep[n_] := If[n == 0, 0, r = n; s = {}; fr = zf[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]; zeckRepLen[n_] := Length[zeckRep[n]]; Table[zeckRepLen[n], {n, 0, 104}] (* _Jean-François Alcover_, Sep 27 2011 *)
%t DigitCount[Select[Range[0, 1000], BitAnd[#, 2#] == 0 &], 2, 1] (* _Jean-François Alcover_, Jan 25 2018 *)
%t Table[Length[DeleteCases[NestWhileList[# - Fibonacci[Floor[Log[Sqrt[5] * # + 3/2]/Log[GoldenRatio]]] &, n, # > 1 &], 0]], {n, 0, 143}] (* _Alonso del Arte_, May 14 2019 *)
%o (PARI) a(n,mx=0)=if(n<4,n>0,if(!mx,while(fibonacci(mx)<n,mx++)); while(fibonacci(mx)>n,mx--); 1+a(n-fibonacci(mx),mx-2)) \\ _Charles R Greathouse IV_, Feb 14 2013
%o (PARI) a(n)=if(n<4, n>0, my(k=2,s,t); while(fibonacci(k++)<=n,); while(k && n, t=fibonacci(k); if(t<=n, n-=t; s++); k--); s) \\ _Charles R Greathouse IV_, Sep 02 2015
%o (Haskell)
%o a007895 = length . a035516_row -- _Reinhard Zumkeller_, Mar 10 2013
%o (Python)
%o from sympy import fibonacci
%o def a(n):
%o k=0
%o x=0
%o while n>0:
%o k=0
%o while fibonacci(k)<=n: k+=1
%o x+=10**(k - 3)
%o n-=fibonacci(k - 1)
%o return str(x).count("1")
%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 09 2017
%Y Cf. A000045, A007953, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911, A014417, A003849.
%Y Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
%Y Record positions are in A027941.
%K nonn,easy
%O 0,5
%A Felix Weinstein (wain(AT)ana.unibe.ch) and _Clark Kimberling_
%E Edited by _N. J. A. Sloane_ Jun 27 2008 at the suggestion of _R. J. Mathar_ and _Don Reble_
|
