login
A272709
Number of 2-colorings of [1..n] with no monochromatic Pythagorean triple.
1
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
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
KEYWORD
nonn
AUTHOR
Robert Israel, May 04 2016
STATUS
approved