A104326 -id:A104326 - cp's OEIS frontend

A003849 The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1

Offset: 0

N. J. A. Sloane

A Sturmian word.
Define strings S(0)=0, S(1)=01, S(n)=S(n-1)S(n-2); iterate; sequence is S(infinity). If the initial 0 is omitted from S(n) for n>0, we obtain A288582(n+1).
The 0's occur at positions in A022342 (i.e., A000201 - 1), the 1's at positions in A003622.
Replace each run (1;1) with (1;0) in the infinite Fibonacci word A005614 (and add 0 as prefix) A005614 begins: 1,0,1,1,0,1,0,1,1,0,1,1,... changing runs (1,1) with (1,0) produces 1,0,0,1,0,1,0,0,1,0,0,1,... - Benoit Cloitre, Nov 10 2003
Characteristic function of A003622. - Philippe Deléham, May 03 2004
The fraction of 0's in the first n terms approaches 1/phi (see for example Allouche and Shallit). - N. J. A. Sloane, Sep 24 2007
The limiting mean and variance of the first n terms are 2-phi and 2*phi-3, respectively. - Clark Kimberling, Mar 12 2014, Aug 16 2018
Let S(n) be defined as above. Then this sequence is S(1) + Sum_{n=0..} S(n), where the addition of strings represents concatenation. - Isaac Saffold, May 03 2019
The word is a concatenation of three runs: 0, 1, and 00. The limiting proportions of these are respectively 1 - phi/2, 1/2, and (phi - 1)/2. The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010
From Amiram Eldar, Mar 10 2021: (Start)
a(n) is the number of the trailing 0's in the dual Zeckendorf representation of (n+1) (A104326).
The asymptotic density of the occurrences of k (0 or 1) is 1/phi^(k+1), where phi is the golden ratio (A001622).
The asymptotic mean of this sequence is 1/phi^2 (A132338). (End)

			The word is 010010100100101001010010010100...
Over the alphabet {a,b} this is a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
Jean Berstel, Fibonacci words—a survey, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc. - see p. 64.
Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337. [See A317208 for a link.]
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

N. J. A. Sloane, Table of n, a(n) for n = 0..10945
A. G. M. Ahmed, AA Weaving, in Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture.
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
P. Arnoux and E. Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Galyna Barabash, Yaroslav Kholyavka, and Iryna Tytar, Periodic words connected with the Lucas numbers, Visnyk of the Lviv Univ. Series Mech. Math. (2017), Issue 84, 62-66.
Jean Berstel, Home Page
J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
Bryce Emerson Blackham, Subtraction Games: Range and Strict Periodicity, Master's thesis, 2018.
Cristian Cobeli and Alexandru Zaharescu, A bias parity question for Sturmian words, arXiv:1811.06509 [math.NT], 2018.
Fabien Durand, Julien Leroy, and Gwenaël Richomme, Do the Properties of an S-adic Representation Determine Factor Complexity?, Journal of Integer Sequences, Vol. 16 (2013), #13.2.6.
J. Endrullis, D. Hendriks and J. W. Klop, Degrees of streams.
S. Ferenczi, Complexity of sequences and dynamical systems, Discrete Math., 206 (1999), 145-154.
L. Goldberg and A. V. Fraenkel, Patterns in the generalized Fibonacci word, applied to games, Discrete Math., 341 2018 1675-1687.
J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
Andreas M. Hinz and Paul K. Stockmeyer, Discovering Fibonacci Numbers, Fibonacci Words, and a Fibonacci Fractal in the Tower of Hanoi, The Fibonacci Quarterly (2019) Vol. 57, No. 5, 72-83.
A. Hof, O. Knill and B. Simon, Singular continuous spectrum for palindromic Schroedinger operators, Commun. Math. Phys. 174 (1995), 149-159.
Tyler Hoffman and B. Steinhurst, Hausdorff Dimension of Generalized Fibonacci Word Fractals, arXiv preprint arXiv:1601.04786 [math.MG], 2016.
T. Karki, A. Lacroix, and M. Rigo, On the recognizability of self-generating sets, JIS 13 (2010) #10.2.2.
Clark Kimberling, A Self-Generating Set and the Golden Mean, J. Integer Sequences, 3 (2000), #00.2.8.
Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
Eve Kivivuori, Implementing, analyzing, and benchmarking the Relative Lempel-Ziv compression algorithm, Master's Thesis, Univ. Helsinki (Finland 2023).
M. Lothaire, Algebraic Combinatorics on Words, Cambridge, 2002, see p. 41, etc.
Frédéric Mansuy, "Palindromic" and "Quasi-crystalline" characteristics of the sequence and Fibonacci words., hal-02082456, 2019.
Douglas M. McKenna, On a Better Golden Rectangle (That Is Not 61.8033...% Useless!), Proceedings of Bridges (2018), 187-194.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
F. Mignosi, A. Restivo, and M. Sciortino, Words and forbidden factors, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096) - From _N. J. A. Sloane_, Jul 10 2012
Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013
Kerry Mitchell, Spirolateral image for this sequence [taken, with permission, from the Spirolateral-Type Images from Integer Sequences article]
T. D. Noe, The first 1652 subwords, including leading zeros.
Saúl Pilatowsky-Cameo, Soonwon Choi, and Wen Wei Ho, Critically slow Hilbert-space ergodicity in quantum morphic drives, arXiv:2502.06936 [quant-ph], 2025. See p. 15.
Giuseppe Pirillo, Fibonacci numbers and words, Discrete Math. 173 (1997), no. 1-3, 197--207. MR1468849 (98g:68135)
J. L. Ramírez and G. N. Rubiano, Properties and Generalizations of the Fibonacci Word Fractal, The Mathematica Journal, Vol. 16 (2014).
José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012.
Aayush Rajasekaran, Using Automata Theory to Solve Problems in Additive Number Theory, MS thesis, University of Waterloo, 2018.
Aayush Rajasekaran, Narad Rampersad, and Jeffrey Shallit, Overpals, Underlaps, and Underpals, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Golden Ratio
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.
Index entries for sequences that are fixed points of mappings
Index entries for characteristic functions

There are several versions of this sequence in the OEIS. This one and A003842 are probably the most important. See also A008352, A076662, A288581, A288582.
Binary complement of A005614. Cf. A014675, A036299, A003714, A014417, A096268, A096270, A133235, A182028, A213975.
Positions of 1's gives A003622.
Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.
Cf. A001622, A104326, A132338.
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

a003849 n = a003849_list !! n
a003849_list = tail $ concat fws where
   fws = [1] : [0] : (zipWith (++) fws $ tail fws)
-- Reinhard Zumkeller, Nov 01 2013, Apr 07 2012

t1:=[ n le 2 select ["0","0,1"][n] else Self(n-1) cat "," cat Self(n-2) : n in [1..12]]; t1[12];

z := proc(m) option remember; if m=0 then [0] elif m=1 then [0,1] else [op(z(m-1)),op(z(m-2))]; fi; end; z(12);
M:=19; S[0]:=`0`; S[1]:=`01`; for n from 2 to M do S[n]:=cat(S[n-1], S[n-2]); od:
t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i-1,substring(t0,i..i)); od: # N. J. A. Sloane, Nov 01 2006

Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 10] (* Robert G. Wilson v, Mar 05 2005 *)
Flatten[Nest[{#, #[[1]]} &, {0, 1}, 9]] (* IWABUCHI Yu(u)ki, Oct 23 2013 *)
Table[Floor[(n + 2) #] - Floor[(n + 1) #], {n, 0, 120}] &[2 - GoldenRatio] (* Michael De Vlieger, Aug 15 2016 *)
SubstitutionSystem[{0->{0,1},1->{0}},{0},{10}][[1]] (* Harvey P. Dale, Dec 20 2021 *)

a(n)=my(k=2);while(fibonacci(k)<=n,k++);while(n>1,while(fibonacci(k--)>n,); n-=fibonacci(k)); n==1 \\ Charles R Greathouse IV, Feb 03 2014

M3849=[2,2,1,0]/*L(k),S(k),L(k-1),S(k-1)*/; A003849(n)={while(n>M3849[1],M3849=vecextract(M3849,[1,2,1,2])+[M3849[3],M3849[4]<M. F. Hasler, Apr 07 2021

def fib(n):
    """Return the concatenation of A003849(0..F-1) where F is the smallest
       Fibonacci number > n, so that the result contains a(n) at index n."""
    a, b = '10'
    while len(b)<=n:
        a, b = b, b + a
    return b # Robert FERREOL, Apr 15 2016, edited by M. F. Hasler, Apr 07 2021

from math import isqrt
def A003849(n): return 2-(n+2+isqrt(m:=5*(n+2)**2)>>1)+(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 25 2022

a(n) = floor((n+2)*r) - floor((n+1)*r) where r=phi/(1+2*phi) and phi is the Golden Ratio. - Benoit Cloitre, Nov 10 2003
a(n) = A003714(n) mod 2 = A014417(n) mod 2. - Philippe Deléham, Jan 04 2004
The first formula by Cloitre is just one of an infinite family of formulas. Using phi^2=1+phi, it follows that r=phi/(1+2*phi)=2-phi. Then from floor(-x)=-floor(x)-1 for non-integer x, it follows that a(n)=2-A014675(n)=2-(floor((n+2)* phi)-floor((n+1)*phi)). - Michel Dekking, Aug 27 2016
a(n) = 1 - A096270(n+1), i.e., A096270 is the complement of this sequence. - A.H.M. Smeets, Mar 31 2024

Revised by N. J. A. Sloane, Jul 03 2012

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

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

A001911 a(n) = Fibonacci(n+3) - 2.

Original entry on oeis.org

0, 1, 3, 6, 11, 19, 32, 53, 87, 142, 231, 375, 608, 985, 1595, 2582, 4179, 6763, 10944, 17709, 28655, 46366, 75023, 121391, 196416, 317809, 514227, 832038, 1346267, 2178307, 3524576, 5702885, 9227463, 14930350, 24157815, 39088167, 63245984

Offset: 0

N. J. A. Sloane

This is the sequence A(0,1;1,1;2) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 17 2010
Ternary words of length n - 1 with subwords (0, 1), (0, 2) and (2, 2) not allowed. - Olivier Gérard, Aug 28 2012
For subsets of (1, 2, 3, 5, 8, 13, ...) Fibonacci Maximal terms (Cf. A181631) equals the number of leading 1's per subset. For example, (7-11) in Fibonacci Maximal = (1010, 1011, 1101, 1110, 1111), numbers of leading 1's = (1 + 1 + 2 + 3 + 4) = 11 = a(4) = row 4 of triangle A181631. - Gary W. Adamson, Nov 02 2010
As in our 2009 paper, we use two types of Fibonacci trees: - Ta: Fibonacci analog of binomial trees; Tb: Binary Fibonacci trees. Let D(r(k)) be the sum over all distances of the form d(r, x), across all vertices x of the tree rooted at r of order k. Ignoring r, but overloading, let D(a(k)) and D(b(k)) be the distance sums for the Fibonacci trees Ta and Tb respectively of the order k. Using the sum-of-product form in Equations (18) and (21) in our paper it follows that F(k+4) - 2 = D(a(k+1)) - D(b(k-1)). - K.V.Iyer and P. Venkata Subba Reddy, Apr 30 2011
a(n) is the length of the n-th palindromic prefix of the infinite Fibonacci word A003849. - Dimitri Hendriks, May 19 2014
The first k terms of the infinite Fibonacci word A014675 are palindromic if and only if k is a positive term of this sequence. - Clark Kimberling, Jul 14 2014
Can be expressed in terms of a rule similar to Recamán's sequence (A005132). Instead of following the Recamán rule "subtract if possible, otherwise add", this sequence follows the rule "If subtraction is possible, do nothing; otherwise add." For example when at the fourth term, 6, it is possible to subtract 4 (giving 2 which is not in {0, 1, 3, 6}) so nothing is done with 4. It is not possible to subtract 5 (6-5=1, which is in {0, 1, 3, 6}), so it is added, resulting in 11. - Matthew Malone, Jan 03 2020
For n>=1, a(n) is the maximum number of vertices (Moore bound) of a (1,1)-regular mixed graph with diameter n-1. - Miquel A. Fiol, Jun 24 2024
Repunits in the lazy Fibonacci representation (A104326), and which is the first row of array A372501. - A.H.M. Smeets, Jun 25 2025

			G.f. = x + 3*x^2 + 6*x^3 + 11*x^4 + 19*x^5 + 32*x^6 + 53*x^7 + 87*x^8 + ...

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 233.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Charles R Greathouse IV, Table of n, a(n) for n = 0..4783 (next term has 1001 digits)
Stefano Bilotta, Variable-length Non-overlapping Codes, arXiv preprint arXiv:1605.03785 [cs.IT], 2016.
D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
C. Dalfó, G. Erskine, G. Exoo, M. A. Fiol, N. López, A. Messegué, and J. Tuite, On large regular (1,1,k)-mixed graphs, Discrete Appl. Math. 356 (2024), 209-228.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
K. Viswanathan Iyer and K. R. Uday Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432 [cs.DM], 2009. (Corrigendum: Eq.(23) to be corrected as follows on the right-side: in the fourth term F(k)-1 should be replaced by F(k); a term F(k)*F(K+1)-1 is to be included; pointed out by Emeric Deutsch).
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
D. G. Rogers, An application of renewal sequences to the dimer problem, pp. 142-153 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences, 2010.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000032, A000045, A101220, A104326, A108617, A181631, A372501.
Cf. A001611, A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616. [Added by N. J. A. Sloane, Jun 25 2010 in response to a comment from Aviezri S. Fraenkel]
Partial sums of A000045(n+1).
Right-hand column 3 of triangle A011794.
See also A165910.
Subsequence of A226538.
Column k=3 of A261019.

a001911 n = a001911_list !! n
a001911_list = 0 : 1 : map (+ 2) (zipWith (+) a001911_list $ tail a001911_list)
-- Reinhard Zumkeller, Jun 18 2013

[(Fibonacci(n+3))-2: n in [0..85]]; // Vincenzo Librandi, Apr 23 2011

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=a[n-1]+a[n-2]+2 od: seq(a[n],n=0..50); # Miklos Kristof, Mar 09 2005
A001911:=(1+z)/(z-1)/(z**2+z-1); # Simon Plouffe in his 1992 dissertation with another offset
a:= n-> (Matrix([[0,-1,1]]). Matrix([[1,1,0], [1,0,0], [2,0,1]])^n)[1,1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 24 2008

Table[Fibonacci[n+3] -2, {n,0,50}] (* Vladimir Joseph Stephan Orlovsky, Nov 19 2010 *)
LinearRecurrence[{2,0,-1}, {0,1,3}, 40] (* Harvey P. Dale, Jun 06 2011 *)
Fibonacci[Range[3,40]]-2 (* Harvey P. Dale, Jun 28 2015 *)

a(n)=fibonacci(n+3)-2 \\ Charles R Greathouse IV, Mar 14 2012

[fibonacci(n+3)-2 for n in range(60)] # G. C. Greubel, Oct 21 2024

From Michael Somos, Jun 09 1999: (Start)
a(n) = A000045(n+3) - 2.
a(n) = a(n-1) + a(n-2) + 2, a(0) = 0, a(1) = 1. (End)
G.f.: x*(1+x)/((1-x)*(1-x-x^2)).
Sum of consecutive pairs of A000071 (partial sums of Fibonacci numbers). - Paul Barry, Apr 17 2004
a(n) = A101220(2, 1, n). - Ross La Haye, Jan 28 2005
a(n) = A108617(n+1, 2) = A108617(n+1, n-1) for n > 0. - Reinhard Zumkeller, Jun 12 2005
a(n) = term (1,1) in the 1 X 3 matrix [0,-1,1].[1,1,0; 1,0,0; 2,0,1]^n. - Alois P. Heinz, Jul 24 2008
a(0) = 0, a(1) = 1, a(2) = 3, a(n) = 2*a(n-1)-a(n-3). - Harvey P. Dale, Jun 06 2011
Eigensequence of an infinite lower triangular matrix with the natural numbers as the left border and (1, 0, 1, 0, ...) in all other columns. - Gary W. Adamson, Jan 30 2012
a(n) = (-2+(2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5))+(1+sqrt(5))^n*(2+sqrt(5))))/sqrt(5)). - Colin Barker, May 12 2016
a(n) = A000032(6+n)-1 mod A000045(6+n). - Mario C. Enriquez, Apr 01 2017
E.g.f.: 2*exp(x/2)*(5*cosh(sqrt(5)*x/2) + 2*sqrt(5)*sinh(sqrt(5)*x/2))/5 - 2*exp(x). - Stefano Spezia, May 08 2022

More terms and better description from Michael Somos

A003754 Numbers with no adjacent 0's in binary expansion.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 21, 22, 23, 26, 27, 29, 30, 31, 42, 43, 45, 46, 47, 53, 54, 55, 58, 59, 61, 62, 63, 85, 86, 87, 90, 91, 93, 94, 95, 106, 107, 109, 110, 111, 117, 118, 119, 122, 123, 125, 126, 127, 170, 171, 173, 174, 175, 181

Offset: 1

N. J. A. Sloane

Theorem (J.-P. Allouche, J. Shallit, G. Skordev): This sequence = A052499 - 1.
Ahnentafel numbers of ancestors contributing the X-chromosome to a female. A280873 gives the male inheritance. - Floris Strijbos, Jan 09 2017 [Equivalence with this sequence pointed out by John Blythe Dobson, May 09 2018]
The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence lists all numbers k such that the k-th composition in standard order has no parts greater than two. See the corresponding example below. - Gus Wiseman, Apr 04 2020
The binary representation of a(n+1) has the same string of digits as the lazy Fibonacci (also known as dual Zeckendorf) representation of n that uses 0s and 1s. (The "+1" is essentially an adjustment for the offset of this sequence.) - Peter Munn, Sep 06 2022

			21 is in the sequence because 21 = 10101_2. '10101' has no '00' present in it. - _Indranil Ghosh_, Feb 11 2017
From _Gus Wiseman_, Apr 04 2020: (Start)
The terms together with the corresponding compositions begin:
    0: ()            30: (1,1,1,2)         90: (2,1,2,2)
    1: (1)           31: (1,1,1,1,1)       91: (2,1,2,1,1)
    2: (2)           42: (2,2,2)           93: (2,1,1,2,1)
    3: (1,1)         43: (2,2,1,1)         94: (2,1,1,1,2)
    5: (2,1)         45: (2,1,2,1)         95: (2,1,1,1,1,1)
    6: (1,2)         46: (2,1,1,2)        106: (1,2,2,2)
    7: (1,1,1)       47: (2,1,1,1,1)      107: (1,2,2,1,1)
   10: (2,2)         53: (1,2,2,1)        109: (1,2,1,2,1)
   11: (2,1,1)       54: (1,2,1,2)        110: (1,2,1,1,2)
   13: (1,2,1)       55: (1,2,1,1,1)      111: (1,2,1,1,1,1)
   14: (1,1,2)       58: (1,1,2,2)        117: (1,1,2,2,1)
   15: (1,1,1,1)     59: (1,1,2,1,1)      118: (1,1,2,1,2)
   21: (2,2,1)       61: (1,1,1,2,1)      119: (1,1,2,1,1,1)
   22: (2,1,2)       62: (1,1,1,1,2)      122: (1,1,1,2,2)
   23: (2,1,1,1)     63: (1,1,1,1,1,1)    123: (1,1,1,2,1,1)
   26: (1,2,2)       85: (2,2,2,1)        125: (1,1,1,1,2,1)
   27: (1,2,1,1)     86: (2,2,1,2)        126: (1,1,1,1,1,2)
   29: (1,1,2,1)     87: (2,2,1,1,1)      127: (1,1,1,1,1,1,1)
(End)

Indranil Ghosh, Table of n, a(n) for n = 1..50000 (terms 1..1000 from T. D. Noe)
J.-P. Allouche, J. Shallit and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math., Vol. 292, No. 1-3 (2005), pp. 1-15.
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.5.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Tomi Kärki, Anne Lacroix, and Michel Rigo, On the recognizability of self-generating sets, Journal of Integer Sequences, Vol. 13 (2010), Article 10.2.2.
Wikipedia, Ahnentafel.
Witzel, Stefan On panel-regular ~A2 lattices Geom. Dedicata 191, 85-135 (2017).
Index entries for 2-automatic sequences.
Index entries for sequences related to binary expansion of n.

A104326(n) = A007088(a(n)); A023416(a(n)) = A087116(a(n)); A107782(a(n)) = 0; A107345(a(n)) = 1; A107359(n) = a(n+1) - a(n); a(A001911(n)) = A000225(n); a(A000071(n+2)) = A000975(n). - Reinhard Zumkeller, May 25 2005
Cf. A003796 (no 000), A004745 (no 001), A004746 (no 010), A004744 (no 011), A004742 (no 101), A004743 (no 110), A003726 (no 111).
Complement of A004753.
Cf. A023705, A196168, A280873.
Positions of numbers <= 2 in A333766 (see this and A066099 for other sequences about compositions in standard order).
Cf. A318928.

a003754 n = a003754_list !! (n-1)
a003754_list = filter f [0..] where
   f x = x == 0 || x `mod` 4 > 0 && f (x `div` 2)
-- Reinhard Zumkeller, Dec 07 2012, Oct 19 2011

isA003754 := proc(n) local bdgs ; bdgs := convert(n,base,2) ; for i from 2 to nops(bdgs) do if op(i,bdgs)=0 and op(i-1,bdgs)= 0 then return false; end if; end do; return true; end proc:
A003754 := proc(n) option remember; if n= 1 then 0; else for a from procname(n-1)+1 do if isA003754(a) then return a; end if; end do: end if; end proc:
# R. J. Mathar, Oct 23 2010

Select[ Range[0, 200], !MatchQ[ IntegerDigits[#, 2], {_, 0, 0, _}]&] (* Jean-François Alcover, Oct 25 2011 *)
Select[Range[0,200],SequenceCount[IntegerDigits[#,2],{0,0}]==0&] (* The program uses the SequenceCount function from Mathematica version 10 *) (* Harvey P. Dale, May 21 2015 *)

is(n)=n=bitor(n,n>>1)+1; n>>=valuation(n,2); n==1 \\ Charles R Greathouse IV, Feb 06 2017

i=0
while i<=500:
    if "00" not in bin(i)[2:]:
        print(str(i), end=',')
    i+=1 # Indranil Ghosh, Feb 11 2017

Sum_{n>=2} 1/a(n) = 4.356588498070498826084131338899394678478395568880140707240875371925764128502... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

Removed "2" from the name, because, for example, one could argue that 10001 has 3 adjacent zeros, not 2. - Gus Wiseman, Apr 04 2020

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

A023610 Convolution of Fibonacci numbers and {F(2), F(3), F(4), ...}.

Original entry on oeis.org

1, 3, 7, 15, 30, 58, 109, 201, 365, 655, 1164, 2052, 3593, 6255, 10835, 18687, 32106, 54974, 93845, 159765, 271321, 459743, 777432, 1312200, 2211025, 3719643, 6248479, 10482351, 17562870, 29391490, 49132669, 82048737, 136884293, 228160495, 379975140, 632293452

Offset: 0

Clark Kimberling

a(n-2) + 1 is the number of (3412,1243)-, (3412,2134)- and (3412,1324)-avoiding involutions in S_n, n>1. - Ralf Stephan, Jul 06 2003
The number of terms in all ordered partitions of (n+1) using only ones and twos. For example, a(3)=15 because there are 15 terms in 1+1+1+1;2+1+1;1+2+1;1+1+2;2+2 - Geoffrey Critzer, Apr 07 2008
a(n) is the number of n-matchings in the graph obtained by a zig-zag triangulation of a convex (2n+1)-gon. Example: a(2)=7 because in the triangulation of the convex pentagon ABCDEA with diagonals AD and AC we have 7 2-matchings: {AB,CD},{AB,DE},{BC,AD},{BC,DE},{BC,EA},{CD,EA} and {DE,AC}. - Emeric Deutsch, Dec 25 2004
Partial sums of A029907. First differences of A002940. - Peter Bala, Oct 24 2007
Equals row sums of triangle A144154. - Gary W. Adamson, Sep 12 2008
Equals the number of 1's in Fibonacci Maximal notation for subsets of
(1, 2, 3, 5, 8, 13, ...) terms. For example (cf. A181630): 4, 5, and 6 are the 3 terms 101, 110, and 111 in Fibonacci Maximal. Total number of 1's for those terms = 7 = a(2). - Gary W. Adamson, Nov 02 2010
a(n) is half the number of strokes needed to draw all the domino tilings of a 2 X (n+2) rectangle. - Roberto Tauraso, Mar 15 2014
a(n) is the total number of 1's in all (n+1)-bit dual Zeckendorf representations of integers (A104326). For example, a(2) = 7 counts the 1's in 101, 110, 111. - Shenghui Yang, Feb 09 2025

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, Hypercubes and Isometric Words based on Swap and Mismatch Distance, arXiv:2303.09898 [math.CO], 2023.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 6.
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
Giuseppa Castiglione and Marinella Sciortino, Standard Sturmian words and automata minimization algorithms, Theoretical Computer Science, Volume 601, 11 October 2015, Pages 58-66 ("WORDS 2013").
Tomislav Došlic and Luka Podrug, Tilings of a Honeycomb Strip and Higher Order Fibonacci Numbers, arXiv:2203.11761 [math.CO], 2022.
Dmitry Efimov, Hafnian of two-parameter matrices, arXiv:2101.09722 [math.CO], 2021.
Eric S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, arXiv:math/0307050 [math.CO], 2003. Sec. 8.
Neven Elezović, Asymptotic Expansions of Central Binomial Coefficients and Catalan Numbers, J. Int. Seq. 17 (2014) # 14.2.1.
Martin Griffiths, A Restricted Random Walk defined via a Fibonacci Process, Journal of Integer Sequences, Vol. 14 (2011), #11.5.4.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Cf. A000045 (Fibonacci numbers).
Column 1 of triangle A063967.
Cf. A001629, A002940, A004798, A010049, A029907, A104326, A144154, A181630.

a023610 n = a023610_list !! n
a023610_list = f [1] $ drop 3 a000045_list where
   f us (v:vs) = (sum $ zipWith (*) us $ tail a000045_list) : f (v:us) vs
-- Reinhard Zumkeller, Jan 18 2014

Table[Sum[Binomial[n - i, i]*(n - i), {i, 0, n}], {n, 1, 33}] (* Geoffrey Critzer, May 04 2009 *)

a(n)=(n+2)*fibonacci(n+4)/5+(n-1)*fibonacci(n+2)/5 \\ Charles R Greathouse IV, Jun 11 2015

def A023610():
    a, b, c, d = 1, 3, 7, 15
    while True:
        yield a
        a, b, c, d = b, c, d, 2*(d-b)+c-a
a = A023610(); [next(a) for i in range(33)]  # Peter Luschny, Nov 20 2013

O.g.f.: (x+1)/(1-x-x^2)^2. - Len Smiley, Dec 11 2001
a(n) = (1/5)*((n+2)*F(n+4) + (n-1)*F(n+2)), with F(n)=A000045(n). - Ralf Stephan, Jul 06 2003
a(n) = Sum_{k=0..n+1} (n-k+1)*binomial(n-k+1, k). - Paul Barry, Nov 05 2005
Recurrence: a(n+2) = a(n+1) + a(n) + Fib(n+4), n >= 0. For n >= 2, a(n-2) = (-1)^n*((-2n+3)*Fib(-n) - (-n)*Fib(-n-1))/5 = (-1)^n*A010049(-n), the second-order Fibonacci numbers of negative index, where Fib(-n) = (-1)^(n+1)*Fib(n). - Peter Bala, Oct 24 2007
a(n) = (n+1)*F(n+2) - A001629(n+1) where F(n) is the n-th Fibonacci number. - Geoffrey Critzer, Apr 07 2008
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n >= 4. - L. Edson Jeffery, Mar 29 2013
a(n+1) = A004798(n) + A000045(n+2) for n >= 0. - John Molokach, Jul 04 2013
a(n) = A001629(n+1) + A001629(n+2). - Philippe Deléham, Oct 30 2013
E.g.f.: exp(x/2)*(5*(5 + 7*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(11 + 15*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 04 2023

A112310 Number of terms in lazy Fibonacci representation of n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Dec 01 2005

Equivalently, the number of ones in the maximal Fibonacci bit-representation (A104326) of n.
Conjecture: if we split the sequence in groups that contain Fibonacci(k) terms like (0), (1), (1, 2), (2, 2, 3), (2, 3, 3, 3, 4), (3, 3, 4, 3, 4, 4, 4, 5) etc, the sums in the groups are the terms of A023610. - Gary W. Adamson, Nov 02 2010
Equivalently, the number of periods in the length-n prefix of the infinite Fibonacci word (A003849). An integer p, 1 <= p <= n, is a period of a length-n word x if x[i] = x[i+p] for 1 <= i <= n-p. - Jeffrey Shallit, May 23 2020

			a(10) = 3 because A104326(10) = 1110 contains three ones.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
J. L. Brown, Jr., A new characterization of the Fibonacci numbers, Fibonacci Quarterly 3, No. 1 (1965), 1-8.
Ron Knott, Using the Fibonacci numbers to represent whole numbers.
Wolfgang Steiner, The joint distribution of greedy and lazy Fibonacci expansions, Fib. Q., 43 (No. 1, 2005), 60-69.

Number of terms in row n of A112309.
Cf. A003849, A035517, A007895, A007953, A104326, A117479.
Record positions are in A001911. - Ray Chandler, Dec 01 2005

a112310 n = a112310_list !! n
a112310_list = concat fss where
   fss = [0] : [1] : (map (map (+ 1))) (zipWith (++) fss $ tail fss)
-- Reinhard Zumkeller, Oct 26 2013

A112310 := proc(n)
    convert(A104326(n),base,10) ;
    add(d,d=%) ;
end proc:
seq(A112310(n),n=0..120) ; # R. J. Mathar, Aug 28 2025

DeleteCases[IntegerDigits[Range[200], 2], {_, 0, 0, _}]
A112309 = Map[DeleteCases[Reverse[#] Fibonacci[Range[Length[#]] + 1], 0] &, DeleteCases[IntegerDigits[-1 + Range[200], 2], {_, 0, 0, _}]]
A112310 = Map[Length, A112309]
(* Peter J. C. Moses, Mar 03 2015 *)

a(n) = A007953(A104326(n)). - Amiram Eldar, Oct 10 2023

Extended by Ray Chandler, Dec 01 2005

Merged with a sequence from Casey Mongoven, Mar 20 2006, by Franklin T. Adams-Watters, Dec 19 2006

A056830 Alternate digits 1 and 0.

Original entry on oeis.org

0, 1, 10, 101, 1010, 10101, 101010, 1010101, 10101010, 101010101, 1010101010, 10101010101, 101010101010, 1010101010101, 10101010101010, 101010101010101, 1010101010101010, 10101010101010101, 101010101010101010

Offset: 0

Henry Bottomley, Aug 30 2000

Fibonacci bit-representations of numbers for which there is only one possible representation and for which the maximal and minimal bit-representations (A104326 and A014417) are equal. The numbers represented are equal to the numbers in A000071 (subtract the first term of that sequence). For example, 10101 = 12 because 8+5+1. - Casey Mongoven, Mar 19 2006
Sequence A000975 written in base 2. - Jaroslav Krizek, Aug 05 2009
The absolute value of alternating sum of the first n repunits: a(n) = abs(Sum_{k=0..n} (-1)^k*A002275(n)). - Ilya Gutkovskiy, Dec 02 2015
Binary representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - Robert Price, Dec 05 2016

			n  a(n)             A000975(n)   (If a(n) is interpreted in base 2.)
------------------------------
0  0 ....................... 0
1  1 ....................... 1
2  10 ...................... 2 = 2^1
3  101 ..................... 5
4  1010 ................... 10 = 2^1 + 2^3
5  10101 .................. 21
6  101010 ................. 42 = 2^1 + 2^3 + 2^5
7  1010101 ................ 85
8  10101010 .............. 170 = 2^1 + 2^3 + 2^5 + 2^7
9  101010101 ............. 341
10 1010101010 ............ 682 = 2^1 + 2^3 + 2^5 + 2^7 + 2^9
11 10101010101 .......... 1365
12 101010101010 ......... 2730 = 2^1 + 2^3 + 2^5 + 2^7 + 2^9 + 2^11, etc.
- _Bruno Berselli_, Dec 02 2015

Vincenzo Librandi, Table of n, a(n) for n = 0..800
Index entries for linear recurrences with constant coefficients, signature (10,1,-10).
Index entries for 2-automatic sequences.

Partial sums of A015585.

Cf. A000975, A033113, A033114, A033115, A033116, A033117, A033118, A033119, A059848, A062864.

List([0..30], n-> Int(10^(n+1)/99) ); # G. C. Greubel, Jul 14 2019

[Round((20*10^n-11)/198) : n in [0..30]]; // Vincenzo Librandi, Jun 25 2011

A056830 := proc(n) floor(10^(n+1)/99) ; end proc:

CoefficientList[Series[x/((1-x^2)*(1-10*x)), {x,0,30}], x] (* G. C. Greubel, Sep 26 2017 *)

Vec(x/((1-x)*(1+x)*(1-10*x))+O(x^30)) \\ Charles R Greathouse IV, Feb 13 2017

[floor(10^(n+1)/99) for n in (0..30)] # G. C. Greubel, Jul 14 2019

a(n) = +10*a(n-1) + a(n-2) - 10*a(n-3).
a(n) = floor(10^(n+1)/(10^2-1)) = a(n-2)+10^(n-1) = 10*a(n-1) + (1 - (-1)^n)/2.
From Paul Barry, Nov 12 2003: (Start)
a(n+1) = Sum_{k=0..floor(n/2)} 10^(n-2*k).
a(n+1) = Sum_{k=0..n} Sum_{j=0..k} (-1)^(j+k)*10^j.
G.f.: x/((1-x)*(1+x)*(1-10*x)).
a(n) = 9*a(n-1) + 10*a(n-2) + 1.
a(n) = 10^(n+1)/99 - (-1)^n/22 - 1/18. (End)
a(n) = A007088(A107909(A104161(n))) = A007088(A000975(n)). - Reinhard Zumkeller, May 28 2005
a(n) = round((20*10^n-11)/198) = floor((10*10^n-1)/99) = ceiling((10*10^n-10)/99) = round((10*10^n-10)/99). - Mircea Merca, Dec 27 2010
From Daniel Forgues, Sep 20 2018: (Start)
If a(n) is interpreted in base 2:
a(2n) = Sum_{k=1..n} 2^(2n-1), n >= 0; a(2n-1) = a(2n)/2, n >= 1.
a(2n) = A020988(n), n >= 0.
a(0) = 0; a(2n) = 4*a(2n-2) + 2, n >= 1. (End)

More terms from Casey Mongoven, Mar 19 2006

cp's OEIS Frontend

A003849 The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

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

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

A001911 a(n) = Fibonacci(n+3) - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A003754 Numbers with no adjacent 0's in binary expansion.

Views

Author

Keywords

Comments

Examples

Links