A049194 -id:A049194 - cp's OEIS frontend

A001609 a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).

1, 1, 4, 5, 6, 10, 15, 21, 31, 46, 67, 98, 144, 211, 309, 453, 664, 973, 1426, 2090, 3063, 4489, 6579, 9642, 14131, 20710, 30352, 44483, 65193, 95545, 140028, 205221, 300766, 440794, 646015, 946781, 1387575, 2033590, 2980371, 4367946, 6401536, 9381907

Offset: 1

N. J. A. Sloane

This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1...m-1, a(m) = m + 1. The generating function is (x + m*x^m)/(1 - x - x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n-1-(m-1)*i, i-1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m=2: A000204, m=3: A001609, m=4: A014097, m=5: A058368, m=6: A058367, m=7: A058366, m=8: A058365, m=9: A058364.
The sequence defined by {a(n) - 1} plays a role for the computation of A065414, A146486, A146487, and A146488 equivalent to the role of A001610 for A005596, A146482, A146483 and A146484, see the variable a_{2,n} in arXiv:0903.2514. - R. J. Mathar, Mar 28 2009
Except for n = 2, a(n) is the number of digits in n-th term of A049064. This can be derived form the T. Sillke link below. - Jianing Song, Apr 28 2019

			G.f. = x + x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 10*x^6 + 15*x^7 + 21*x^8 + ...

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).

Indranil Ghosh, Table of n, a(n) for n = 1..6012 (terms 1..500 from T. D. Noe)
Ignacio Cascudo, On squares of cyclic codes, arXiv:1703.01267 [cs.IT], 2017. See Theorem 6.1/Table 1.
Johann Cigler, Some remarks on generalized Fibonacci and Lucas polynomials, arXiv:1912.06651 [math.CO], 2019.
E. Di Cera and Y. Kong, Theory of multivalent binding in one and two-dimensional lattices, Biophysical Chemistry, Vol. 61 (1996), pp. 107-124.
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Daniel C. Fielder, Errata:Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 91.
Matthew Macauley, Jon McCammond, Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
M. Newman and D. Shanks, On a sequence arising in series for pi, Math. Comp., 42 (1984), 199-217 (see Eq. 29).
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.
Souvik Roy, Nazim Fatès, and Sukanta Das, Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence, hal-04456320 [nlin.CG], [cs], 2024. See p. 19.
T. Sillke, The binary form of Conway's sequence
Z. Skupien, Sparse Hamiltonian 2-decompositions together with exact count of numerous Hamiltonian cycles, Discr. Math., 309 (2009), 6382-6390. - _N. J. A. Sloane_, Feb 12 2010
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Cf. A000204, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A000930, A218439.

Cf. also A049064, A049194.

I:=[1,1,4]; [n le 3 select I[n] else Self(n-1)+Self(n-3): n in [1..45]]; // Vincenzo Librandi, Jun 28 2015

A001609:=-(1+3*z**2)/(-1+z+z**3); # Simon Plouffe in his 1992 dissertation
f:= gfun:-rectoproc({a(n) = a(n-1) + a(n-3), a(1)=1,a(2)=1,a(3)=4},a(n),remember):
map(f, [$1..100]); # Robert Israel, Jun 29 2015

Table[Tr[MatrixPower[{{0, 0, 1}, {1, 0, 0}, {0, 1, 1}}, n]], {n, 1, 60}] (* Artur Jasinski, Jan 10 2007 *)
Table[ HypergeometricPFQ[{1/3 - n/3, 2/3 - n/3, -(n/3)}, {1/2 - n/2, 1 - n/2}, -(27/4)], {n, 20}] (* Alexander R. Povolotsky, Nov 21 2008 *)
a[1] = a[2] = 1; a[3] = 4; m = 3; a[n_] := 1 + n*Sum [Binomial [n - 1 - (m - 1)*i, i - 1]/i, {i, n/m}] A001609 = Table[a[n], {n, 100}] (* Zak Seidov, Nov 21 2008 *)
LinearRecurrence[{1, 0, 1}, {1, 1, 4}, 50] (* Vincenzo Librandi, Jun 28 2015 *)

{a(n) = if( n<1, n=-n; polcoeff( (3 + x^2) / (1 + x^2 - x^3) + x * O(x^n), n), polcoeff( x * (1 + 3*x^2) / (1 - x - x^3) + x * O(x^n), n))}; /* Michael Somos, Aug 15 2016 */

G.f.: x*(1 + 3*x^2)/(1 - x - x^3).
a(n) = trace of successive powers of matrix ({{0,0,1},{1,0,0},{0,1,1}})^n. - Artur Jasinski, Jan 10 2007
a(n) = A000930(n) + 3*A000930(n-2). - R. J. Mathar, Nov 16 2007
Logarithmic derivative of Narayana's cows sequence A000930. - Paul D. Hanna, Oct 28 2012
a(n) = w1^n + w2^n + w3^n, where w1,w2,w3 are the roots of the cubic: (-1 - x^2 + x^3), see A092526. - Gerry Martens, Jun 27 2015

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
More terms from Michael Somos, Oct 03 2002
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A001387 The binary "look and say" sequence.

Original entry on oeis.org

1, 11, 101, 111011, 11110101, 100110111011, 111001011011110101, 111100111010110100110111011, 100110011110111010110111001011011110101, 1110010110010011011110111010110111100111010110100110111011

Offset: 1

Thomas L. York

I conjecture that the ratio r(n) of the number of "1"s to the number of "0"s in a(n) converges to 5/3 (or some nearby limit). - Joseph L. Pe, Jan 31 2003
The ratio r(n) of the number of "1"s to the number of "0"s in a(n) actually converges to ((101 - 10*sqrt(93))*a^2 + (139 - 13*sqrt(93))*a - 76)/108, where a = (116 + 12*sqrt(93))^(1/3). This ratio has decimal expansion 1.6657272222676... - Nathaniel Johnston, Nov 07 2010 [Corrected by Kevin J. Gomez, Dec 12 2017]
Reading terms as binary numbers and converting to decimal gives A049190. - Andrey Zabolotskiy, Dec 12 2017
From Jianing Song, Oct 05 2022: (Start)
"000" or "11111" never appear in any a(n). Proof:
When "000" appears for the first time in a(n),
- if it reads as "..00 0's", then a(n-1) must contain at least 4 consecutive 0's, which is impossible;
- if it reads as "...000... 0's" or "...000... 1's", then a(n-1) must contain at least 8 consecutive 0's or at least 8 consecutive 1's.
In conclusion, a(n-1) must contain at least 8 consecutive 1's.
When "11111" appears for the first time in a(n),
- if it reads as "...1111 1's", then a(n-1) must contain at least 15 consecutive 1's, which is impossible;
- if it reads as "...111 1's, 1... 0's", then a(n-1) must contain at least 7 consecutive 1's, which is impossible;
- if it reads as "...11 1's, 11... 0's", then a(n-1) must contain at least 3 consecutive 0's;
- if it reads as "...1 1's, 111... 0's", then a(n-1) must contain at least 7 consecutive 0's;
- if it reads as "... 1's, 1111... 0's", then a(n-1) must contain at least 15 consecutive 0's;
- if it reads as "...11111... 0's" or "...11111... 1's", then a(n-1) must contain at least 31 consecutive 0's or at least 31 consecutive 1's.
In conclusion, a(n-1) must contain at least 3 consecutive 0's. Combining these two results, one can easily show that "000" or "11111" cannot appear. (End)

			To get the 5th term, for example, note that 4th term has three (11 in binary!) 1's, one (1) 0 and two (10) 1's, giving 11 1 1 0 10 1.

John Cerkan, Table of n, a(n) for n = 1..17
J. H. Conway, The weird and wonderful chemistry of audioactive decay, Eureka 46 (1986) 5-16, reprinted in: Open Problems in Communications and Computations, Springer, 1987, 173-188.
Nathaniel Johnston, The Binary "Look-and-Say" Sequence
Thomas Morrill, Look, Knave, arXiv:2004.06414 [math.CO], 2020.
Torsten Sillke, The binary form of Conway's sequence

Cf. A005150, A001391, A049190, A049194.

a[1] := 1; a[n_] := a[n] = FromDigits[Flatten[{IntegerDigits[Length[#],2], First[#]}& /@ Split[IntegerDigits[a[n-1]]]]]; Map[a, Range[20]] (* Peter J. C. Moses, Mar 24 2013 *)
Nest[Append[#, FromDigits@ Flatten@ Map[Reverse /@ IntegerDigits[Tally@ #, 2] &, Split@ IntegerDigits@ Last@ #]] &, {1}, 9] (* Michael De Vlieger, Dec 12 2017 *)

from itertools import accumulate, groupby, repeat
def summarize(n, _): return int("".join(bin(len(list(g)))[2:]+k for k, g in groupby(str(n))))
def aupto(terms): return list(accumulate(repeat(1, terms), summarize))
print(aupto(11)) # Michael S. Branicky, Sep 18 2022

New name from Andrey Zabolotskiy, Dec 13 2017

A179999 Length of the n-th term in the modified Look and Say sequence A110393.

Original entry on oeis.org

1, 2, 2, 4, 6, 8, 10, 14, 18, 24, 30, 40, 50, 66, 82, 108, 134, 176, 218, 286, 354, 464, 574, 752, 930, 1218, 1506, 1972, 2438, 3192, 3946, 5166, 6386, 8360, 10334, 13528, 16722, 21890, 27058, 35420, 43782, 57312, 70842, 92734, 114626, 150048

Offset: 1

Nathaniel Johnston, Jan 13 2011

The average multiplicative growth from the n-th term to the (n+1)-st term is sqrt(phi) = 1.272..., where phi = (1+sqrt(5))/2 is the golden ratio, see A139339.

			The 6th term in A110393 is 21112211, so a(6) = 8.

Colin Barker, Table of n, a(n) for n = 1..1000
N. Johnston, Further Variants of the “Look-and-Say” Sequence
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1).

Cf. A005341, A049194, A098596, A110393.

Cf. A001622, A134972, A139339, A239798.

CoefficientList[Series[((1+x) (-1-x+x^2) (1-x+x^2))/((1-x) (-1+x^2+x^4)),{x,0,99}],x] (* Peter J. C. Moses, Jun 23 2013 *)

Vec(x*(1 + x)*(1 + x - x^2)*(1 - x + x^2) / ((1 - x)*(1 - x^2 - x^4)) + O(x^50)) \\ Colin Barker, Aug 10 2019

a(n) = length(A110393(n)).
From Colin Barker, Aug 10 2019: (Start)
G.f.: x*(1 + x)*(1 + x - x^2)*(1 - x + x^2) / ((1 - x)*(1 - x^2 - x^4)).
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) for n>6. (End)
From A.H.M. Smeets, Aug 10 2019 (Start)
Limit_{n->oo} a(n+1)/a(n) = (1+phi)/2 = (3+sqrt(5))/4 = A239798 for odd n.
Limit_{n->oo} a(n+1)/a(n) = 2/phi = 4/(1+sqrt(5)) = A134972 for even n.
Limit_{n->oo} a(n+2)/a(n) = (1+phi)/phi = phi = A001622. (End)
For odd n > 1, a(n) = 4*Fibonacci((n + 1)/2) - 2. For even n, a(n) = 2*Fibonacci(n/2 + 2) - 2. - Ehren Metcalfe, Aug 10 2019

A046639 Length of A001388(n).

Original entry on oeis.org

1, 2, 2, 4, 6, 7, 10, 12, 18, 25, 31, 41, 56, 73, 96, 128, 171, 226, 302, 399, 533, 704, 937, 1236, 1645, 2170, 2884, 3806, 5059, 6680, 8875, 11725, 15575, 20584, 27332, 36132, 47963, 63420, 84160, 111306, 147673, 195345, 259118, 342831, 454680

Offset: 1

David W. Wilson

The average multiplicative growth from the n-th term to the (n+1)st term is the largest root of x^3 - x - 1, which is approximately 1.324718. - Nathaniel Johnston, Jan 13 2011

Peter J. C. Moses, Table of n, a(n) for n = 1..1000
N. Johnston, Further Variants of the “Look-and-Say” Sequence
Index entries for linear recurrences with constant coefficients, signature (0,2,1,0,-2,-2,0,2,2,0,-1,-1).

Cf. A005150, A049194.

p={-1,3,4,1,-2,-4,-4,1,5,1,0,0,-1,0,-1,0,2,1};
q={1,1,0,-2,-2,0,2,2,0,-1,-2,0,1};
gf=Fold[x #1+#2&,0,p]/Fold[x #1+#2&,0,q];
CoefficientList[Series[gf,{x,0,100}],x] (* Peter J. C. Moses, Jun 21 2013 *)
LinearRecurrence[{0,2,1,0,-2,-2,0,2,2,0,-1,-1},{1,2,2,4,6,7,10,12,18,25,31,41,56,73,96,128,171,226},50] (* Harvey P. Dale, Mar 08 2022 *)

Vec(x*(1 + 2*x - x^3 - x^5 + x^8 + 5*x^9 + x^10 - 4*x^11 - 4*x^12 - 2*x^13 + x^14 + 4*x^15 + 3*x^16 - x^17) / ((1 - x)*(1 + x)*(1 + x^2)*(1 - x^2 - x^3)*(1 - x^2 + x^5)) + O(x^50)) \\ Colin Barker, Jul 01 2020

From Colin Barker, Jul 01 2020: (Start)
G.f.: x*(1 + 2*x - x^3 - x^5 + x^8 + 5*x^9 + x^10 - 4*x^11 - 4*x^12 - 2*x^13 + x^14 + 4*x^15 + 3*x^16 - x^17) / ((1 - x)*(1 + x)*(1 + x^2)*(1 - x^2 - x^3)*(1 - x^2 + x^5)).
a(n) = 2*a(n-2) + a(n-3) - 2*a(n-5) - 2*a(n-6) + 2*a(n-8) + 2*a(n-9) - a(n-11) - a(n-12) for n>18.
(End)

cp's OEIS Frontend

A001609 a(1) = a(2) = 1, a(3) = 4; thereafter a(n) = a(n-1) + a(n-3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A001387 The binary "look and say" sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A179999 Length of the n-th term in the modified Look and Say sequence A110393.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A046639 Length of A001388(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula