A035615 -id:A035615 - cp's OEIS frontend

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

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

Offset: 0

Sascha Kurz, Oct 23 2001

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

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

Chris Burns and Benjamin Purcell, A note on Stephan's conjecture 77, preprint, 2005. [Cached copy]
Chris Burns and Benjamin Purcell, Counting the number of winning strings in the 1-dimensional same game, Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials in "same game", 2001. [ps file]
Sascha Kurz, Polynomials for same game, 2001. [pdf file]
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

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

Row b=9 of A323844.

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

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

Original entry on oeis.org

1, 3, 5, 10, 19, 35, 65, 117, 211, 374, 661, 1157, 2017, 3495, 6033, 10370, 17767, 30343, 51681, 87801, 148831, 251758, 425065, 716425, 1205569, 2025675, 3399005, 5696122, 9534331, 15941099, 26625281, 44426877, 74062507, 123360230, 205303933, 341416205, 567353377, 942154863, 1563526761

Offset: 2

Petros Hadjicostas, Sep 01 2019

nonn

For n >= 2, a(n) is one-half 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", while A309874 counts the losing strings.
Thus, a(n) = A309874(n)/2 for n >= 2. The reason sequence A309874 is divisible by 2 is because the complement of every winning string is also a winning string (where by "complement" we mean 0 is replaced with 1 and vice versa).

			11011001 is a winning string because 110{11}001 -> 11{000}1 -> {111} -> null. Its complement, 00100110 is also a winning string because 001{00}110 -> 00{111}0 -> {000} -> null.

Chris Burns and Benjamin Purcell, A note on Stephan's conjecture 77, preprint, 2005. [Cached copy]
Chris Burns and Benjamin Purcell, Counting the number of winning strings in the 1-dimensional same game, Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials for same game, pdf.
Ralf Stephan, Prove or disprove: 100 conjectures from the OEIS, arXiv:math/0409509 [math.CO], 2004.

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

Table[n Fibonacci[n-2]+((-1)^n+1)/2,{n,2,40}] (* Harvey P. Dale, Sep 17 2019 *)

a(n) = A309874(n)/2 for n >= 2.

A323830 a(0) = 1; thereafter a(n) is obtained by doubling a(n-1) and repeatedly deleting any string of identical digits.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 636, 1272, 25, 50, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 636, 1272, 25, 50, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 636, 1272, 25, 50

Offset: 0

N. J. A. Sloane, Feb 03 2019, following a suggestion from Yukun Yao

Periodic with period length 20.
Conjecture: If we start with any nonnegative number, and repeatedly double it and apply the "repeatedly delete any run of identical digits" operation described here, we eventually reach one of 0, 1, or 5.
In other words, the conjecture is that eventually we reach 0 or join the trajectory shown here or the trajectory shown in A323831.
The number of steps to reach 0, 1, or 5 is given in A323832.

			After a(15) = 32768 we get 65536 which becomes 636 after deleting "55". Then doubling 636 we get 1272, then 2544 which becomes 25 after deleting "44", then 50, then 100 which becomes 1 after deleting "00", and now the sequence repeats.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1).

Cf. A000079, A320487, A321801, A321802, A323831, A323832.

See A035615 for a classic related base-2 sequence.

dad[n_]:=FromDigits[FixedPoint[Flatten[Select[Split[#],Length[#]==1&]]&,IntegerDigits[2n]]];NestList[dad,1,100] (* Paolo Xausa, Nov 14 2023 *)

Vec((1 + 2*x)*(1 + 4*x^2 + 16*x^4 + 64*x^6 + 256*x^8 + 1024*x^10 + 4096*x^12 + 16384*x^14 + 636*x^16 + 25*x^18) / (1 - x^20) + O(x^40)) \\ Colin Barker, Feb 03 2019

From Colin Barker, Feb 03 2019: (Start)
G.f.: (1 + 2*x)*(1 + 4*x^2 + 16*x^4 + 64*x^6 + 256*x^8 + 1024*x^10 + 4096*x^12 + 16384*x^14 + 636*x^16 + 25*x^18) / (1 - x^20).
a(n) = a(n-20) for n>19.
(End)
a(n+1) = A321801(2*a(n)). For general numbers, the "repeatedly delete any run of identical digits" operation corresponds to repeatedly applying A321801. - Chai Wah Wu, Feb 11 2019

A066345 Winning binary "same game" templates of length n as defined below.

Original entry on oeis.org

1, 1, 4, 7, 20, 39, 96, 191, 432, 863, 1856, 3711, 7744, 15487, 31744, 63487, 128768, 257535, 519168, 1038335, 2085888, 4171775, 8364032, 16728063, 33501184, 67002367, 134103040, 268206079, 536625152, 1073250303, 2146959360

Offset: 1

Frank Ellermann, Dec 23 2001

A "same game template" is a pattern representing the run pattern of a string in a 2 symbol alphabet. Each position in the template represents either an isolated symbol, or a run of two or more identical symbols. Such a template can be represented as a ternary number without digit 0 (A007931), where 2 represents any run of 2 or more identical symbols and ternary 1 represents remaining single bitsymbols, e.g. 211 for 0010, 1101, 00010, etc. A winning template represents an infinite subset of winning binary "same games", e.g. 121 for 0110, 1001, 01110, etc.

			There are a(3)= 4 winning templates 121, 122, 221, 222 with 3 ternary digits and a(4)= 7 winning templates 1212, 2121, 1222, 2221, 2122, 2212, 2222.

Index entries for linear recurrences with constant coefficients, signature (2,5,-10,-8,16,4,-8).

a(2*n-1)= A008353(n-1), cf. A035615, A007931, A066067.

a(2*n-1)= 2^(2*n-1) -n * 2^(n-1), a(2*n)= 2*a(2*n-1) -1.

G.f. x*( 1-x-3*x^2+4*x^3+4*x^4-4*x^5 ) / ( (x-1)*(2*x-1)*(1+x)*(-1+2*x^2)^2 ). - R. J. Mathar, May 07 2013

A066067 Number of binary strings u of any length with property that length(u) + number of 0's in u <= n (only one of a string and its reversal are counted).

Original entry on oeis.org

1, 2, 3, 6, 10, 18, 29, 49, 78, 128, 203, 329, 523, 844, 1347, 2172, 3480, 5614, 9023, 14567, 23466, 37910, 61165, 98865, 159677, 258190, 417283, 674890, 1091214, 1765146, 2854793, 4618373, 7470614, 12086436, 19552903, 31635193, 51181367, 82809832

Offset: 1

Frank Ellermann, Dec 02 2001

nonn

If 0 is replaced by 2 (as in A007931) "length + 0-bits" is simply the total of ternary digits (e.g., 3 for 21 instead of 01).

			a(3) = 3: 0 01 111 (e.g. 01: length 2 + 1 zero = 3).
a(4) = 6: 0 01 00 011 101 1111.
a(5) =10: 0 01 00 011 101 001 010 0111 1011 11111.

Index entries for linear recurrences with constant coefficients, signature (3,-1,-4,4,-2,1,1,-1)

If reversals are counted as distinct then we obtain A000126.
A007931 (binary strings represented by ternary numbers),
Cf. A035615 (binary "same game").

CoefficientList[Series[x (-x^7-x^4+3x^3-2x^2-x+1)/((1-x-x^2) (1-x^2-x^4) (1-x)^2),{x,0,50}],x] (* Harvey P. Dale, Jun 15 2011 *)

G.f.: x*(-x^7-x^4+3x^3-2x^2-x+1)/((1-x-x^2)*(1-x^2-x^4)*(1-x)^2).

More terms from Harvey P. Dale, Jun 15 2011

A066346 Number of winning binary "same game" templates with ternary digits totaling n.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 4, 9, 13, 28, 46, 84, 146, 252, 433, 736, 1242, 2087, 3482, 5791, 9587, 15823, 26038, 42743, 70016, 114485, 186903, 304728, 496260, 807395, 1312504, 2132102, 3461407, 5616609, 9109732

Offset: 0

Frank Ellermann, Dec 23 2001

Equivalently, templates whose minimum matching string has length n.

			a(1)..a(5) correspond to the winning templates -;2;-; 121,22; 122,221.
a(6) = 4 winning templates 11211,1212,2121 and 222 have a total of 6.

Sean A. Irvine, Java program (github)

Cf. A066345 (definition), A007931 (templates). A035615 (binary same game).

a(17)-a(35) from Sean A. Irvine, Oct 09 2023

A324128 a(n) = 2nFibonacci(n) + (-1)^n + 1.

Original entry on oeis.org

2, 2, 6, 12, 26, 50, 98, 182, 338, 612, 1102, 1958, 3458, 6058, 10558, 18300, 31586, 54298, 93026, 158878, 270602, 459732, 779286, 1318222, 2225666, 3751250, 6312438, 10606572, 17797418, 29825282, 49922402, 83468678, 139411778, 232622148, 387796318, 645922550, 1074985346, 1787678458, 2970700846

Offset: 0

N. J. A. Sloane, Feb 20 2019

This sequence is distantly related to the number of losing strings using a binary alphabet in the "same game" described by Burns and Purcell (2007) and Kurz (2001). - Petros Hadjicostas, Sep 01 2019

Colin Barker, Table of n, a(n) for n = 0..1000
Chris Burns and Benjamin Purcell, Counting the number of winning strings in the 1-dimensional same game, Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials in "same game", 2001.
Index entries for linear recurrences with constant coefficients, signature (2,2,-4,-2,2,1).

Cf. A000045, A035615, A099920, A309874, A324129.

A324128[n_]:=Fibonacci[n]2n+(-1)^n+1;Array[A324128,50,0] (* Paolo Xausa, Nov 15 2023 *)

Vec(2*(1 - x - x^2 + 2*x^3 + x^4 - x^5) / ((1 - x)*(1 + x)*(1 - x - x^2)^2) + O(x^40)) \\ Colin Barker, Mar 03 2019

From Chai Wah Wu, Feb 20 2019: (Start)
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3) - 2*a(n-4) + 2*a(n-5) + a(n-6) for n > 5.
G.f.: (2*x^5 - 2*x^4 - 4*x^3 + 2*x^2 + 2*x - 2)/((x - 1)*(x + 1)*(x^2 + x - 1)^2). (End)
From Petros Hadjicostas, Sep 01 2019: (Start)
a(n) = 2*A324129(n) for n >= 0.
a(n) = A309874(n) + 2*A099920(n-1) = 2^n - A035615(n) + 2*A099920(n-1) for n >= 2.[Here A309874 counts the losing strings while A035615 counts the winning strings using a binary alphabet in the "same game". See Burns and Purcell (2007) and Kurz (2001).]
(End)

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

Original entry on oeis.org

1, 1, 3, 6, 13, 25, 49, 91, 169, 306, 551, 979, 1729, 3029, 5279, 9150, 15793, 27149, 46513, 79439, 135301, 229866, 389643, 659111, 1112833, 1875625, 3156219, 5303286, 8898709, 14912641, 24961201, 41734339, 69705889, 116311074, 193898159, 322961275

Offset: 0

N. J. A. Sloane, Feb 20 2019

Equals A324128(n)/2.

This sequence is distantly related to (one-half) the number of losing strings using a binary alphabet in the "same game" described by Burns and Purcell (2007) and Kurz (2001). - Petros Hadjicostas, Sep 01 2019

Colin Barker, Table of n, a(n) for n = 0..1000
Chris Burns and Benjamin Purcell, Counting the number of winning strings in the 1-dimensional same game, Fibonacci Quarterly, 45(3) (2007), 233-238.
Sascha Kurz, Polynomials in "same game", 2001.
Index entries for linear recurrences with constant coefficients, signature (2,2,-4,-2,2,1).

Cf. A000045, A035615, A099920, A323812, A324128.

[n*Fibonacci(n)+((-1)^n+1)/2:n in [0..35]]; // Marius A. Burtea, Aug 29 2019

A324129[n_]:=Fibonacci[n]n+((-1)^n+1)/2;Array[A324129,50,0] (* Paolo Xausa, Nov 15 2023 *)

Vec((1 - x - x^2 + 2*x^3 + x^4 - x^5) / ((1 - x)*(1 + x)*(1 - x - x^2)^2) + O(x^40)) \\ Colin Barker, Mar 03 2019

From Chai Wah Wu, Feb 20 2019: (Start)
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3) - 2*a(n-4) + 2*a(n-5) + a(n-6) for n > 5.
G.f.: (x^5 - x^4 - 2*x^3 + x^2 + x - 1)/((x - 1)*(x + 1)*(x^2 + x - 1)^2). (End)
a(n) = A309874(n)/2 + A099920(n-1) = 2^(n-1) - A035615(n)/2 + A099920(n-1) = A323812(n) + A099920(n-1) for n >= 2. [Sequence A309874 counts the losing strings while A035615 counts the winning strings using a binary alphabet in the "same game". See Burns and Purcell (2007) and Kurz (2001).] - Petros Hadjicostas, Sep 01 2019

A066709 Triangle T(r,c) of winning binary "same game" templates.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 0, 2, 4, 1, 1, 5, 8, 5, 1, 0, 3, 14, 15, 6, 1, 1, 9, 25, 32, 21, 7, 1, 0, 4, 32, 62, 56, 28, 8, 1, 1, 14, 56, 109, 122, 84, 36, 9, 1, 0, 5, 60, 170, 242, 210, 120, 45, 10, 1, 1, 20, 105, 275, 436, 457, 330, 165, 55, 11, 1, 0, 6, 100, 375, 732, 912, 792, 495, 220, 66, 12, 1

Offset: 1

Frank Ellermann, Dec 31 2001

T(r,c) is the number of winning templates with length r and minimum matching string length c; equivalently, ternary digits totaling r+c. For a definition and row sums 1,1,4,7,20, etc. see A066345. For antidiagonal sums 1,0,2,2,4,9, etc. see A066346.

			Rows:
1;
0,1;
1,2,1;
0,2,4,1;
1,5,8,5,1;
0,3,14,15,6,1; ...
a(17) = T(6,2) = 3 winning templates with length 6 and total 8 = 6+2: 211211, 121121, 112112.
A035615(6) = 2*( 1*1+0*1+1*3+1*1+2*2+1*1+1*1+0*1+2*1+1*1 ) = 2*13 = 26.

Sean A. Irvine, Java program (github)

Cf. A035615, A066345, A066346, A007318.

A035615(n) = 2 * Sum_{r=1..n-1, c=1..min(r,n-r)} T(r,c) * P(n-r,c) where P(n-r,c) = C(n-r-1,c-1) = (n-r-1)!/((n-r-c-2)!*(c-1)!).

More terms from Sean A. Irvine, Nov 03 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A323830 a(0) = 1; thereafter a(n) is obtained by doubling a(n-1) and repeatedly deleting any string of identical digits.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066345 Winning binary "same game" templates of length n as defined below.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A066067 Number of binary strings u of any length with property that length(u) + number of 0's in u <= n (only one of a string and its reversal are counted).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A066346 Number of winning binary "same game" templates with ternary digits totaling n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

A324128 a(n) = 2nFibonacci(n) + (-1)^n + 1.