

A272709


Number of 2colorings 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

a(7824) >= 8, but a(n) = 0 for n >= 7825.
a(n) <= 2*a(n1), 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 CubeandConquer, arXiv:1605.00723 [cs.DM].


EXAMPLE

For n <= 4, a(n) = 2^n because all 2colorings are admissible.
For n = 5, there are 32 2colorings 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 mmnn>= 1 and nn >= 1 and igcd(mm, nn)=1 then
[mm^2nn^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[n1], n, PT(n));
od:
2, 4, seq(8*nops(CC[n]), n=3..30);


CROSSREFS

Sequence in context: A089827 A222089 A182763 * A119311 A305183 A112992
Adjacent sequences: A272706 A272707 A272708 * A272710 A272711 A272712


KEYWORD

nonn


AUTHOR

Robert Israel, May 04 2016


STATUS

approved



