A378195 Number of 2-colorings of length n without an arithmetic progression of length 3

1, 2, 4, 6, 10, 14, 20, 16, 6, 0

Offset

0,2

Comments

After 0, the sequence will continue to be 0. A sequence satisfying this property cannot have a subsequence which violates it, thus there must exist a sequence of length n-1 if there exists a sequence of length n.

Links

Table of n, a(n) for n=0..9.

Example

a(3) = 6 since we have [0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0].

Mathematica

HasEquallySpacedKBits[bits_, k_] :=
 If[k == 1, True,
  Module[{n = Length[bits], found = False},
   Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
       bits[[start]]] == k, found = True; Break[]], {gap, 1,
     Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
   found]]
BitSequence[k_] :=
 Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
  ExtendSequence[seq_] :=
   Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
    newSeq1 = Join[seq, {1}];
    If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
    If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
    result];
  Function[targetN,
   Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
   While[n < targetN, n++;
    currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
    prevSequences = currSequences;
    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]]; ]; ]]
BitSequence[3][9]
(* Ethan Ji, Nov 19 2024 *)

Crossrefs

First 0 index given by A005346.

Cf. A378196, A378197.

Sequence in context: A036641 A260732 A062425 * A121386 A007777 A082379

Adjacent sequences: A378190 A378191 A378192 * A378196 A378197 A378198

Keyword

nonn,new

Author

Ethan Ji, Nov 19 2024

Status

approved