A291779 -id:A291779 - cp's OEIS frontend

A004523 Two even followed by one odd; or floor(2n/3).

0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 18, 18, 19, 20, 20, 21, 22, 22, 23, 24, 24, 25, 26, 26, 27, 28, 28, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 36, 36, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 44, 44, 45, 46

Offset: 0

N. J. A. Sloane

Guenther Rosenbaum showed that the sequence represents the optimal number of guesses in the static Mastermind game with two pegs. Namely, the optimal number of static guesses equals 2k, if the number of colors is either (3k - 1) or 3k and is (2k + 1), if the number of colors is (3k + 1), k >= 1. - Alex Bogomolny, Mar 06 2002
First differences are in A011655. - R. J. Mathar, Mar 19 2008
a(n+1) is the maximum number of wins by a team in a sequence of n basketball games if the team's longest winning streak is 2 games. See example below. In general, floor(k(n+1)/(k+1)) gives the maximum number of wins in n games when the longest winning streak is of length k. - Dennis P. Walsh, Apr 18 2012
Sum_{n>=2} 1/a(n)^k = Sum_{j>=1} Sum_{i=1..2} 1/(i*j)^k = Zeta(k)^2 - Zeta(k)*Zeta(k,3), where Zeta(,) is the generalized Riemann zeta function, for the case k=2 this sum is 5*Pi^2/24. - Enrique Pérez Herrero, Jun 25 2012
a(n) is the pattern of (0+2k, 0+2k, 1+2k), k>=0. a(n) is also the number of odd integers divisible by 3 in ]2(n-1)^2, 2n^2[. - Ralf Steiner, Jun 25 2017
a(n) is also the total domination number of the n-triangular (Johnson) graph for n > 2. - Eric W. Weisstein, Apr 09 2018
a(n) is the maximum total domination number of connected graphs with order n>2.  The extremal graphs are "brushes", as defined in the links below. - Allan Bickle, Dec 24 2021
a(n) is the minimal number of ascending or descending staircase walks necessary to cover a chessboard of size n-1, for n > 1. See Ackerman and Pinchasi. - Sela Fried, Jan 16 2023

			For n=11, we have a(11)=7 since there are at most 7 wins by a team in a sequence of 10 games in which its longest winning streak is 2 games. One such win-loss sequence with 7 wins is wwlwwlwwlw. - _Dennis P. Walsh_, Apr 18 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
E. Ackerman and R. Pinchasi, Covering a chessboard with staircase walks, Discrete Mathematics, 313 (2013).
Allan Bickle, Two Short Proofs on Total Domination, Discuss Math Graph Theory, 33 2 (2013), 457-459.
Alex Bogomolny and Don Greenwell, Static Mastermind Game, Cut The Knot!, December 1999.
R. C. Brigham, J. R. Carrington, and R. P. Vitray, Connected graphs with maximum total domination number, J. Combin. Comput. Combin. Math. 34 (2000), 81-96.
E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211-219.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47.
Francis Laclé, 2-adic parity explorations of the 3n+ 1 problem, hal-03201180v2 [cs.DM], 2021.
G. Rosenbaum, (Static-)Mastermind.
Paul B. Slater, Formulas for Generalized Two-Qubit Separability Probabilities, arXiv:1609.08561 [quant-ph], 2016.
Paul B. Slater, Hypergeometric/Difference-Equation-Based Separability Probability Formulas and Their Asymptotics for Generalized Two-Qubit States Endowed with Random Induced Measure, arXiv:1504.04555 [quant-ph], 2015.
Eric Weisstein's World of Mathematics, Johnson Graph.
Eric Weisstein's World of Mathematics, Total Domination Number.
Eric Weisstein's World of Mathematics, Triangular Graph.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Cf. A003881, A004396, A004773, A182210, A291778, A291779.

Zero followed by partial sums of A011655.

a004523 n = a004523_list !! n
a004523_list = 0 : 0 : 1 : map (+ 2) a004523_list
-- Reinhard Zumkeller, Nov 06 2012

[Floor(2*n/3): n in [0..50]]; // G. C. Greubel, Nov 02 2017

Maple
```
seq(floor(2n/3), n=0..75);
```

Table[Floor[2 n/3], {n, 0, 75}]
Table[(6 n + 3 Cos[2 n Pi/3] - Sqrt[3] Sin[2 n Pi/3] - 3)/9, {n, 0, 20}] (* Eric W. Weisstein, Apr 08 2018 *)
Floor[2 Range[0, 20]/3] (* Eric W. Weisstein, Apr 08 2018 *)
LinearRecurrence[{1, 0, 1, -1}, {0, 1, 2, 2}, {0, 20}] (* Eric W. Weisstein, Apr 08 2018 *)
CoefficientList[Series[x^2 (1 + x)/((-1 + x)^2 (1 + x + x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 08 2018 *)
Table[If[EvenQ[n],{n,n},n],{n,0,50}]//Flatten (* Harvey P. Dale, May 27 2021 *)

a(n)=2*n\3 \\ Charles R Greathouse IV, Sep 02 2015

G.f.: (x^2 + 2*x^3 + 2*x^4 + x^5)/(1 - x^3)^2, not reduced. - Len Smiley
a(n) = floor(2*n/3).
a(0) = a(1) = 0; for n > 1, a(n) = n - 1 - floor(a(n-1)/2). - Benoit Cloitre, Nov 26 2002
a(n) = a(n-1) + (1/2)*((-1)^floor((2*n+2)/3)+1), with a(0)=0. - Mario Catalani (mario.catalani(AT)unito.it), Oct 20 2003
a(n) = Sum_{k=0..n-1} (Fibonacci(k) mod 2). - Paul Barry, May 31 2005
a(n) = A004773(n) - A004396(n). - Reinhard Zumkeller, Aug 29 2005
O.g.f.: x^2*(1 + x)/((1 - x)^2*(1 + x + x^2)). - R. J. Mathar, Mar 19 2008
a(n) = ceiling(2*(n-1)/3) = n - 1 - floor((n-1)/3). - Bruno Berselli, Jan 18 2017
a(n) = (6*n - 3 + 2*sqrt(3)*sin(2*(n-2)*Pi/3))/9. - Wesley Ivan Hurt, Sep 30 2017
Sum_{n>=2} (-1)^n/a(n) = Pi/4 (A003881). - Amiram Eldar, Sep 29 2022

A291068 Largest number of distinct words arising in Watanabe's tag system {00, 1110} applied to a binary word w, over all starting words w of length n.

Original entry on oeis.org

6, 5, 4, 15, 14, 13, 26, 25, 24, 39, 38, 37, 54, 53, 52, 69, 68, 67, 86, 85, 84, 103, 102, 101, 120, 119, 118, 139, 138, 137, 158, 157, 156, 177, 176, 175, 196, 195, 194, 215, 214, 213, 236, 235, 234, 257, 256, 255, 278, 277

Offset: 1

N. J. A. Sloane, Aug 18 2017

Watanabe's tag system {00, 1110} maps a word w over {0,1} to w', where if w begins with 0, w' is obtained by appending 00 to w and deleting the first three letters, or if w begins with 1, w' is obtained by appending 1110 to w and deleting the first three letters.
The empty word is included in the count.
Comment from Don Reble, Aug 25 2017: (Start)
The following comment applies to both the 3-shift tag systems {00,1110} (A291068) and {00,0111} (A291069). Number the bits in a binary word w starting at the left with bit 0. For the trajectory of w under the tag system, only bits numbered 0,3,6,9,... are important, the others (the unimportant bits) having no effect on the outcome.
An important 1 bit produces 0111 or 1110, and exactly one of those new 1 bits is important. The number of important 1's never changes. So the number of initial words of length n that terminate (the analog of A289670) is just 2^(number-of-unimportant-bits) = 2^(floor(2*n/3)) = A291778.
The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.
Furthermore, the number of important zeros is eventually bounded.
Proof. If a word has A important zeros and B important ones, then after A+B steps, there will be at most 2A+4B bits, and at most (2A+4B+2)/3 important bits. B of them are important ones, so at most (2A+B+2)/3 are important zeros.
If A >= B+3, then (2A+B+2)/3 <= (2A+A-1)/3 < A. If A < B+3, then (2A+B+2)/3 < (3B+8)/3 = B+2. The first kind must shrink; the second kind can't grow past A+B+2. QED
Ultimately, a word with B important ones has at most A+B+2 important bits, so can't diverge. So the word "finite" in the definition was unnecessary and has been omitted. (End)

			Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

Shigeru Watanabe, Periodicity of Post's normal process of tag, in Jerome Fox, ed., Proceedings of Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press, Polytechnic Institute of Brooklyn, 1963, pp. 83-99. [Annotated scanned copy]
N. J. A. Sloane, Maple programs that compute first 7 terms for each of A284116, A291067, A291068, A291069

For the 3-shift tag systems {00,1101}, {00, 1011}, {00, 1110}, {00, 0111} see A284116, A291067, A291068, A291069 respectively (as well as the cross-referenced entries mentioned there).

Cf. A291073.

Maple
```
See link.
```

a(8)-(50) from Lars Blomberg, Sep 16 2017

A291069 Largest number of distinct words arising in Watanabe's tag system {00, 0111} applied to a binary word w, over all starting words w of length n.

Original entry on oeis.org

5, 4, 4, 14, 13, 12, 25, 24, 23, 38, 37, 36, 53, 52, 51, 68, 67, 66, 85, 84, 83, 102, 101, 100, 119, 118, 117, 138, 137, 136, 157, 156, 155, 176, 175, 174, 195, 194, 193, 214, 213, 212, 235, 234, 233, 256, 255, 254, 277, 276

Offset: 1

N. J. A. Sloane, Aug 18 2017

Watanabe's tag system {00, 0111} maps a word w over {0,1} to w', where if w begins with 0, w' is obtained by appending 00 to w and deleting the first three letters, or if w begins with 1, w' is obtained by appending 0111 to w and deleting the first three letters.
The empty word is included in the count.
Comment from Don Reble, Aug 25 2017: (Start)
The following comment applies to both the 3-shift tag systems {00,1110} (A291068) and {00,0111} (A291069). Number the bits in a binary word w starting at the left with bit 0. For the trajectory of w under the tag system, only bits numbered 0,3,6,9,... are important, the others (the unimportant bits) having no effect on the outcome.
An important 1 bit produces 0111 or 1110, and exactly one of those new 1 bits is important. The number of important 1's never changes. So the number of initial words of length n that terminate (the analog of A289670) is just 2^(number-of-unimportant-bits) = 2^(floor(2*n/3)) = A291778.
The number that end in a cycle is 2^n - 2^(floor(2*n/3)) = A291779.
Furthermore, the number of important zeros is eventually bounded.
Proof. If a word has A important zeros and B important ones, then after A+B steps, there will be at most 2A+4B bits, and at most (2A+4B+2)/3 important bits. B of them are important ones, so at most (2A+B+2)/3 are important zeros.
If A >= B+3, then (2A+B+2)/3 <= (2A+A-1)/3 < A. If A < B+3, then (2A+B+2)/3 < (3B+8)/3 = B+2. The first kind must shrink; the second kind can't grow past A+B+2. QED
Ultimately, a word with B important ones has at most A+B+2 important bits, so can't diverge. So the word "finite" in the definition was unnecessary and has been omitted. (End)

			Examples of strings that achieve these records: "1", "10", "000", "1001", "10010", "100100", "1001001".

Shigeru Watanabe, Periodicity of Post's normal process of tag, in Jerome Fox, ed., Proceedings of Symposium on Mathematical Theory of Automata, New York, April 1962, Polytechnic Press, Polytechnic Institute of Brooklyn, 1963, pp. 83-99. [Annotated scanned copy]
N. J. A. Sloane, Maple programs that compute first 7 terms for each of A284116, A291067, A291068, A291069

For the 3-shift tag systems {00,1101}, {00, 1011}, {00, 1110}, {00, 0111} see A284116, A291067, A291068, A291069 respectively (as well as the cross-referenced entries mentioned there).

Cf. A291074.

Maple
```
See link.
```

a(8)-(50) from Lars Blomberg, Sep 16 2017

A291778 a(n) = 2^floor(2*n/3).

Original entry on oeis.org

1, 1, 2, 4, 4, 8, 16, 16, 32, 64, 64, 128, 256, 256, 512, 1024, 1024, 2048, 4096, 4096, 8192, 16384, 16384, 32768, 65536, 65536, 131072, 262144, 262144, 524288, 1048576, 1048576, 2097152, 4194304, 4194304, 8388608, 16777216, 16777216, 33554432, 67108864, 67108864

Offset: 0

Don Reble and N. J. A. Sloane, Aug 31 2017

nonn

Robert Israel, Table of n, a(n) for n = 0..4978
Index entries for linear recurrences with constant coefficients, signature (0,0,4).

Cf. A004523, A291779.

seq(2^floor(2*n/3),n=0..100); # Robert Israel, Sep 01 2017

LinearRecurrence[{0, 0, 4}, {1, 1, 2}, 41] (* Jean-François Alcover, Apr 02 2019 *)

a(n) = 2^A004523(n).
G.f.: (1+x+2*x^2)/(1-4*x^3). - Robert Israel, Sep 01 2017
From Amiram Eldar, Sep 29 2022: (Start)
Sum_{n>=0} 1/a(n) =  10/3.
Sum_{n>=0} (-1)^n/a(n) = 2/5. (End)

A059409 a(n) = 4^n * (2^n - 1).

Original entry on oeis.org

0, 4, 48, 448, 3840, 31744, 258048, 2080768, 16711680, 133955584, 1072693248, 8585740288, 68702699520, 549688705024, 4397778075648, 35183298347008, 281470681743360, 2251782633816064, 18014329790005248, 144114913197948928, 1152920405095219200

Offset: 0

N. J. A. Sloane, Alford Arnold, Jan 30 2001

Jordan's totient functions are described more fully in A059379 and A059380; for example, J_1(n) is Euler's totient function and J_2(n) the Moebius transform of squares.

			(4,48,448,3840,...) = (8,64,512,4096,...) - (2,12,56,240,...) - (1,3,7,15,...) - (1,1,1,1,...)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 199, #3.

Harry J. Smith, Table of n, a(n) for n = 0..100
Index entries for linear recurrences with constant coefficients, signature (12,-32).

Cf. A059379, A059380, A016152.
Cf. A024023, A000225, A000012.
Cf. A065442.

List([0..100], n->4^n * (2^n - 1)); # Muniru A Asiru, Jan 29 2018

[4^n*(2^n - 1): n in [0..40]]; // Vincenzo Librandi, Apr 26 2011

seq(4^n * (2^n - 1), n=0..20); # Muniru A Asiru, Jan 29 2018

Table[4^n*(2^n - 1), {n,0,30}] (* G. C. Greubel, Jan 29 2018 *)
LinearRecurrence[{12,-32},{0,4},20] (* Harvey P. Dale, Oct 14 2019 *)

a(n) = { 4^n*(2^n - 1) } \\ Harry J. Smith, Jun 26 2009

Equals J_n(8) (see A059379).
J_n(8) = 8^n - A024023(n) - A000225(n) - A000012(n).
a(n) = 4*A016152(n).
G.f.: 4*x / ( (8*x-1)*(4*x-1) ). - R. J. Mathar, Nov 23 2018
Sum_{n>0} 1/a(n) = E - 4/3, where E is the Erdős-Borwein constant (A065442). - Peter McNair, Dec 19 2022
a(n) = A291779(A008585(n)) = A045991(A000079(n)). - Mathew Englander, Feb 08 2024

cp's OEIS Frontend

A004523 Two even followed by one odd; or floor(2n/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A291068 Largest number of distinct words arising in Watanabe's tag system {00, 1110} applied to a binary word w, over all starting words w of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A291069 Largest number of distinct words arising in Watanabe's tag system {00, 0111} applied to a binary word w, over all starting words w of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A291778 a(n) = 2^floor(2*n/3).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059409 a(n) = 4^n * (2^n - 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula