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

2, 4, 8, 16, 24, 48, 96, 192, 384, 576, 1152, 2304, 3456, 6912, 10368, 20736, 31104, 62208, 124416, 186624, 373248, 746496, 1492992, 2985984, 3234816, 4829184, 9658368, 19316736, 28975104, 43462656, 86925312, 173850624, 347701248, 519561216, 779341824, 1558683648

Offset: 1

Author

Robert Israel, May 04 2016

Keywords

• nonn

Comments

a(7824) >= 8, but a(n) = 0 for n >= 7825.

a(n) <= 2*a(n-1), with equality if n has no prime factor == 1 mod 4.

Examples

			For n <= 4, a(n) = 2^n because all 2-colorings are admissible.
For n = 5, there are 32 2-colorings of which 8 have 3,4,5 monochromatic, so a(5) = 32 - 8 = 24.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..56
• M. J. H. Heule, O. Kullmann, and V. W. Marek, Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer, arXiv:1605.00723 [cs.DM].

Programs

Maple

PPT:= proc(c) local m,n; option remember;
  map(proc(p) local mm,nn; mm:= subs(p,m); nn:= subs(p,n);
    if mm-nn>= 1 and nn >= 1 and igcd(mm,nn)=1 then
      [mm^2-nn^2, 2*mm*nn,c]
    else NULL
    fi
  end proc, {isolve(m^2+n^2=c)})
end proc:
PT:= proc(c) local k;
   `union`(seq(map(`*`,PPT(k),c/k), k = select(t -> t mod 4 = 1, numtheory:-divisors(c))))
end proc:
extend:= proc(C,n,PTn) local b0, b1;
   b0:= not ormap(t -> {t[1],t[2]} subset C, PTn);
   b1:= not ormap(t -> {t[1],t[2]} intersect C = {}, PTn);
   if b0 then
      if b1 then C, C union {n}
      else C union {n}
      fi
   elif b1 then C
   else NULL
   fi
end proc:
CC[3]:= {{}}:
for n from 4 to 30 do
  CC[n]:= map(extend,CC[n-1],n,PT(n));
od:
2,4,seq(8*nops(CC[n]),n=3..30);