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,1

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.

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].

Example

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.

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);

Crossrefs

Sequence in context: A369151 A222089 A182763 * A119311 A305183 A360642

Adjacent sequences: A272706 A272707 A272708 * A272710 A272711 A272712

Keyword

nonn

Author

Robert Israel, May 04 2016

Status

approved