A001911 -id:A001911 - cp's OEIS frontend

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

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

A014675 The infinite Fibonacci word (start with 1, apply 1->2, 2->21, take limit).

Original entry on oeis.org

2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2

Offset: 0

N. J. A. Sloane

The limiting mean and variance of the first n terms are both equal to the golden ratio (A001622). - Clark Kimberling, Mar 12 2014
Let F = A000045 (Fibonacci numbers).  For n >= 3, the first F(n)-2 terms of A014675 form a palindrome; see A001911.  If k is not one of the numbers F(n)-2, then the first k terms of A014675 do not form a palindrome. - Clark Kimberling, Jul 14 2014
First differences of A000201. - Tom Edgar, Apr 23 2015 [Editor's note: except for the offset: as for A022342, below. - M. F. Hasler, Oct 13 2017]
Also first differences of A022342 (which starts at offset 1): a(n)=A022342(n+2)-A022342(n+1), n >= 0. Equal to A001468 without its first term: a(n) = A001468(n+1), n >= 0. - M. F. Hasler, Oct 13 2017
The word is a concatenation of three runs: 1, 2, and 22. The limiting proportions of these are respectively 1/2, 1 - phi/2, and (phi - 1)/2, where phi = golden ratio.  The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010

D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. See Table 2.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7, p. 36.
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

T. D. Noe, Table of n, a(n) for n = 0..10945 (20 iterations)
M. Bunder and K. Tognetti, On the self matching properties of [j tau], Discrete Math., 241 (2001), 139-151.
D. Gault and M. Clint, "Curiouser and curiouser said Alice. Further reflections on an interesting recursive function, Intern. J. Computer. Math., 26 (1988), 35-43. (Annotated scanned copy)
J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Index entries for sequences that are fixed points of mappings

This is the {2,1} version. The standard form is A003849 (alphabet {0,1}). See also A005614 (alphabet {1,0}), A003842 (alphabet {1,2} instead of {2,1}).
Cf. A082389, A008351, A000045, A001622, A001911.
Equals A001468 except for initial term.
Differs from A025143 in many entries starting at entry 8.
First differences of A000201 and of A022342.
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

Digits := 50: t := evalf( (1+sqrt(5))/2); A014675 := n->floor((n+2)*t)-floor((n+1)*t);

Nest[ Flatten[ # /. {1 -> 2, 2 -> {2, 1}}] &, {1}, 11] (* Robert G. Wilson v *)
SubstitutionSystem[{1->{2},2->{2,1}},{1},{11}][[1]] (* Harvey P. Dale, Jan 01 2023 *)

first(n)=my(v=[1],u); while(#vCharles R Greathouse IV, Jun 21 2017

apply( {A014675(n,r=quadgen(5)-1)=(n+2)\r-(n+1)\r}, [0..99]) \\ M. F. Hasler, Apr 07 2021, improved on suggestion from Kevin Ryde, Apr 23 2021

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

Define strings S(0)=1, S(1)=2, S(n)=S(n-1).S(n-2) for n>=2. Sequence is S(infinity).

a(n) = floor((n+2)*phi) - floor((n+1)*phi) = A000201(n+2) - A000201(n+1), phi = (1 + sqrt(5))/2.

Corrected by N. J. A. Sloane, Nov 07 2001

A101220 a(n) = Sum_{k=0..n} Fibonacci(n-k)*n^k.

Original entry on oeis.org

0, 1, 3, 14, 91, 820, 9650, 140601, 2440317, 49109632, 1123595495, 28792920872, 816742025772, 25402428294801, 859492240650847, 31427791175659690, 1234928473553777403, 51893300561135516404, 2322083099525697299278

Offset: 0

Ross La Haye, Dec 14 2004

In what follows a(i,j,k) denotes a three-dimensional array, the terms a(n) are defined as a(n,n,n) in that array. - Joerg Arndt, Jan 03 2021
Previous name was: Three-dimensional array: a(i,j,k) = expansion of x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)), read by a(n,n,n).
a(i,j,k) = the k-th value of the convolution of the Fibonacci numbers (A000045) with the powers of i = Sum_{m=0..k} a(i-1,j,m), both for i = j and i > 0; a(i,j,k) = a(i-1,j,k) + a(j,j,k-1), for i,k > 0; a(i,1,k) = Sum_{m=0..k} a(i-1,0,m), for i > 0. With F = Fibonacci and L = Lucas, then a(1,1,k) = F(k+2) - 1; a(2,1,k) = F(k+3) - 2; a(3,1,k) = L(k+2) - 3; a(4,1,k) = 4*F(k+1) + F(k) - 4; a(1,2,k) = 2^k - F(k+1); a(2,2,k) = 2^(k+1) - F(k+3); a(3,2,k) = 3(2^k - F(k+2)) + F(k); a(4,2,k) = 2^(k+2) - F(k+4) - F(k+2); a(1,3,k) = (3^k + L(k-1))/5, for k > 0; a(2,3,k) = (2 * 3^k - L(k)) /5, for k > 0; a(3,3,k) = (3^(k+1) - L(k+2))/5; a(4,3,k) = (4 * 3^k - L(k+2) - L(k+1))/5, etc..

			a(1,3,3) = 6 because a(1,3,0) = 0, a(1,3,1) = 1, a(1,3,2) = 2 and 4*2 - 2*1 - 3*0 = 6.

G. C. Greubel, Table of n, a(n) for n = 0..385
Eric Weisstein's World of Mathematics, Fibonacci Number
Eric Weisstein's World of Mathematics, Lucas Number

a(0, j, k) = A000045(k).
a(1, 2, k+1) - a(1, 2, k) = A099036(k).
a(3, 2, k+1) - a(3, 2, k) = A104004(k).
a(4, 2, k+1) - a(4, 2, k) = A027973(k).
a(1, 3, k+1) - a(1, 3, k) = A099159(k).
a(i, 0, k) = A109754(i, k).
a(i, i+1, 3) = A002522(i+1).
a(i, i+1, 4) = A071568(i+1).
a(2^i-2, 0, k+1) = A118654(i, k), for i > 0.
Sequences of the form a(n, 0, k): A000045(k+1) (n=1), A000032(k) (n=2), A000285(k-1) (n=3), A022095(k-1) (n=4), A022096(k-1) (n=5), A022097(k-1) (n=6), A022098(k-1) (n=7), A022099(k-1) (n=8), A022100(k-1) (n=9), A022101(k-1) (n=10), A022102(k-1) (n=11), A022103(k-1) (n=12), A022104(k-1) (n=13), A022105(k-1) (n=14), A022106(k-1) (n=15), A022107(k-1) (n=16), A022108(k-1) (n=17), A022109(k-1) (n=18), A022110(k-1) (n=19), A088209(k-2) (n=k-2), A007502(k) (n=k-1), A094588(k) (n=k).
Sequences of the form a(1, n, k): A000071(k+2) (n=1), A027934(k-1) (n=2), A098703(k) (n=3).
Sequences of the form a(2, n, k): A001911(k) (n=1), A008466(k+1) (n=2), A106517(k-1) (n=3).
Sequences of the form a(3, n, k): A027961(k) (n=1), A094688(k) (n=3).
Sequences of the form a(4, n, k): A053311(k-1) (n=1), A027974(k-1) (n=2).
Cf. A001622, A001891, A001924, A023537, A104161, A106517.

A101220:= func< n | (&+[n^k*Fibonacci(n-k): k in [0..n]]) >;
[A101220(n): n in [0..30]]; // G. C. Greubel, Jun 01 2025

Join[{0}, Table[Sum[Fibonacci[n-k]*n^k, {k, 0, n}], {n, 1, 20}]] (* Vaclav Kotesovec, Jan 03 2021 *)

a(n)=sum(k=0,n,fibonacci(n-k)*n^k) \\ Joerg Arndt, Jan 03 2021

def A101220(n): return sum(n^k*fibonacci(n-k) for k in range(n+1))
print([A101220(n) for n in range(31)]) # G. C. Greubel, Jun 01 2025

a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1; a(i, j, k) = ((j+1)*a(i, j, k-1)) - ((j-1)*a(i, j, k-2)) - (j*a(i, j, k-3)), for k > 2.
a(i, j, k) = Fibonacci(k) + i*a(j, j, k-1), for i, k > 0.
a(i, j, k) = (Phi^k - (-Phi)^-k + i(((j^k - Phi^k) / (j - Phi)) - ((j^k - (-Phi)^-k) / (j - (-Phi)^-1)))) / sqrt(5), where Phi denotes the golden mean/ratio (A001622).
i^k = a(i-1, i, k) + a(i-2, i, k+1).
A104161(k) = Sum_{m=0..k} a(k-m, 0, m).
a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1, a(i, j, 3) = i*(j+1) + 2; a(i, j, k) = (j+2)*a(i, j, k-1) - 2*j*a(i, j, k-2) - a(i, j, k-3) + j*a(i, j, k-4), for k > 3. a(i, j, 0) = 0, a(i, j, 1) = 1; a(i, j, k) = a(i, j, k-1) + a(i, j, k-2) + i * j^(k-2), for k > 1.
G.f.: x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)).
a(n, n, n) = Sum_{k=0..n} Fibonacci(n-k) * n^k. - Ross La Haye, Jan 14 2006
Sum_{m=0..k} binomial(k,m)*(i-1)^m = a(i-1,i,k) + a(i-2,i,k+1), for i > 1. - Ross La Haye, May 29 2006
From Ross La Haye, Jun 03 2006: (Start)
a(3, 3, k+1) - a(3, 3, k) = A106517(k).
a(1, 1, k) = A001924(k) - A001924(k-1), for k > 0.
a(2, 1, k) = A001891(k) - A001891(k-1), for k > 0.
a(3, 1, k) = A023537(k) - A023537(k-1), for k > 0.
Sum_{j=0..i+1} a(i-j+1, 0, j) - Sum_{j=0..i} a(i-j, 0, j) = A001595(i). (End)
a(i,j,k) = a(j,j,k) + (i-j)*a(j,j,k-1), for k > 0.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Jan 03 2021

New name from Joerg Arndt, Jan 03 2021

A022290 Replace 2^k in binary expansion of n with Fibonacci(k+2).

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 6, 5, 6, 7, 8, 8, 9, 10, 11, 8, 9, 10, 11, 11, 12, 13, 14, 13, 14, 15, 16, 16, 17, 18, 19, 13, 14, 15, 16, 16, 17, 18, 19, 18, 19, 20, 21, 21, 22, 23, 24, 21, 22, 23, 24, 24, 25, 26, 27, 26, 27, 28, 29, 29, 30, 31, 32, 21, 22, 23, 24, 24, 25, 26

Offset: 0

Marc LeBrun

			n=4 = 2^2 is replaced by A000045(2+2) = 3. n=5 = 2^2 + 2^0 is replaced by A000045(2+2) + A000045(0+2) = 3+1 = 4. - _R. J. Mathar_, Jan 31 2015
From _Philippe Deléham_, Jun 05 2015: (Start)
This sequence regarded as a triangle with rows of lengths 1, 1, 2, 4, 8, 16, ...:
  0
  1
  2, 3
  3, 4, 5, 6
  5, 6, 7, 8, 8, 9, 10, 11
  8, 9, 10, 11, 11, 12, 13, 14, 13, 14, 15, 16, 16, 17, 18, 19
  ...
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Other sequences that are built by replacing 2^k in the binary representation with other numbers: A029931 (naturals), A054204 (even-indexed Fibonacci numbers), A062877 (odd-indexed Fibonacci numbers), A059590 (factorials), A089625 (primes).

Cf. A003754, A022342, A026274.

a022290 0 = 0
a022290 n = h n 0 $ drop 2 a000045_list where
   h 0 y _      = y
   h x y (f:fs) = h x' (y + f * r) fs where (x',r) = divMod x 2
-- Reinhard Zumkeller, Oct 03 2012

A022290 := proc(n)
    dgs := convert(n,base,2) ;
    add( op(i,dgs)*A000045(i+1),i=1..nops(dgs)) ;
end proc: # R. J. Mathar, Jan 31 2015
# second Maple program:
b:= (n, i, j)-> `if`(n=0, 0, j*irem(n, 2, 'q')+b(q, j, i+j)):
a:= n-> b(n, 1$2):
seq(a(n), n=0..127);  # Alois P. Heinz, Jan 26 2022

Table[Reverse[#].Fibonacci[1 + Range[Length[#]]] &@ IntegerDigits[n, 2], {n, 0, 54}] (* IWABUCHI Yu(u)ki, Aug 01 2012 *)

my(m=Mod('x,'x^2-'x-1)); a(n) = subst(lift(subst(Pol(binary(n)), 'x,m)), 'x,2); \\ Kevin Ryde, Sep 22 2020

def A022290(n):
    a, b, s = 1,2,0
    for i in bin(n)[-1:1:-1]:
        s += int(i)*a
        a, b = b, a+b
    return s # Chai Wah Wu, Sep 10 2022

G.f.: (1/(1-x)) * Sum_{k>=0} F(k+2)*x^2^k/(1+x^2^k), where F = A000045.
a(n) = Sum_{k>=0} A030308(n,k)*A000045(k+2). - Philippe Deléham, Oct 15 2011
a(A003714(n)) = n. - R. J. Mathar, Jan 31 2015
a(A000225(n)) = A001911(n). - Philippe Deléham, Jun 05 2015
From Jeffrey Shallit, Jul 17 2018: (Start)
Can be computed from the recurrence:
a(4*k)   = a(k) + a(2*k),
a(4*k+1) = a(k) + a(2*k+1),
a(4*k+2) = a(k) - a(2*k) + 2*a(2*k+1),
a(4*k+3) = a(k) - 2*a(2*k) + 3*a(2*k+1),
and the initial terms a(0) = 0, a(1) = 1. (End)
a(A003754(n)) = n-1. - Rémy Sigrist, Jan 28 2020
From Rémy Sigrist, Aug 04 2022: (Start)
Empirically:
- a(2*A003714(n)) = A022342(n+1),
- a(3*A003714(n)) = a(4*A003714(n)) = A026274(n) for n > 0.
(End)

A001891 Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....

Original entry on oeis.org

0, 1, 4, 10, 21, 40, 72, 125, 212, 354, 585, 960, 1568, 2553, 4148, 6730, 10909, 17672, 28616, 46325, 74980, 121346, 196369, 317760, 514176, 831985, 1346212, 2178250, 3524517, 5702824, 9227400, 14930285, 24157748, 39088098, 63245913, 102334080, 165580064

Offset: 0

N. J. A. Sloane, Simon Plouffe

a(n) is the sum of the n-th row of the triangle in A119457 for n > 0. - Reinhard Zumkeller, May 20 2006
Convolution of odds (A005408) with Fibonacci numbers (A000045). - Graeme McRae, Jun 06 2006
Equals row sums of triangle A152203. - Gary W. Adamson, Nov 29 2008
Define a triangle by T(n,0) = n*(n+1)+1, T(n,n) = 1, and T(r,c) = T(r-1,c) + T(r-2,c-1). This triangle starts: 1; 3,1; 7,2,1; 13,5,2,1; 21,12,4,2,1; the sum of terms in row n is a(n+1). - J. M. Bergot, Apr 23 2013
a(n) = number of k-tuples (u(1), u(2), ..., u(k)) with 1 <= u(1) < u(2) < ... < u(k) <= n such that u(i) - u(i-1) <= 2 for i = 2,...,k. Changing the bound from 2 to 3, then 4, then 5, yields A356619, A356620, A356621. The patterns suggest that the limiting sequence as the bound increases is A000295. - Clark Kimberling, Aug 24 2022

J. Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963. (See A001883)
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).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
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
N. J. A. Sloane, Annotated copy of Riordan's Three-Ply Staircase paper (unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct 1963)
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Partial sums of A001911.
A diagonal of triangle in A080061.
Right-hand column 5 of triangle A011794.
Cf. A001883-A001890. A152203.
Cf. A000295, A356619, A356620, A356621.

List([0..40], n-> Fibonacci(n+5) -2*n-5); # G. C. Greubel, Jul 06 2019

[Fibonacci(n+5)-(5+2*n): n in [0..40]]; // Vincenzo Librandi, Jun 07 2013

LinearRecurrence[{3,-2,-1,1}, {0,1,4,10}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 16 2012 *)
Table[Fibonacci[n+5] -(2*n+5), {n,0,40}] (* G. C. Greubel, Jul 06 2019 *)
maxDiff = 2;
Map[Length[Select[Map[{#, Max[Differences[#]]} &,
  Drop[Subsets[Range[#]], # + 1]], #[[2]] <= maxDiff &]] &,
  Range[16]] (* Peter J. C. Moses, Aug 14 2022 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,-1,-2,3]^n*[0;1;4;10])[1,1] \\ Charles R Greathouse IV, Apr 08 2016

[fibonacci(n+5) -2*n-5 for n in (0..40)] # G. C. Greubel, Jul 06 2019

G.f.: x*(1+x)/((1-x-x^2)*(1-x)^2). - Simon Plouffe in his 1992 dissertation
a(n) = Fibonacci(n+5) - (5+2*n). - Wolfdieter Lang
a(n) = a(n-1) + a(n-2) + (2n+1); a(-x)=0. - Barry E. Williams, Mar 27 2000
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4). - Sam Lachterman (slachterman(AT)fuse.net), Sep 22 2003
a(n) - a(n-1) = A101220(2,1,n). - Ross La Haye, May 31 2006
a(n) = (-3 + (2^(-1-n)*((1-sqrt(5))^n*(-11+5*sqrt(5)) + (1+sqrt(5))^n*(11+5*sqrt(5)))) / sqrt(5) - 2*(1+n)). - Colin Barker, Mar 11 2017

A204922 Ordered differences of Fibonacci numbers.

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 7, 6, 5, 3, 12, 11, 10, 8, 5, 20, 19, 18, 16, 13, 8, 33, 32, 31, 29, 26, 21, 13, 54, 53, 52, 50, 47, 42, 34, 21, 88, 87, 86, 84, 81, 76, 68, 55, 34, 143, 142, 141, 139, 136, 131, 123, 110, 89, 55, 232, 231, 230, 228, 225, 220, 212, 199, 178

Offset: 1

Clark Kimberling, Jan 21 2012

For a guide to related sequences, see A204892. For numbers not in A204922, see A050939.
From Emanuele Munarini, Mar 29 2012: (Start)
Diagonal elements = Fibonacci numbers F(n+1) (A000045)
First column = Fibonacci numbers - 1 (A000071);
Second column = Fibonacci numbers - 2 (A001911);
Row sums = n*F(n+3) - F(n+2) + 2 (A014286);
Central coefficients = F(2*n+1) - F(n+1) (A096140).
(End)

			a(1) = s(2) - s(1) = F(3) - F(2) = 2-1 = 1, where F=A000045;
a(2) = s(3) - s(1) = F(4) - F(2) = 3-1 = 2;
a(3) = s(3) - s(2) = F(4) - F(3) = 3-2 = 1;
a(4) = s(4) - s(1) = F(5) - F(2) = 5-1 = 4.
From _Emanuele Munarini_, Mar 29 2012: (Start)
Triangle begins:
   1;
   2,  1;
   4,  3,  2;
   7,  6,  5,  3;
  12, 11, 10,  8,  5;
  20, 19, 18, 16, 13,  8;
  33, 32, 31, 29, 26, 21, 13;
  54, 53, 52, 50, 47, 42, 34, 21;
  88, 87, 86, 84, 81, 76, 68, 55, 34;
  ... (End)

G. C. Greubel, Rows n=1..100 of triangle, flattened

Cf. A204924, A204892.

/* As triangle */ [[Fibonacci(n+2)-Fibonacci(k+1) : k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Aug 04 2015

Mathematica
```
(See the program at A204924.)
```

create_list(fib(n+3)-fib(k+2),n,0,20,k,0,n); /* Emanuele Munarini, Mar 29 2012 */

{T(n,k) = fibonacci(n+2) - fibonacci(k+1)};
for(n=1,15, for(k=1,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Feb 03 2019

[[fibonacci(n+2) - fibonacci(k+1) for k in (1..n)] for n in (1..15)] # G. C. Greubel, Feb 03 2019

From Emanuele Munarini, Mar 29 2012: (Start)
T(n,k) = Fibonacci(n+2) - Fibonacci(k+1).
T(n,k) = Sum_{i=k..n} Fibonacci(i+1). (End)

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

A006327 a(n) = Fibonacci(n) - 3. Number of total preorders.

Original entry on oeis.org

0, 2, 5, 10, 18, 31, 52, 86, 141, 230, 374, 607, 984, 1594, 2581, 4178, 6762, 10943, 17708, 28654, 46365, 75022, 121390, 196415, 317808, 514226, 832037, 1346266, 2178306, 3524575, 5702884, 9227462, 14930349, 24157814, 39088166, 63245983, 102334152, 165580138

Offset: 4

N. J. A. Sloane, Simon Plouffe

Minimal cost of maximum height Huffman tree of size n. - Alex Vinokur (alexvn(AT)barak-online.net), Oct 25 2004

			G.f. = 2*x^5 + 5*x^6 + 10*x^7 + 18*x^8 + 31*x^9 + 52*x^10 + 86*x^11 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 4..1000
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
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
A. Sapounakis, I. Tasoulas and P. Tsikouras, On the Dominance Partial Ordering of Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.5.
A. B. Vinokur, Huffman trees and Fibonacci numbers, Kibernetika Issue 6 (1986) 9-12 (in Russian); English translation in Cybernetics 21, Issue 6 (1986), 692-696.
Alex Vinokur, Fibonacci connection between Huffman codes and Wythoff array, arXiv:cs/0410013 [cs.DM], 2004-2005.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

A diagonal of A079502.

Cf. A000045, 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]

List([4..45], n-> Fibonacci(n)-3) # G. C. Greubel, Jul 13 2019

[Fibonacci(n)-3: n in [4..45]]; // G. C. Greubel, Jul 13 2019

with(combinat):a:=n->sum(fibonacci(j),j=3..n): seq(a(n),n=2..40); # Zerinvary Lajos, Oct 03 2007
A006327:=(2+z)/(z-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation

Fibonacci[Range[4, 45]] - 3 (* Vladimir Joseph Stephan Orlovsky, Mar 19 2010 *)

a(n)=fibonacci(n)-3 \\ Charles R Greathouse IV, Feb 03 2014

[fibonacci(n)-3 for n in (4..45)] # G. C. Greubel, Jul 13 2019

G.f.: x^5*(2 + x)/((1-x)*(1-x-x^2)).
a(n) = a(n-1) + a(n-2) + 3.
a(n+3) = Sum_{k=-n+1..n} F(abs(n)+1). - Paul Barry, Oct 24 2007
a(n) = F(4*n) mod F(n+1) = F(n) - (F(n+4)^2 - F(n)^2)/F(2*n+4). - Gary Detlefs, Apr 02 2012

Offset corrected by Gary Detlefs, Apr 02 2012

A157725 a(n) = Fibonacci(n) + 2.

Original entry on oeis.org

2, 3, 3, 4, 5, 7, 10, 15, 23, 36, 57, 91, 146, 235, 379, 612, 989, 1599, 2586, 4183, 6767, 10948, 17713, 28659, 46370, 75027, 121395, 196420, 317813, 514231, 832042, 1346271, 2178311, 3524580, 5702889, 9227467, 14930354, 24157819, 39088171, 63245988, 102334157

Offset: 0

N. J. A. Sloane, Jun 26 2010

a(n) = A226649(2*n+1) - A226649(2*n). - Reinhard Zumkeller, Jul 30 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..285
Kwang-Wu Chen, Greatest Common Divisors in Shifted Fibonacci Sequences, J. Int. Seq. 14 (2011) # 11.4.7.
Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
Ivana Jovović and Branko Malešević, Some enumerations of non-trivial composition of the differential operations and the directional derivative, Notes on Number Theory and Discrete Mathematics, Vol. 23, 2017, No. 1, 28-38.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000045, A001611, A000071, A001911, A157726, A006327, A157727, A157728, A157729, A167616, A226649.

a157725 = (+ 2) . a000045
a157725_list = 2 : 3 : map (subtract 2)
                       (zipWith (+) a157725_list $ tail a157725_list)
-- Reinhard Zumkeller, Jul 30 2013

[ Fibonacci(n) + 2: n in [0..40] ]; // Vincenzo Librandi, Apr 24 2011

Fibonacci[Range[0, 50]] + 2 (* or *)
LinearRecurrence[{2, 0, -1}, {2, 3, 3}, 50] (* Paolo Xausa, Jul 28 2024 *)

a(n)=fibonacci(n)+2 \\ Charles R Greathouse IV, Jul 02 2013

G.f.: -(1+x)*(3*x-2) / ( (x-1)*(x^2+x-1) ). - R. J. Mathar, Aug 08 2012
a(0) = 2, a(1) = 3, a(n) = a(n - 2) + a(n - 1) - 2. - Reinhard Zumkeller, Jul 30 2013
E.g.f.: 2*(exp(x) + exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5)). - Stefano Spezia, Apr 09 2025

A167616 a(n) = Fibonacci(n) - 5.

Original entry on oeis.org

0, 3, 8, 16, 29, 50, 84, 139, 228, 372, 605, 982, 1592, 2579, 4176, 6760, 10941, 17706, 28652, 46363, 75020, 121388, 196413, 317806, 514224, 832035, 1346264, 2178304, 3524573, 5702882, 9227460, 14930347, 24157812, 39088164, 63245981, 102334150

Offset: 5

N. J. A. Sloane, Jun 26 2010

G. C. Greubel, Table of n, a(n) for n = 5..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000045, A001611, A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616.

List([5..45], n-> Fibonacci(n)-5); # G. C. Greubel, Jul 13 2019

[(Fibonacci(n) - 5): n in [5..45]]; // Vincenzo Librandi, Apr 23 2011

Fibonacci[Range[5,45]]-5 (* or *) LinearRecurrence[{2,0,-1},{0,3,8},40] (* Harvey P. Dale, Dec 31 2011 *)

a(n)=fibonacci(n)-5 \\ Charles R Greathouse IV, Jul 01 2013

[fibonacci(n)-5 for n in (5..45)] # G. C. Greubel, Jul 13 2019

a(n) = a(n-1) + a(n-2) + 5. - Zak Seidov, Jun 27 2010
a(5)=0, a(6)=3, a(7)=8, a(n) = 2*a(n-1) - a(n-3). - Harvey P. Dale, Dec 31 2011
G.f.: x^6*(3+2*x)/((1-x)*(1-x-x^2)). - L. Edson Jeffery, Mar 17 2013

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A014675 The infinite Fibonacci word (start with 1, apply 1->2, 2->21, take limit).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A101220 a(n) = Sum_{k=0..n} Fibonacci(n-k)*n^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A022290 Replace 2^k in binary expansion of n with Fibonacci(k+2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A001891 Hit polynomials; convolution of natural numbers with Fibonacci numbers F(2), F(3), F(4), ....

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A204922 Ordered differences of Fibonacci numbers.

Views

Author