cp's OEIS Frontend

A378196 Number of 2-colorings of length n without an arithmetic progression of length 4.

%I A378196 #7 Jun 02 2025 15:28:40
%S A378196 1,2,4,8,14,26,48,78,132,230,356,548,842,1078,1344,1764,1744,1850,
%T A378196 1948,1708,1442,1342,1032,702,524,316,168,136,136,144,152,160,168,176,
%U A378196 28,0
%N A378196 Number of 2-colorings of length n without an arithmetic progression of length 4.
%C A378196 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.
%t A378196 HasEquallySpacedKBits[bits_, k_] :=
%t A378196  If[k == 1, True,
%t A378196   Module[{n = Length[bits], found = False},
%t A378196    Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
%t A378196        bits[[start]]] == k, found = True; Break[]], {gap, 1,
%t A378196      Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
%t A378196    found]]
%t A378196 BitSequence[k_] :=
%t A378196  Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
%t A378196   ExtendSequence[seq_] :=
%t A378196    Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
%t A378196     newSeq1 = Join[seq, {1}];
%t A378196     If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
%t A378196     If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
%t A378196     result];
%t A378196   Function[targetN,
%t A378196    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
%t A378196    While[n < targetN, n++;
%t A378196     currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
%t A378196     prevSequences = currSequences;
%t A378196     Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];];]]
%t A378196 BitSequence[4][35]
%t A378196 (* _Ethan Ji_, Nov 19 2024 *)
%Y A378196 First 0 index given by A005346.
%Y A378196 Cf. A378195, A378197.
%K A378196 nonn
%O A378196 0,2
%A A378196 _Ethan Ji_, Nov 19 2024