A035516 -id:A035516 - 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

A003622 The Wythoff compound sequence AA: a(n) = floor(n*phi^2) - 1, where phi = (1+sqrt(5))/2.

Original entry on oeis.org

1, 4, 6, 9, 12, 14, 17, 19, 22, 25, 27, 30, 33, 35, 38, 40, 43, 46, 48, 51, 53, 56, 59, 61, 64, 67, 69, 72, 74, 77, 80, 82, 85, 88, 90, 93, 95, 98, 101, 103, 106, 108, 111, 114, 116, 119, 122, 124, 127, 129, 132, 135, 137, 140, 142, 145, 148, 150, 153, 156, 158, 161, 163, 166

Offset: 1

N. J. A. Sloane, Mira Bernstein, Marc LeBrun

Also, integers with "odd" Zeckendorf expansions (end with ...+F_2 = ...+1) (Fibonacci-odd numbers); first column of Wythoff array A035513; from a 3-way splitting of positive integers. [Edited by Peter Munn, Sep 16 2022]
Also, numbers k such that A005206(k) = A005206(k+1). Also k such that A022342(A005206(k)) = k+1 (for all other k's this is k). - Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001
Also, positions of 1's in A139764, the smallest term in Zeckendorf representation of n. - John W. Layman, Aug 25 2011
From Amiram Eldar, Sep 03 2022: (Start)
Numbers with an odd number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is odd.
The asymptotic density of this sequence is 1 - 1/phi (A132338). (End)
{a(n)} is the unique monotonic sequence of positive integers such that {a(n)} and {b(n)}: b(n) = a(n) - n form a partition of the nonnegative integers. - Yifan Xie, Jan 25 2025

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 62.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.
C. Kimberling, "Stolarsky interspersions", Ars Combinatoria 39 (1995) 129-138.
D. R. Morrison, "A Stolarsky array of Wythoff pairs", in A Collection of Manuscripts Related to the Fibonacci Sequence. Fibonacci Assoc., Santa Clara, CA, 1980, pp. 134-136.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 10.
N. J. A. Sloane and Simon Plouffe, Encyclopedia of Integer Sequences, Academic Press, 1995: this sequence appears twice, as both M3277 and M3278.

A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (terms 1.1000 from T. D. Noe)
J.-P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, arXiv:1809.03424 [math.NT], 2018.
Jon Asier Bárcena-Petisco, Luis Martínez, María Merino, Juan Manuel Montoya, and Antonio Vera-López, Fibonacci-like partitions and their associated piecewise-defined permutations, arXiv:2503.19696 [math.CO], 2025. See p. 4.
A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 62.
Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012. - _N. J. A. Sloane_, Jun 10 2012
Aviezri S. Fraenkel, The Raleigh game, INTEGERS: Electronic Journal of Combinatorial Number Theory 7.2 (2007): A13, 10 pages. See Table 1.
Martin Griffiths, On a Matrix Arising from a Family of Iterated Self-Compositions, Journal of Integer Sequences, 18 (2015), Article 15.11.8.
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
Clark Kimberling, Interspersions.
Clark Kimberling, Complementary equations and Wythoff Sequences, JIS 11 (2008), Article 08.3.3.
Clark Kimberling, Lucas Representations of Positive Integers, J. Int. Seq., Vol. 23 (2020), Article 20.9.5.
Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
Clark Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
Johan Kok, Integer sequences with conjectured relation with certain graph parameters of the family of linear Jaco graphs, arXiv:2507.16500 [math.CO], 2025. See pp. 5-6.
L. Lindroos, A. Sills, and H. Wang, Odd fibbinary numbers and the golden ratio, Fib. Q., 52 (2014), 61-65.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See page 3.
Mathematics Stack Exchange, Golden ratio and floor function floor(phi^2*n) - floor(phi*floor(phi*n)) = 1.
M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.5.
N. J. A. Sloane, Classic Sequences
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Jiemeng Zhang, Zhixiong Wen, and Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), Article P2.52.

Positions of 1's in A003849.
Complement of A022342.
Cf. A066096, A139764, A035516, A026273, A104326, A132338, A356749.
The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

a003622 n = a003622_list !! (n-1)
a003622_list = filter ((elem 1) . a035516_row) [1..]
-- Reinhard Zumkeller, Mar 10 2013

A003622 := proc(n)
    n+floor(n*(1+sqrt(5))/2)-1 ;
end proc: # R. J. Mathar, Jan 25 2015
# Maple code for the Wythoff compound sequences, from N. J. A. Sloane, Mar 30 2016
# The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.
# Assume files out1, out2 contain lists of the terms in the base sequences A and B from their b-files
read out1; read out2; b[0]:=b1: b[1]:=b2:
w2:=(i,j,n)->b[i][b[j][n]];
w3:=(i,j,k,n)->b[i][b[j][b[k][n]]];
for i from 0 to 1 do
lprint("name=",i);
lprint([seq(b[i][n],n=1..100)]):
od:
for i from 0 to 1 do for j from 0 to 1 do
lprint("name=",i,j);
lprint([seq(w2(i,j,n),n=1..100)]);
od: od:
for i from 0 to 1 do for j from 0 to 1 do for k from 0 to 1 do
lprint("name=",i,j,k);
lprint([seq(w3(i,j,k,n),n=1..100)]);
od: od: od:

With[{c=GoldenRatio^2},Table[Floor[n c]-1,{n,70}]] (* Harvey P. Dale, Jun 11 2011 *)
Range[70]//Floor[#*GoldenRatio^2]-1& (* Waldemar Puszkarz, Oct 10 2017 *)

PARI
```
a(n)=floor(n*(sqrt(5)+3)/2)-1
```

a(n) = (sqrtint(n^2*5)+n*3)\2 - 1; \\ Michel Marcus, Sep 17 2022

from sympy import floor
from mpmath import phi
def a(n): return floor(n*phi**2) - 1 # Indranil Ghosh, Jun 09 2017

from math import isqrt
def A003622(n): return (n+isqrt(5*n**2)>>1)+n-1 # Chai Wah Wu, Aug 11 2022

a(n) = floor(n*phi) + n - 1. [Corrected by Jianing Song, Aug 18 2022]
a(n) = floor(floor(n*phi)*phi) = A000201(A000201(n)). [See the Mathematics Stack Exchange link for a proof of the equivalence of the definition. - Jianing Song, Aug 18 2022]
a(n) = 1 + A022342(1 + A022342(n)).
G.f.: 1 - (1-x)*Sum_{n>=1} x^a(n) = 1/1 + x/1 + x^2/1 + x^3/1 + x^5/1 + x^8/1 + ... + x^F(n)/1 + ... (continued fraction where F(n)=n-th Fibonacci number). - Paul D. Hanna, Aug 16 2002
a(n) = A001950(n) - 1. - Philippe Deléham, Apr 30 2004
a(n) = A022342(n) + n. - Philippe Deléham, May 03 2004
a(n) = a(n-1) + 2 + A005614(n-2); also a(n) =  a(n-1) + 1 + A001468(n-1). - A.H.M. Smeets, Apr 26 2024

A022342 Integers with "even" Zeckendorf expansions (do not end with ...+F_2 = ...+1) (the Fibonacci-even numbers); also, apart from first term, a(n) = Fibonacci successor to n-1.

Original entry on oeis.org

0, 2, 3, 5, 7, 8, 10, 11, 13, 15, 16, 18, 20, 21, 23, 24, 26, 28, 29, 31, 32, 34, 36, 37, 39, 41, 42, 44, 45, 47, 49, 50, 52, 54, 55, 57, 58, 60, 62, 63, 65, 66, 68, 70, 71, 73, 75, 76, 78, 79, 81, 83, 84, 86, 87, 89, 91, 92, 94, 96, 97, 99, 100, 102, 104, 105, 107

Offset: 1

Marc LeBrun

The Zeckendorf expansion of n is obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains; for example, 100 = 89 + 8 + 3.
The Fibonacci successor to n is found by replacing each F_i in the Zeckendorf expansion by F_{i+1}; for example, the successor to 100 is 144 + 13 + 5 = 162.
If k appears, k + (rank of k) does not (10 is the 7th term in the sequence but 10 + 7 = 17 is not a term of the sequence). - Benoit Cloitre, Jun 18 2002
From Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001: (Start)
a(n) = Sum_{k in A_n} F_{k+1}, where a(n)= Sum_{k in A_n} F_k is the (unique) expression of n as a sum of "noncontiguous" Fibonacci numbers (with index >= 2).
a(10^n) gives the first few digits of g = (sqrt(5)+1)/2.
The sequences given by b(n+1) = a(b(n)) obey the general recursion law of Fibonacci numbers. In particular the (sub)sequence (of a(-)) yielded by a starting value of 2=a(1), is the sequence of Fibonacci numbers >= 2. Starting points of all such subsequences are given by A035336.
a(n) = floor(phi*n+1/phi); phi = (sqrt(5)+1)/2. a(F_n)=F_{n+1} if F_n is the n-th Fibonacci number.
(End)
From Amiram Eldar, Sep 03 2022: (Start)
Numbers with an even number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is even.
The asymptotic density of this sequence is 1/phi (A094214). (End)

			The successors to 1, 2, 3, 4=3+1 are 2, 3, 5, 7=5+2.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.
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.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Joerg Arndt, Matters Computational (The Fxtbook)
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 3, 6.
M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
Jeffrey Shallit, The Hurt-Sada Array and Zeckendorf Representations, arXiv:2501.08823 [math.NT], 2025. See p. 2.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Classic Sequences
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Jiemeng Zhang, Zhixiong Wen, and Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), Article P2.52.

Positions of 0's in A003849.
Complement of A003622.
Cf. A000201, A005206, A035336, A066096, A001950, A062879, A035516, A026274.
Cf. A035612, A094214, A104326, A356749.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

a022342 n = a022342_list !! (n-1)
a022342_list = filter ((notElem 1) . a035516_row) [0..]
-- Reinhard Zumkeller, Mar 10 2013

[Floor(n*(Sqrt(5)+1)/2)-1: n in [1..100]]; // Vincenzo Librandi, Feb 16 2015

A022342 := proc(n)
      local g;
      g := (1+sqrt(5))/2 ;
    floor(n*g)-1 ;
end proc: # R. J. Mathar, Aug 04 2013

With[{t=GoldenRatio^2},Table[Floor[n*t]-n-1,{n,70}]] (* Harvey P. Dale, Aug 08 2012 *)

PARI
```
a(n)=floor(n*(sqrt(5)+1)/2)-1
```

a(n)=(sqrtint(5*n^2)+n-2)\2 \\ Charles R Greathouse IV, Feb 27 2014

from math import isqrt
def A022342(n): return (n+isqrt(5*n**2)>>1)-1 # Chai Wah Wu, Aug 17 2022

a(n) = floor(n*phi^2) - n - 1 = floor(n*phi) - 1 = A000201(n) - 1, where phi is the golden ratio.
a(n) = A003622(n) - n. - Philippe Deléham, May 03 2004
a(n+1) = A022290(2*A003714(n)). - R. J. Mathar, Jan 31 2015
For n > 1: A035612(a(n)) > 1. - Reinhard Zumkeller, Feb 03 2015
a(n) = A000201(n) - 1. First differences are given in A014675 (or A001468, ignoring its first term). - M. F. Hasler, Oct 13 2017
a(n) = a(n-1) + 1 + A005614(n-2) for n > 1; also  a(n) = a(n-1) + A014675(n-2) = a(n-1) + A001468(n-1). - A.H.M. Smeets, Apr 26 2024

Name edited by Peter Munn, Dec 07 2021

A035517 Triangular array read by rows, formed from Zeckendorf expansion of integers: repeatedly subtract the largest Fibonacci number you can until nothing remains. Row n give Z. expansion of n.

Original entry on oeis.org

0, 1, 2, 3, 1, 3, 5, 1, 5, 2, 5, 8, 1, 8, 2, 8, 3, 8, 1, 3, 8, 13, 1, 13, 2, 13, 3, 13, 1, 3, 13, 5, 13, 1, 5, 13, 2, 5, 13, 21, 1, 21, 2, 21, 3, 21, 1, 3, 21, 5, 21, 1, 5, 21, 2, 5, 21, 8, 21, 1, 8, 21, 2, 8, 21, 3, 8, 21, 1, 3, 8, 21, 34, 1, 34, 2, 34, 3, 34, 1, 3, 34, 5, 34, 1, 5, 34, 2, 5, 34

Offset: 0

N. J. A. Sloane

Row n has A007895(n) terms.

With the 2nd Maple program, B(n) yields the number of terms in the Zeckendorf expansion of n, while Z(n) yields the expansion itself. For example, B(100)=3 and Z(100)=3, 8, 89. [Emeric Deutsch, Jul 05 2010]

			0=0; 1=1; 2=2; 3=3; 4=1+3; 5=5; 6=1+5; 7=2+5; 8=8; 9=1+8; 10=2+8; ... so triangle begins
  0;
  1;
  2;
  3;
  1, 3;
  5;
  1, 5;
  2, 5;
  8;
  1, 8;
  2, 8;
  3, 8;
  1, 3, 8;

Zeckendorf, E., 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, Rows n = 0..1000 of triangle, flattened
D. E. Knuth, Fibonacci multiplication, Appl. Math. Lett. 1 (1988), 57-60.
N. J. A. Sloane, Classic Sequences

Cf. A014417, A007895, A035514, A035515, A035516.

a035517 n k = a035517_tabf !! n !! k
a035517_row n = a035517_tabf !! n
a035517_tabf = map reverse a035516_tabf
-- Reinhard Zumkeller, Mar 10 2013

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: F := proc (n) local i: for i while fibonacci(i) <= n do fibonacci(i) end do end proc: Z := proc (n) local j, z: for j to B(n) do z[j] := F(n-add(z[i], i = 1 .. j-1)) end do: seq(z[B(n)+1-k], k = 1 .. B(n)) end proc: for n to 25 do Z(n) end do;
# Emeric Deutsch, Jul 05 2010
# yields sequence in triangular form; end of this Maple program

f[n_] := (k=1; ff={}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff,1]); ro[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]; Flatten[ro /@ Range[0, 42]] (* Jean-François Alcover, Jul 23 2011 *)

zeck, fib = [], [0, 1]
from itertools import count, islice
def agen(): # generator of terms
    for r in count(0):
        while fib[-1] < r:
            fib.append(fib[-2] + fib[-1])
        i = 1
        while fib[-i] > r: i += 1
        bigfib = fib[-i]
        zeck.append( ([] if r == bigfib else zeck[r-bigfib]) + [bigfib] )
        yield from zeck[r]  # row r of the triangle
print(list(islice(agen(), 90))) # Michael S. Branicky, Apr 04 2022

More terms from James Sellers, Dec 13 1999

A087172 Greatest Fibonacci number that does not exceed n.

Original entry on oeis.org

1, 2, 3, 3, 5, 5, 5, 8, 8, 8, 8, 8, 13, 13, 13, 13, 13, 13, 13, 13, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55

Offset: 1

Sam Alexander, Oct 19 2003

Also the largest term in Zeckendorf representation of n; starting at Fibonacci positions the sequence is repeated again and again in A107017: A107017(A000045(n)+k) = a(k) with 0 < k < A000045(n-1). - Reinhard Zumkeller, May 09 2005

Fibonacci(n) occurs Fibonacci(n-1) times, for n >= 2. - Benoit Cloitre, Dec 15 2022

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fibonacci Number.

Cf. A000045, A007895, A035516, A035517, A066628, A107017, A130233, A130234, A256654.

Partial sums: A130473.

a087172 = head . a035516_row -- Reinhard Zumkeller, Mar 10 2013

with(combinat):
A087172 := proc (n) local j: for j while fibonacci(j) <= n do fibonacci(j) end do: fibonacci(j-1) end proc:
seq(A087172(n), n = 1 .. 40); # Emeric Deutsch, Nov 11 2014
# Alternative
N:= 100: # to get a(n) for n from 1 to N
Fibs:= [seq(combinat:-fibonacci(i), i = 1 .. ceil(log[(1 + sqrt(5))/2](sqrt(5)*N)))]:
A:= Vector(N):
for i from 1 to nops(Fibs)-1 do
  A[Fibs[i] .. min(N,Fibs[i+1]-1)]:= Fibs[i]
od:
convert(A,list); # Robert Israel, Nov 11 2014

With[{rf=Reverse[Fibonacci[Range[10]]]},Flatten[Table[ Select[ rf,n>=#&, 1],{n,80}]]] (* Harvey P. Dale, Dec 08 2012 *)
Flatten[Map[ConstantArray[Fibonacci[#],Fibonacci[#-1]]&,Range[15]]] (* Peter J. C. Moses, May 02 2022 *)

a(n)=my(k=log(n)\log((1+sqrt(5))/2)); while(fibonacci(k)<=n, k++); fibonacci(k--) \\ Charles R Greathouse IV, Jul 24 2012

a(n) = Fibonacci(A130233(n)) = Fibonacci(A130234(n+1)-1). - Hieronymus Fischer, May 28 2007
a(n) = A035516(n, 0) = A035517(n, A007895(n)-1). - Reinhard Zumkeller, Mar 10 2013
a(n) = n - A066628(n). - Michel Marcus, Feb 02 2016
Sum_{n>=1} 1/a(n)^2 = Sum_{n>=1} Fibonacci(n)/Fibonacci(n+1)^2 = 1.7947486789... . - Amiram Eldar, Aug 16 2022

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

A003622 The Wythoff compound sequence AA: a(n) = floor(n*phi^2) - 1, where phi = (1+sqrt(5))/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A022342 Integers with "even" Zeckendorf expansions (do not end with ...+F_2 = ...+1) (the Fibonacci-even numbers); also, apart from first term, a(n) = Fibonacci successor to n-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A035517 Triangular array read by rows, formed from Zeckendorf expansion of integers: repeatedly subtract the largest Fibonacci number you can until nothing remains. Row n give Z. expansion of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Extensions

A087172 Greatest Fibonacci number that does not exceed n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple