A213911 -id:A213911 - cp's OEIS frontend

A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).

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

Offset: 0

Felix Weinstein (wain(AT)ana.unibe.ch) and Clark Kimberling

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)

			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)

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.

T. D. Noe, Table of n, a(n) for n = 0..10000
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.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See p. 10.
I. Nemes, Fibonacci representations of multiples of Fibonacci numbers.
Don Reble, Zeckendorf vs. Wythoff representations: Comments on A007895.
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.

Cf. A000045, A007953, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911, A014417, A003849.
Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
Record positions are in A027941.

a007895 = length . a035516_row  -- Reinhard Zumkeller, Mar 10 2013

# 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") : # https://oeis.org/transforms.txt
A007895 := proc(n)
    wt(A003714(n)) ;
end proc:
seq(A007895(n),n=0..10) ; # R. J. Mathar, Sep 22 2020

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 *)
Flatten[Nest[{Flatten[#], #[[1]] + 1} &, {0, 1}, 9]] (* Paolo Xausa, Jun 17 2024 *)

a(n,mx=0)=if(n<4,n>0,if(!mx,while(fibonacci(mx)n,mx--); 1+a(n-fibonacci(mx),mx-2)) \\ Charles R Greathouse IV, Feb 14 2013

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

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

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

Edited by N. J. A. Sloane Jun 27 2008 at the suggestion of R. J. Mathar and Don Reble

A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.

Original entry on oeis.org

0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010, 1010000, 1010001, 1010010, 1010100, 1010101

Offset: 0

Olivier Gérard

Old name was: Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary vectors not containing 11.
For n > 0, write n = Sum_{i >= 2} eps(i) Fib_i where eps(i) = 0 or 1 and no 2 consecutive eps(i) can be 1 (see A035517); then a(n) is obtained by writing the eps(i) in reverse order.
"One of the most important properties of the Fibonacci numbers is the special way in which they can be used to represent integers. Let's write j >> k <==> j >= k+2. Then every positive integer has a unique representation of the form n = F_k1 + F_k2 + ... + F_kr, where k1 >> k2 >> ... >> kr >> 0. (This is 'Zeckendorf's theorem.') ... We can always find such a representation by using a "greedy" approach, choosing F_k1 to be the largest Fibonacci number =< n, then choosing F_k2 to be the largest that is =< n - F_k1 and so on. Fibonacci representation needs a few more bits because adjacent 1's are not permitted; but the two representations are analogous." [Concrete Math.]
Since the binary representation of n in base of Fibonacci numbers allows only the successive bit pairs 00, 01, 10 and leaves 11 unused, we can use a ternary representation using all trits 0, 1, 2 where 00 --> 0, 01 --> 1 and 10 --> 2 (e.g. binary 1001010 as ternary 1022). - Daniel Forgues, Nov 30 2009
The same sequence also arises when considering the NegaFibonacci representations of the integers, as follows. Take the NegaFibonacci representations of n = 0, 1, 2, ... (A215022) and of n = -1, -2, -3, ... (A215023), sort the union of these two lists into increasing binary order, and we get A014417. Likewise the corresponding list of decimal representations, A003714, is the union of A215024 and A215025 sorted into increasing order.  - N. J. A. Sloane, Aug 10 2012
Also, numbers, written in binary, such that no adjacent bits are equal to 1: A one-dimensional analog of the matrices considered in A228277/A228285, A228390, A228476, A228506 etc. - M. F. Hasler, Apr 27 2014
The sequence of final bits, starting with a(1), is the complement of the Fibonacci word A005614. - N. J. A. Sloane, Oct 03 2018
This representation is named after the Belgian Army doctor and mathematician Edouard Zeckendorf (1901-1983). - Amiram Eldar, Jun 11 2021

			The Zeckendorf expansions of 1, 2, ... are 1 = 1 = Fib_2 -> 1, 2 = 2 = Fib_3 -> 10, 3 = Fib_4 -> 100, 4 = 3+1 = Fib_4 + Fib_2 -> 101, 5 = 5 = Fib_5 -> 1000, 6 = 1+5 = Fib_2 + Fib_5 -> 1001, etc.

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
Edouard 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.

T. D. Noe and Harry J. Smith, Table of n, a(n) for n = 0..10000
Paul Dalenberg and Tom Edgar, Consecutive factorial base Niven numbers, Fibonacci Quart., Vol. 56, No. 2 (2018), pp. 163-166.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, 43 pages, no date, apparently unpublished. See Table 2.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, unpublished, no date. [Cached copy, with permission]
Donald E. Knuth, Fibonacci multiplication, Appl. Math. Lett., Vol. 1, No. 1 (1988), pp. 57-60.
Julien Leroy, Michel Rigo and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics, Vol. 340, No. 5 (2017), pp. 862-881.
Casey Mongoven, Zeckendorf Representations no. 17 (a musical composition with A014417).
Wikipedia, Zeckendorf's theorem.

Cf. A000045, A003794, A007895, A035517, A130234, A215022, A215023, A215024, A215025.
a(n) = A003714(n) converted to binary.
Cf. also A005614, A189920, A104324, A213911.
See A104326 for dual Zeckendorf representation of n.

a014417 0 = 0
a014417 n = foldl (\v z -> v * 10 + z) 0 $ a189920_row n
-- Reinhard Zumkeller, Mar 10 2013

A014417 := proc(n)
    local nshi,Z,i ;
    if n <= 1 then
        return n;
    end if;
    nshi := n ;
    Z := [] ;
    for i from A130234(n) to 2 by -1 do
        if nshi >= A000045(i) and nshi > 0 then
            Z := [1,op(Z)] ;
            nshi := nshi-A000045(i) ;
        else
            Z := [0,op(Z)] ;
        end if;
    end do:
    add( op(i,Z)*10^(i-1),i=1..nops(Z)) ;
end proc: # R. J. Mathar, Jan 31 2015

fb[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n * Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; FromDigits[fr]]; Table[ fb[n], {n, 0, 30}] (* Robert G. Wilson v, May 15 2004 *)
r = Map[Fibonacci, Range[2, 12]]; Table[Total[FromDigits@ PadRight[{1}, Flatten@ #] &@ Reverse@ Position[r, #] & /@ Abs@ Differences@ NestWhileList[Function[k, k - SelectFirst[Reverse@ r, # < k &]], n + 1, # > 1 &]], {n, 0, 33}] (* Michael De Vlieger, Mar 27 2016, Version 10 *)
FromDigits/@Select[Tuples[{0,1},7],SequenceCount[#,{1,1}]==0&] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Aug 14 2019 *)

Zeckendorf(n)=my(k=0,v,m); while(fibonacci(k)<=n,k=k+1); m=k-1; v=vector(m-1); v[1]=1; n=n-fibonacci(k-1); while(n>0,k=0; while(fibonacci(k)<=n,k=k+1); v[m-k+2]=1; n=n-fibonacci(k-1)); v \\ Ralf Stephan

Zeckendorf(n)= { local(k); a=0; while(n>0, k=0; while(fibonacci(k)<=n, k=k+1); a=a+10^(k-3); n=n-fibonacci(k-1); ); a }
{ for (n=0, 10000, Zeckendorf(n); print(n," ",a); write("b014417.txt", n, " ", a) ) } \\ Harry J. Smith, Jan 17 2009

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 x
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Harry J. Smith

Comment layout fixed by Daniel Forgues, Dec 07 2009
Typo corrected by Daniel Forgues, Mar 25 2010
Definition expanded and Duchene et al. reference added by N. J. A. Sloane, Aug 07 2018
Name corrected by Michel Dekking, Nov 30 2020

A371176 Numbers k such that A000120(k) <= A001511(k).

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 28, 32, 34, 36, 40, 44, 48, 52, 56, 64, 66, 68, 72, 76, 80, 84, 88, 96, 100, 104, 112, 120, 128, 130, 132, 136, 140, 144, 148, 152, 160, 164, 168, 176, 184, 192, 196, 200, 208, 216, 224, 232, 240, 256, 258, 260, 264, 268

Offset: 1

Mikhail Kurkov, Mar 14 2024

It appears that this sequence is obtained when ordering Schreier sets as explained in the Bird link. See decM(n) PARI code. - Michel Marcus, May 31 2024
That is correct since the binary representation of these numbers can be put into 1-to-1 correspondence with Schreier sets, which satisfy |X| <= min X, using the indicator function of X as the bits (starting from the right, LSB). The reason is that A000120 then computes |X| and A001511 computes min X. For example, the Schreier set X = {2, 5} can be mapped to 10010_2 = 18. - Michael S. Branicky, May 31 2024
From David A. Corneth, May 31 2024: (Start)
If k is in the sequence then so is 2*k.
a(A000045(k)) = 2^(k-2) for k >= 2. (End)
Apart from a(1), all terms are even. - Paolo Xausa, May 31 2024
Zeckendorf representation of n with rewrite 0 -> 0, {0, 1} -> 1 and k-1 zeros appended to the right side (where k is the number of ones in the given representation) and then interpreted as binary expansion is the same as a(n) (see the first formula). - Mikhail Kurkov, Oct 21 2024

Michel Marcus, Table of n, a(n) for n = 1..10945
Alistair Bird, Jozef Schreier, Schreier sets and the Fibonacci sequence, Out Of The Norm blog, May 13 2012.
Vaclav Kotesovec, Plot of log(a(n))/log(n) for n = 2..2129243
Vaclav Kotesovec, Plot of a(n) / 2^(log(sqrt(5)*n)/log((1 + sqrt(5))/2) - 2) for n = 2..2129243

Cf. A000045, A000120, A001316, A001511, A003849, A005206, A007895, A048679, A066628, A072649, A213911.
Cf. A355489, A373345, A373347 (complement), A373557.
Cf. A104287.

filter:= proc(n) convert(convert(n,base,2),`+`) <= 1+padic:-ordp(n,2) end proc:
select(filter, [1,seq(i,i=2..1000,2)]); # Robert Israel, Oct 20 2024

Join[{1}, Select[Range[2, 1000, 2], DigitSum[#, 2] <= IntegerExponent[#, 2] + 1 &]] (* Paolo Xausa, Aug 12 2025 *)

isok(n) = hammingweight(n) <= (valuation(n, 2) + 1)

M(n) = my(list=List()); for (i=1, n, forsubset(i, s, my(bOk = if (#s && (vecmax(s) == n), #s <= vecmin(s), 0)); if (bOk, listput(list, vecsort(Vec(s),,4))););); Vec(list);
decM(nn) = my(v = vector(nn, k, M(k)), list=List()); for (i=1, #v, my(vi = v[i]); for (j=1, #vi, my(s = vecsort(vi[j]), slist=List(), m = vecmax(s)); forstep(k=m, 1, -1, listput(slist, sign(vecsearch(s, k)))); listput(list, fromdigits(Vec(slist), 2)););); vecsort(Vec(list)); \\ Michel Marcus, May 31 2024

def ok(n): return n.bit_count() <= (-n&n).bit_length()
print([k for k in range(1, 300) if ok(k)]) # Michael S. Branicky, May 31 2024

# Assuming the list starts with 0.
def a():
    n = na = nb = 1
    while True:
        yield not(nb < (na - 1) << 1)
        nb, na = na, n.bit_count()
        n += 1
aList = a(); print([n for n in range(77) if next(aList)]) # Peter Luschny, Jun 07 2024

a(n) = b(n)*A001316(b(n))/2 where b(n) = A048679(n).
a(n) = Sum_{i=0..n-1} 2^A213911(i).
a(n) = 2^(A072649(n) - 1) + [c(n) > 0]*2*a(c(n)) where c(n) = A066628(n).
a(n) = 2*a(A005206(n)) - A003849(n)*2^A007895(n-1) for n > 1 with a(1) = 1.
Conjecture: lim sup_{n -> oo} log(a(n))/log(n) = log(2) / log((1 + sqrt(5))/2) = 1.440420090412556479... = A104287. - Vaclav Kotesovec, Aug 12 2025

A104324 The Fibonacci word over the nonnegative integers; or, the number of runs of identical bits in the binary Zeckendorf representation of n.

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 3, 4, 2, 3, 4, 4, 5, 2, 3, 4, 4, 5, 4, 5, 6, 2, 3, 4, 4, 5, 4, 5, 6, 4, 5, 6, 6, 7, 2, 3, 4, 4, 5, 4, 5, 6, 4, 5, 6, 6, 7, 4, 5, 6, 6, 7, 6, 7, 8, 2, 3, 4, 4, 5, 4, 5, 6, 4, 5, 6, 6, 7, 4, 5, 6, 6, 7, 6, 7, 8, 4, 5, 6, 6, 7, 6, 7, 8, 6, 7, 8, 8, 9, 2, 3, 4, 4, 5, 4, 5, 6, 4, 5, 6, 6, 7, 4, 5, 6, 6

Offset: 0

Ron Knott, Mar 01 2005

Image of 0 under repeated application of the morphism phi = {2i -> 2i,2i+1; 2i+1 -> 2i+2: i = 0,1,2,3,...}. - N. J. A. Sloane, Jun 30 2017
This sequence has some interesting fractal properties (plot it!).
First occurrence of k=0,1,2,... is at 0,1,2,4,7,12,20,33,54, ..., A000071(k+1): Fibonacci numbers - 1. - Robert G. Wilson v, Apr 25 2006
Read mod 2 gives the Fibonacci word A003849. The differences, halved, give A213911.

			14 = 13+1 as a sum of Fibonacci numbers = 100001(in Fibonacci base) using the least number of 1's (Zeckendorf Rep): it consists of 3 runs: one 1, four 0's, one 1, so a(14)=3.
This sequence may be broken up into blocks of lengths 1,1,2,3,5,8,... (the nonzero Fibonacci numbers). The first occurrence of a number indicates the start of a new block. The first few blocks are:
0,
1,
2,2,
3,2,3,
4,2,3,4,4,
5,2,3,4,4,5,4,5,
6,2,3,4,4,5,4,5,6,4,5,6,6,
7,2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6,7,6,7,
8,2,3,4,4,5,4,5,6,4,5,6,6,7,4,5,6,6,7,6,7,8,4,5,6,6,7,6,7,8,6,7,8,8,
... (see also A288576). -  _N. J. A. Sloane_, Jun 30 2017

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.

N. J. A. Sloane, Table of n, a(n) for n = 0..28656 [First 10000 terms from Reinhard Zumkeller]
Amy Glen, Jamie Simpson, and W. F. Smyth, More properties of the Fibonacci word on an infinite alphabet, arXiv:1710.02782 [math.CO], 2017.
Ron Knott, Using Fibonacci Numbers to Represent Whole Numbers
Casey Mongoven, Sonification of multiple Fibonacci-related sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.
Jiemeng Zhang, Zhixiong Wen, and Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), #P2.52.

Cf. A007895, A014417, A104325, A189920, A213676, A213911.
See also the Fibonacci word A003849.
For partial sums see A288575.
See A288576 for another view of the initial blocks.

import Data.List (group)
a104324 = length . map length . group . a213676_row
-- Reinhard Zumkeller, Mar 10 2013

with(combinat,fibonacci):fib:=fibonacci: zeckrep:=proc(N)local i,z,j,n;i:=2;z:=NULL;n:=N; while fib(i)<=n do i:=i+1 od;print(i=fib(i)); for j from i-1 by -1 to 2 do if n>=fib(j) then z:=z,1;n:=n-fib(j) else z:=z,0 fi od; [z] end proc: countruns:=proc(s)local i,c,elt;elt:=s[1];c:=1; for i from 2 to nops(s) do if s[i]<>s[i-1] then c:=c+1 fi od; c end proc: seq(countruns(zeckrep(n)),n=1..100);

f[n_Integer] := Block[{k = Ceiling[ Log[ GoldenRatio, n*Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; While[ fr[[1]] == 0, fr = Rest@fr]; Length@ Split@ fr]; Array[f, 105] (* Robert G. Wilson v, Apr 25 2006 *)
Nest[ReplaceAll[#, {t_ /; EvenQ[t] :> Sequence[t, t+1], t_ /; OddQ[t] :> t+1}] &, {0}, 10] (* Paolo Xausa, Apr 05 2024 *)

phi(n) = if (n%2, n+1, [n, n+1]);
vphi(v) = nv = []; for (k=1, #v, nv = concat(nv, phi(v[k]));); nv;
lista(nn) = {v = [0]; for (i=1, nn, v = vphi(v);); v;} \\ Michel Marcus, Oct 10 2017

a(n) = A007895(n) + A213911(n). - Reinhard Zumkeller, Mar 10 2013

Entry revised by N. J. A. Sloane, Jun 30 2017

A353654 Numbers whose binary expansion has the same number of trailing 0 bits as other 0 bits.

Original entry on oeis.org

1, 3, 7, 10, 15, 22, 26, 31, 36, 46, 54, 58, 63, 76, 84, 94, 100, 110, 118, 122, 127, 136, 156, 172, 180, 190, 204, 212, 222, 228, 238, 246, 250, 255, 280, 296, 316, 328, 348, 364, 372, 382, 392, 412, 428, 436, 446, 460, 468, 478, 484, 494, 502, 506, 511, 528, 568

Offset: 1

Mikhail Kurkov, Jul 15 2022

Numbers k such that A007814(k) = A086784(k).
To reproduce the sequence through itself, use the following rule: if binary 1xyz is a term then so are 11xyz and 10xyz0 (except for 1 alone where 100 is not a term).
The number of terms with bit length k is equal to Fibonacci(k-1) for k > 1.
Conjecture: 2*A247648(n-1) + 1 with rewrite 1 -> 1, 01 -> 0 applied to binary expansion is the same as a(n) without trailing 0 bits in binary.
Odd terms are positive Mersenne numbers (A000225), because there is no 0 in their binary expansion. - Bernard Schott, Oct 12 2022

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000045, A000120, A000523, A007814, A010056, A025480, A030109, A054429, A060142, A072649, A084471, A086784, A091892, A132665, A133512, A200650, A213911, A232559, A280514, A343152, A348366.
Cf. A356385 (first differences).
Subsequences with same number k of trailing 0 bits and other 0 bits: A000225 (k=0), 2*A190620 (k=1), 4*A357773 (k=2), 8*A360573 (k=3).

N:= 10: # for terms <= 2^N
S:= {1};
for d from 1 to N do
  for k from 0 to d/2-1 do
    B:= combinat:-choose([$k+1..d-2],k);
    S:= S union convert(map(proc(t) local s; 2^d - 2^k - add(2^(s),s=t) end proc,B),set);
od od:
sort(convert(S,list)); # Robert Israel, Sep 21 2023

Join[{1}, Select[Range[2, 600], IntegerExponent[#, 2] == Floor[Log2[# - 1]] - DigitCount[# - 1, 2, 1] &]] (* Amiram Eldar, Jul 16 2022 *)

isok(k) = if (k==1, 1, (logint(k-1, 2)-hammingweight(k-1) == valuation(k, 2))); \\ Michel Marcus, Jul 16 2022

from itertools import islice, count
def A353654_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:(m:=(~n & n-1).bit_length()) == bin(n>>m)[2:].count('0'),count(max(startvalue,1)))
A353654_list = list(islice(A353654_gen(),30)) # Chai Wah Wu, Oct 14 2022

a(n) = a(n-1) + A356385(n-1) for n > 1 with a(1) = 1.
Conjectured formulas: (Start)
a(n) = 2^g(n-1)*(h(n-1) + 2^A000523(h(n-1))*(2 - g(n-1))) for n > 2 with a(1) = 1, a(2) = 3 where f(n) = n - A130312(n), g(n) = [n > 2*f(n)] and where h(n) = a(f(n) + 1).
a(n) = 1 + 2^r(n-1) + Sum_{k=1..r(n-1)} (1 - g(s(n-1, k)))*2^(r(n-1) - k) for n > 1 with a(1) = 1 where r(n) = A072649(n) and where s(n, k) = f(s(n, k-1)) for n > 0, k > 1 with s(n, 1) = n.
a(n) = 2*(2 + Sum_{k=1..n-2} 2^(A213911(A280514(k)-1) + 1)) - 2^A200650(n) for n > 1 with a(1) = 1.
A025480(a(n)-1) = A348366(A343152(n-1)) for n > 1.
a(A000045(n)) = 2^(n-1) - 1 for n > 1. (End)

cp's OEIS Frontend

A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Extensions

A371176 Numbers k such that A000120(k) <= A001511(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A104324 The Fibonacci word over the nonnegative integers; or, the number of runs of identical bits in the binary Zeckendorf representation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A353654 Numbers whose binary expansion has the same number of trailing 0 bits as other 0 bits.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula