cp's OEIS Frontend

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

%I A378195 #8 Jun 02 2025 15:28:35
%S A378195 1,2,4,6,10,14,20,16,6,0
%N A378195 Number of 2-colorings of length n without an arithmetic progression of length 3.
%C A378195 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.
%e A378195 a(3) = 6 since we have [0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0].
%t A378195 HasEquallySpacedKBits[bits_, k_] :=
%t A378195  If[k == 1, True,
%t A378195   Module[{n = Length[bits], found = False},
%t A378195    Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
%t A378195        bits[[start]]] == k, found = True; Break[]], {gap, 1,
%t A378195      Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
%t A378195    found]]
%t A378195 BitSequence[k_] :=
%t A378195  Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
%t A378195   ExtendSequence[seq_] :=
%t A378195    Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
%t A378195     newSeq1 = Join[seq, {1}];
%t A378195     If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
%t A378195     If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
%t A378195     result];
%t A378195   Function[targetN,
%t A378195    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
%t A378195    While[n < targetN, n++;
%t A378195     currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
%t A378195     prevSequences = currSequences;
%t A378195     Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];];]]
%t A378195 BitSequence[3][9]
%t A378195 (* _Ethan Ji_, Nov 19 2024 *)
%Y A378195 First 0 index given by A005346.
%Y A378195 Cf. A378196, A378197.
%K A378195 nonn
%O A378195 0,2
%A A378195 _Ethan Ji_, Nov 19 2024