cp's OEIS Frontend

A378197 Number of 2-colorings of length n without an arithmetic progression of length 5.

%I A378197 #14 Nov 23 2024 03:37:17
%S A378197 1,2,4,8,16,30,58,112,216,400,740,1398,2638,4710,8444,15118,27690,
%T A378197 48406,84382,146928,255844,402998,625824,956370,1447476,2066828,
%U A378197 3225856,5020232,7823236,10975318,15264202,21500308,30004914,39030820,50728472,65402746,88886116
%N A378197 Number of 2-colorings of length n without an arithmetic progression of length 5.
%C A378197 After a(178) = 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.
%H A378197 Michael De Vlieger, <a href="/A378197/b378197.txt">Table of n, a(n) for n = 0..178</a>
%t A378197 HasEquallySpacedKBits[bits_, k_] :=
%t A378197  If[k == 1, True,
%t A378197   Module[{n = Length[bits], found = False},
%t A378197    Do[If[Count[Table[bits[[start + gap*i]], {i, 0, k - 1}],
%t A378197        bits[[start]]] == k, found = True; Break[]], {gap, 1,
%t A378197      Floor[n/(k - 1)]}, {start, 1, n - gap*(k - 1)}];
%t A378197    found]]
%t A378197 BitSequence[k_] :=
%t A378197  Module[{prevSequences = {{}}, currSequences, n = 0, ExtendSequence},
%t A378197   ExtendSequence[seq_] :=
%t A378197    Module[{newSeq0, newSeq1, result = {}}, newSeq0 = Join[seq, {0}];
%t A378197     newSeq1 = Join[seq, {1}];
%t A378197     If[! HasEquallySpacedKBits[newSeq0, k], AppendTo[result, newSeq0]];
%t A378197     If[! HasEquallySpacedKBits[newSeq1, k], AppendTo[result, newSeq1]];
%t A378197     result];
%t A378197   Function[targetN,
%t A378197    Print["k=", k, ", n=", n, ": count=", Length[prevSequences]];
%t A378197    While[n < targetN, n++;
%t A378197     currSequences = Flatten[ExtendSequence /@ prevSequences, 1];
%t A378197     prevSequences = currSequences;
%t A378197     Print["k=", k, ", n=", n, ": count=", Length[prevSequences]]; ]; ]]
%t A378197 BitSequence[5][178]
%t A378197 (* _Ethan Ji_, Nov 19 2024 *)
%Y A378197 First 0 index given by A005346.
%Y A378197 Cf. A378195, A378196.
%K A378197 nonn
%O A378197 0,2
%A A378197 _Ethan Ji_, Nov 19 2024