cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 11 results. Next

A035615 Number of winning length n strings with a 2-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 2, 2, 6, 12, 26, 58, 126, 278, 602, 1300, 2774, 5878, 12350, 25778, 53470, 110332, 226610, 463602, 945214, 1921550, 3896642, 7885092, 15927086, 32121582, 64697726, 130166378, 261637446, 525478668, 1054673162, 2115601450, 4241716734, 8501080838, 17031744170
Offset: 0

Views

Author

Erich Friedman

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243.
See A309874 for the losing strings.
For some similar questions in base 10, see A323830, A323831, A320487. - N. J. A. Sloane, Feb 04 2019
Row b=2 of A323844.

Programs

  • Mathematica
    Join[{1}, Rest[CoefficientList[Series[x (2x^6 - 6x^5 + 8x^4 + 2x^3 - 6x^2 + 2x)/((1 - x^2)(1 - 2x)(1 - x - x^2)^2), {x, 0, 40}], x]]] (* or *) Join[{1}, LinearRecurrence[{4, -2, -8, 6, 6, -3, -2}, {0, 2, 2, 6, 12, 26, 58}, 40]] (* Harvey P. Dale, Sep 26 2012 *)
  • PARI
    a(n)=if(n, ([0,1,0,0,0,0,0; 0,0,1,0,0,0,0; 0,0,0,1,0,0,0; 0,0,0,0,1,0,0; 0,0,0,0,0,1,0; 0,0,0,0,0,0,1; -2,-3,6,6,-8,-2,4]^(n-1)*[0;2;2;6;12;26;58])[1,1], 1) \\ Charles R Greathouse IV, Jun 15 2015

Formula

G.f.: x(2x^6 - 6x^5 + 8x^4 + 2x^3 - 6x^2 + 2x)/[(1 - x^2)(1 - 2x)(1 - x - x^2)^2] (conjectured). - Ralf Stephan, May 11 2004. Established by Burns and Purcell - see link.
a(0) = 1, a(1) = 0, a(2) = 2, a(3) = 2, a(4) = 6, a(5) = 12, a(6) = 26, a(7) = 58, a(n) = 4*a(n-1) - 2*a(n-2) - 8*a(n-3) + 6*a(n-4) + 6*a(n-5) - 3*a(n-6) - 2*a(n-7). - Harvey P. Dale, Sep 26 2012
a(n) = 2^n - 2 * n * Fibonacci(n-2) - (-1)^n - 1 for n >= 2 (proved by Burns and Purcell (2005, 2007)). - Petros Hadjicostas, Jul 04 2018

Extensions

More terms from Naohiro Nomoto, Jul 09 2001
Further terms from Sascha Kurz, Oct 19 2001
a(27)-a(36) from Robert Price, Apr 08 2019

A035617 Number of winning length n strings with a 3-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 3, 3, 15, 33, 105, 297, 879, 2631, 7833, 23697, 71385, 216765, 657849, 2003151, 6103743, 18624693, 56870385, 173760513, 531128349, 1623881889, 4965695331, 15185222199, 46435889601, 141985777503
Offset: 0

Views

Author

Erich Friedman

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Dec 27 2018

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A065237, A065238, A065239, A065240, A065241, A065242, A065243.
Row b=3 of A323844.

Extensions

a(16)-a(25) from Bert Dobbelaere, Dec 26 2018

A065237 Number of winning length n strings with a 4-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 4, 4, 28, 64, 268, 844, 3100, 10876, 39244, 142432, 518380, 1906012, 7012660, 25980940, 96407356, 359260936, 1341482740, 5023006444, 18844637356
Offset: 0

Views

Author

Sascha Kurz, Oct 23 2001

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Jul 05 2018

Examples

			11011001 is a winning string since 110{11}001->11{000}1->{111}->null.

Links

Crossrefs

Cf. A035615, A035617, A065238, A065239, A065240, A065241, A065242, A065243.
Row b=4 of A323844.

Extensions

a(13)-a(20) from Bert Dobbelaere, Dec 26 2018

A065243 Number of winning length n strings with a 10-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 10, 10, 190, 460, 4690, 17650, 136630, 651790, 4439890, 24056020, 154885870, 898393870, 5659321510, 34068918250, 213351643990
Offset: 0

Views

Author

Sascha Kurz, Oct 23 2001

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A309874, A323812.
Row b=10 of A323844.

Extensions

a(12)-a(16) from Bert Dobbelaere, Dec 24 2018

A309874 a(n) = 2*n*Fibonacci(n-2) + (-1)^n + 1.

Original entry on oeis.org

2, 6, 10, 20, 38, 70, 130, 234, 422, 748, 1322, 2314, 4034, 6990, 12066, 20740, 35534, 60686, 103362, 175602, 297662, 503516, 850130, 1432850, 2411138, 4051350, 6798010, 11392244, 19068662, 31882198, 53250562, 88853754, 148125014
Offset: 2

Views

Author

Petros Hadjicostas, Sep 01 2019

Keywords

Comments

For n >= 2, a(n) is the number of length n losing strings with a binary alphabet in the "same game".
In the "same game", winning strings are those that can be reduced to the null string by repeatedly removing an entire run of two or more consecutive symbols.
Sequence A035615 counts the winning strings of length n in a binary alphabet in the "same game".

Examples

			For n=2, we have 2^2 = 4 strings of length 2 in the binary alphabet {0,1}: 00, 11, 01, and 10. Out of those strings, only 00 and 11 are winning strings in the "same game" because removing an entire run of two or more consecutive symbols gives the null string. Thus, a(2) = 2 (corresponding to the losing strings 01 and 10).
For n=3, we have 2^3 = 8 strings of length 3 in the binary alphabet {0,1}: 000, 001, 010, 100, 110, 101, 011, 111. Out of these, only the strings 000 and 111 are winning, while the rest a(2) = 6 strings are losing strings.
For n=4, we have 2^4 = 16 strings of length 4 in the binary alphabet {0,1}. From these, only 0000, 0011, 1100, 0110, 1001, and 1111 are winning strings while the rest a(4) = 16 - 6 = 10 are losing strings. (For example 0{11}0 -> 00 -> null.)
For n=8, the string 11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065242, A065243, A323812, A323844.

Programs

  • Maple
    seq(2*n*combinat:-fibonacci(n-2) + (-1)^n + 1, n=2..100); # Robert Israel, Sep 03 2019
  • Mathematica
    A309874[n_]:=Fibonacci[n-2]2n+(-1)^n+1;Array[A309874,50,2] (* Paolo Xausa, Nov 16 2023 *)

Formula

a(n) = 2^n - A323844(2,n) = 2^n - A035615(n) = 2*A323812(n) for n >= 2.
G.f.: x^2*(2 + 2*x - 6*x^2 - 4*x^3 + 6*x^4 + 2*x^5)/((1-x^2)*(1-x-x^2)^2). - Robert Israel, Sep 03 2019

A323844 Square array T(b,m), read by descending antidiagonals: Number of winning length m strings with a b-symbol alphabet in "same game" (b >= 2, m >= 0).

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 6, 3, 4, 0, 1, 12, 15, 4, 5, 0, 1, 26, 33, 28, 5, 6, 0, 1, 58, 105, 64, 45, 6, 7, 0, 1, 126, 297, 268, 105, 66, 7, 8, 0, 1, 278, 879, 844, 545, 156, 91, 8, 9, 0, 1, 602, 2631, 3100, 1825, 966, 217, 120, 9, 10, 0, 1
Offset: 0

Views

Author

Petros Hadjicostas, Aug 31 2019

Keywords

Comments

Terms for this square array were calculated by Bert Dobbelaere, Erich Friedman, Sascha Kurz, and Robert Price (see the Crossrefs below).
This array counts strings that can be reduced to the null string by repeatedly removing an entire run of two or more consecutive symbols (see the example below and the references).
For binary strings (b = 2), the formula for the number of winning strings of length m (i.e., T(b=2, m) = 2^m - 2 * m * Fibonacci(m-2) - (-1)^m - 1 for m >= 2) was conjectured by Ralf Stephan (2004, p. 8) and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved.

Examples

			Table T(b,m) (with rows b >= 2 and columns m >= 0) begins as follows:
  1, 0, 2, 2,   6,  12,   26,   58,   126,    278,     602,    1300,     2774, ...
  1, 0, 3, 3,  15,  33,  105,  297,   879,   2631,    7833,   23697,    71385, ...
  1, 0, 4, 4,  28,  64,  268,  844,  3100,  10876,   39244,  142432,   518380, ...
  1, 0, 5, 5,  45, 105,  545, 1825,  7965,  30845,  128945,  527785,  2202785, ...
  1, 0, 6, 6,  66, 156,  966, 3366, 16986,  70386,  332646, 1484676,  6922146, ...
  1, 0, 7, 7,  91, 217, 1561, 5593, 32011, 139363,  732697, 3492265, 17899609, ...
  1, 0, 8, 8, 120, 288, 2360, 8632, 55224, 249656, 1443128, 7243552, 40366040, ...
  ...
11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615 (row b=2), A035617 (row b=3), A065237 (row b=4), A065238 (row b=5), A065239 (row b=6), A065240 (row b=7), A065241 (row b=8), A065242 (row b=9), A065243 (row b=10), A238879, A309874 (losing strings for b=2), A323812 (one-half of the losing strings for b=2).

Formula

T(b=2, m) = 2^m - 2 * m * Fibonacci(m-2) - (-1)^m - 1 for m >= 2 (Burns and Purcell (2005, 2007)).
For the columns, Kurz (2001) says: "Because of the fact, that a winning m-digit b-ary string can only have floor(m/2) different digits, there exists for T(b,m) a polynomial with maximal degree floor(m/2)." (I changed his n to m and his a(n,b) to T(b,m).)
Kurz (2001) goes on to list the following formulas (without proof) for the columns of the array (valid for b >= 1):
T(b,1) = 0;
T(b,2) = b;
T(b,3) = b;
T(b,4) = 2*b^2 - b;
T(b,5) = 5*b^2 - 4*b;
T(b,6) = 5*b^3 - 3*b^2 - b;
T(b,7) = 21*b^3 - 35*b^2 + 15*b;
T(b,8) = 14*b^4 - 36*b^2 + 23*b;
T(b,9) = 84*b^4 - 204*b^3 + 162*b^2 - 41*b;
T(b,10) = 42*b^5 + 60*b^4 - 405*b^3 + 465*b^2 - 161*b;
T(b,11) = 330*b^5 - 990*b^4 + 990*b^3 - 341*b^2 + 12*b.
It is not clear whether Kurz's formulas are statements of fact (with an easy proof) or just conjectures.
From the results in the Crossrefs, we may also conjecture the following:
T(b,12) = 132*b^6 + 495*b^5 - 3135*b^4 + 5066*b^3 - 3384*b^2 + 827*b;
T(b,13) = 1287*b^6 - 4290*b^5 + 4004*b^4 + 585*b^3 - 2392*b^2 + 807*b;
T(b,14) = 429*b^7 + 3003*b^6 - 20020*b^5 + 40495*b^4 - 38402*b^3 + 18095*b^2 - 3599*b;
T(b,15) = 5005*b^7 - 17017*b^6 + 7098*b^5 + 38500*b^4 - 62455*b^3 + 36495*b^2 - 7625*b;
T(b,16) = 1430*b^8 + 16016*b^7 - 113568*b^6 + 266560*b^5 - 308660*b^4 + 197440*b^3 - 73376*b^2 + 14159*b.
It seems that, for m >= 2, T(b,m) is a polynomial of b of degree floor(m/2) with a leading coefficient equal to A238879(m-2). In other words, the leading coefficient equals (2/(m+2)) * binomial(m, m/2), if m is even >= 2, and binomial(m, (m - 3)/2) if m is odd >= 3.

A065238 Number of winning length n strings with a 5-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 5, 5, 45, 105, 545, 1825, 7965, 30845, 128945, 527785, 2202785, 9222985, 38818505, 164436125, 698347645, 2981306665, 12756855065
Offset: 0

Views

Author

Sascha Kurz, Oct 23 2001

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A035617, A065237, A065239, A065240, A065241, A065242, A065243, A309874, A323812.
Row b=5 of A323844.

Extensions

a(13)-a(18) from Bert Dobbelaere, Dec 26 2018

A065239 Number of winning length n strings with a 6-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 6, 6, 66, 156, 966, 3366, 16986, 70386, 332646, 1484676, 6922146, 31921506, 149341506, 700002366, 3299514906, 15618721956, 74169285366
Offset: 0

Views

Author

Sascha Kurz, Oct 23 2001

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A035617, A065237, A065238, A065240, A065241, A065242, A065243, A309874, A323812.
Row b=6 for A323844.

Extensions

a(12)-a(18) from Bert Dobbelaere, Dec 26 2018

A065241 Number of winning length n strings with an 8-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 8, 8, 120, 288, 2360, 8632, 55224, 249656, 1443128, 7243552, 40366040, 213357880, 1178216264, 6395922296, 35375108728, 194951335888
Offset: 0

Views

Author

Sascha Kurz, Oct 23 2001

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065242, A065243, A309874, A323812.
Row b=8 of A323844.

Extensions

a(12)-a(17) from Bert Dobbelaere, Dec 26 2018

A065242 Number of winning length n strings with a 9-symbol alphabet in "same game".

Original entry on oeis.org

1, 0, 9, 9, 153, 369, 3393, 12609, 89145, 415161, 2614689, 13684977, 82237185, 457154577, 2704775985, 15524314425, 91659251961
Offset: 0

Views

Author

Sascha Kurz, Oct 23 2001

Keywords

Comments

Strings that can be reduced to null string by repeatedly removing an entire run of two or more consecutive symbols.
For binary strings, the formula for the number of winning strings of length n has been conjectured by Ralf Stephan and proved by Burns and Purcell (2005, 2007). For b-ary strings with b >= 3, the same problem seems to be unsolved. - Petros Hadjicostas, Aug 31 2019

Examples

			11011001 is a winning string since 110{11}001 -> 11{000}1 -> {111} -> null.

Links

Crossrefs

Cf. A035615, A035617, A065237, A065238, A065239, A065240, A065241, A065243, A309874, A323812.
Row b=9 of A323844.

Extensions

a(12)-a(16) from Bert Dobbelaere, Dec 26 2018
Showing 1-10 of 11 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.