login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007895 Number of terms in Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers). 84
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) = 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 sequence = concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003

Let M(1)=1, M(2)=2 and for n>=3, M(n)=M(n-1).f(M(n-2)) where f() increments by one and the dot stands for concatenation, then this sequence is 0.M(1).M(2).M(3).M(4)... , see the example. - Joerg Arndt, May 14 2011

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

REFERENCES

C. G. 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.

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, 179-182, 1972.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..10000

Joerg Arndt, Matters Computational (The Fxtbook), pp. 754-756.

D. E. Daykin, Representation of natural numbers as sums of generalized Fibonacci numbers, J. London Math. Soc. 35 (1960) 143-160.

I. Nemes, Fibonacci representations of multiples of Fibonacci numbers

_Don Reble_, Zeckendorf vs. Wythoff representations: Comments on A007895

T. 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-2015.

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

EXAMPLE

a(46) = a(1+3+8+34) = 4.

From Joerg Arndt, May 14 2011: (Start)

The sequence, apart from the initial zero, as an irregular triangle:

1,        = M(1)

1,        = M(2)

1, 2,     = M(3) = M(2).f(M(1))

1, 2, 2,  = M(4) = M(3).f(M(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, ...

(End)

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)

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

MATHEMATICA

f[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); z[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]; a[n_] := Length[z[n]]; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Sep 27 2011 *)

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 xrange(0, 101)] # Indranil Ghosh, Jun 09 2017

CROSSREFS

Cf. A000045, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911.

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

Adjacent sequences:  A007892 A007893 A007894 * A007896 A007897 A007898

KEYWORD

nonn,easy,changed

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 20 05:42 EDT 2017. Contains 293601 sequences.