cp's OEIS Frontend

A272709 Number of 2-colorings of [1..n] with no monochromatic Pythagorean triple.

%I A272709 #10 May 19 2016 19:54:51
%S A272709 2,4,8,16,24,48,96,192,384,576,1152,2304,3456,6912,10368,20736,31104,
%T A272709 62208,124416,186624,373248,746496,1492992,2985984,3234816,4829184,
%U A272709 9658368,19316736,28975104,43462656,86925312,173850624,347701248,519561216,779341824,1558683648
%N A272709 Number of 2-colorings of [1..n] with no monochromatic Pythagorean triple.
%C A272709 a(7824) >= 8, but a(n) = 0 for n >= 7825.
%C A272709 a(n) <= 2*a(n-1), with equality if n has no prime factor == 1 mod 4.
%H A272709 Robert Israel, <a href="/A272709/b272709.txt">Table of n, a(n) for n = 1..56</a>
%H A272709 M. J. H. Heule, O. Kullmann, and V. W. Marek, <a href="http://arxiv.org/abs/1605.00723">Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer</a>, arXiv:1605.00723 [cs.DM].
%e A272709 For n <= 4, a(n) = 2^n because all 2-colorings are admissible.
%e A272709 For n = 5, there are 32 2-colorings of which 8 have 3,4,5 monochromatic, so a(5) = 32 - 8 = 24.
%p A272709 PPT:= proc(c) local m,n; option remember;
%p A272709   map(proc(p) local mm,nn; mm:= subs(p,m); nn:= subs(p,n);
%p A272709     if mm-nn>= 1 and nn >= 1 and igcd(mm,nn)=1 then
%p A272709       [mm^2-nn^2, 2*mm*nn,c]
%p A272709     else NULL
%p A272709     fi
%p A272709   end proc, {isolve(m^2+n^2=c)})
%p A272709 end proc:
%p A272709 PT:= proc(c) local k;
%p A272709    `union`(seq(map(`*`,PPT(k),c/k), k = select(t -> t mod 4 = 1, numtheory:-divisors(c))))
%p A272709 end proc:
%p A272709 extend:= proc(C,n,PTn) local b0, b1;
%p A272709    b0:= not ormap(t -> {t[1],t[2]} subset C, PTn);
%p A272709    b1:= not ormap(t -> {t[1],t[2]} intersect C = {}, PTn);
%p A272709    if b0 then
%p A272709       if b1 then C, C union {n}
%p A272709       else C union {n}
%p A272709       fi
%p A272709    elif b1 then C
%p A272709    else NULL
%p A272709    fi
%p A272709 end proc:
%p A272709 CC[3]:= {{}}:
%p A272709 for n from 4 to 30 do
%p A272709   CC[n]:= map(extend,CC[n-1],n,PT(n));
%p A272709 od:
%p A272709 2,4,seq(8*nops(CC[n]),n=3..30);
%K A272709 nonn
%O A272709 1,1
%A A272709 _Robert Israel_, May 04 2016