login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers). 130
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,5
COMMENTS
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
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
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
From Joerg Arndt, Nov 09 2012: (Start)
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).
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).
A000120 gives the equivalent for (all) compositions. (End)
a(n) = A104324(n) - A213911(n); row lengths in A035516 and A035516. - Reinhard Zumkeller, Mar 10 2013
a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - Alan Worley, Apr 17 2015
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
From Michel Dekking, Mar 08 2020: (Start)
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.
The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
tau((j,0)) = (j,0) (j+1,1),
tau((j,1)) = (j,0).
The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
This implies that for all n and j one has
|tau^n(j,0)| = F(n+2),
where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
Secondly, we need the following simple, but crucial observation. Let the Zeckendorf representation of n be Z(n) = A014417(n). For example,
Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
Z(F(n+1)+i) = 10...0 Z(i),
where zeros are added to Z(i) to give the total representation length n-1.
This gives for i = 0,1,...,F(n)-1 that
a(F(n+1)+i) = a(i) + 1.
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).
Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
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
tau'(2j) = 2j, 2j+3, tau'(2j+1) = 2j.
The fixed point of tau' starting with 0 is
u = 03225254254472544747625...
The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
(End)
REFERENCES
Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
F. Weinstein, The Fibonacci Partitions, preprint, 1995.
É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.
LINKS
Joerg Arndt, Matters Computational (The Fxtbook), pp. 754-756.
Paul Baird-Smith, Alyssa Epstein, Kristen Flint, and Steven J. Miller, The Zeckendorf Game, arXiv:1809.04881 [math.NT], 2018.
D. E. Daykin, Representation of natural numbers as sums of generalized Fibonacci numbers, J. London Math. Soc. 35 (1960) 143-160.
Michel Dekking, Points of increase of the sum of digits function of the base phi expansion, arXiv:2003.14125 [math.CO], 2020.
F. Michel Dekking, The sum of digits functions of the Zeckendorf and the base phi expansions, Theoretical Computer Science (2021) Vol. 859, 70-79.
Damien Jamet, Pierre Popoli, and Thomas Stoll, Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences, arXiv:2106.09959 [math.NT], 2021, see p. 5.
C. G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Stichting Mathematisch Centrum, Zuivere Wiskunde, 1951.
Thomas Stoll, Combinatorial constructions for the Zeckendorf sum of digits of polynomial values, The Ramanujan Journal November 2013, Volume 32, Issue 2, pp 227-243.
F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT], 2003-2018.
FORMULA
a(n) = A000120(A003714(n)). - Reinhard Zumkeller, May 05 2005
a(n) = A107015(n) + A107016(n). - Reinhard Zumkeller, May 09 2005
a(n) = A143299(n+1) - 1. - Filip Zaludek, Oct 31 2016
a(n) = A007953(A014417(n)). - Amiram Eldar, Oct 10 2023
EXAMPLE
a(46) = a(1 + 3 + 8 + 34) = 4.
From Joerg Arndt, Nov 09 2012: (Start)
Connection to the compositions of n into odd parts (see comment):
[ #]: a(n) composition into odd parts
[ 0] [ 0] 1 1 1 1 1 1 1 1
[ 1] [ 1] 1 1 1 1 1 3
[ 2] [ 1] 1 1 1 1 3 1
[ 3] [ 1] 1 1 1 3 1 1
[ 4] [ 2] 1 1 1 5
[ 5] [ 1] 1 1 3 1 1 1
[ 6] [ 2] 1 1 3 3
[ 7] [ 2] 1 1 5 1
[ 8] [ 1] 1 3 1 1 1 1
[ 9] [ 2] 1 3 1 3
[10] [ 2] 1 3 3 1
[11] [ 2] 1 5 1 1
[12] [ 3] 1 7
[13] [ 1] 3 1 1 1 1 1
[14] [ 2] 3 1 1 3
[15] [ 2] 3 1 3 1
[16] [ 2] 3 3 1 1
[17] [ 3] 3 5
[18] [ 2] 5 1 1 1
[19] [ 3] 5 3
[20] [ 3] 7 1
Connection to the compositions of n into parts 1 or 2 (see comment):
[ #]: a(n) composition into parts 1 and 2
[ 0] [0] 1 1 1 1 1 1 1
[ 1] [1] 1 1 1 1 1 2
[ 2] [1] 1 1 1 1 2 1
[ 3] [1] 1 1 1 2 1 1
[ 4] [2] 1 1 1 2 2
[ 5] [1] 1 1 2 1 1 1
[ 6] [2] 1 1 2 1 2
[ 7] [2] 1 1 2 2 1
[ 8] [1] 1 2 1 1 1 1
[ 9] [2] 1 2 1 1 2
[10] [2] 1 2 1 2 1
[11] [2] 1 2 2 1 1
[12] [3] 1 2 2 2
[13] [1] 2 1 1 1 1 1
[14] [2] 2 1 1 1 2
[15] [2] 2 1 1 2 1
[16] [2] 2 1 2 1 1
[17] [3] 2 1 2 2
[18] [2] 2 2 1 1 1
[19] [3] 2 2 1 2
[20] [3] 2 2 2 1
(End)
From Michel Dekking, Mar 08 2020: (Start)
The third iterate of the morphism tau generating this sequence:
tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
= (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)
MAPLE
# With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n.
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);
# Emeric Deutsch, Jul 05 2010
N:= 1000: # to get a(n) for n <= N
m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)):
Z:= Vector(m):
a[0]:= 0:
for n from 1 to N do
if Z[1] = 0 then Z[1]:= 1; q:= 1;
else Z[2]:= 1; Z[1]:= 0; q:= 2;
fi;
while Z[q+1] = 1 do
Z[q]:= 0;
Z[q+1]:= 0;
Z[q+2]:= 1;
q:= q+2;
od:
a[n]:= add(Z[i], i=1..m);
od:
seq(a[n], n=0..N); # Robert Israel, Apr 17 2015
# alternative
read("transforms") :
A007895 := proc(n)
wt(A003714(n)) ;
end proc:
seq(A007895(n), n=0..10) ; # R. J. Mathar, Sep 22 2020
MATHEMATICA
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 *)
DigitCount[Select[Range[0, 1000], BitAnd[#, 2#] == 0 &], 2, 1] (* Jean-François Alcover, Jan 25 2018 *)
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 *)
PROG
(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
(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
(Haskell)
a007895 = length . a035516_row -- Reinhard Zumkeller, Mar 10 2013
(Python)
from sympy import fibonacci
def a(n):
k=0
x=0
while n>0:
k=0
while fibonacci(k)<=n: k+=1
x+=10**(k - 3)
n-=fibonacci(k - 1)
return str(x).count("1")
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 09 2017
CROSSREFS
Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
Record positions are in A027941.
Sequence in context: A102382 A024890 A254123 * A053260 A267135 A140223
KEYWORD
nonn,easy
AUTHOR
Felix Weinstein (wain(AT)ana.unibe.ch) and Clark Kimberling
EXTENSIONS
Edited by N. J. A. Sloane Jun 27 2008 at the suggestion of R. J. Mathar and Don Reble
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 28 04:16 EST 2024. Contains 370379 sequences. (Running on oeis4.)