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

%I #10 May 19 2016 19:54:51

%S 2,4,8,16,24,48,96,192,384,576,1152,2304,3456,6912,10368,20736,31104,

%T 62208,124416,186624,373248,746496,1492992,2985984,3234816,4829184,

%U 9658368,19316736,28975104,43462656,86925312,173850624,347701248,519561216,779341824,1558683648

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

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

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

%H Robert Israel, <a href="/A272709/b272709.txt">Table of n, a(n) for n = 1..56</a>

%H 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 For n <= 4, a(n) = 2^n because all 2-colorings are admissible.

%e For n = 5, there are 32 2-colorings of which 8 have 3,4,5 monochromatic, so a(5) = 32 - 8 = 24.

%p PPT:= proc(c) local m,n; option remember;

%p map(proc(p) local mm,nn; mm:= subs(p,m); nn:= subs(p,n);

%p if mm-nn>= 1 and nn >= 1 and igcd(mm,nn)=1 then

%p [mm^2-nn^2, 2*mm*nn,c]

%p else NULL

%p fi

%p end proc, {isolve(m^2+n^2=c)})

%p end proc:

%p PT:= proc(c) local k;

%p `union`(seq(map(`*`,PPT(k),c/k), k = select(t -> t mod 4 = 1, numtheory:-divisors(c))))

%p end proc:

%p extend:= proc(C,n,PTn) local b0, b1;

%p b0:= not ormap(t -> {t[1],t[2]} subset C, PTn);

%p b1:= not ormap(t -> {t[1],t[2]} intersect C = {}, PTn);

%p if b0 then

%p if b1 then C, C union {n}

%p else C union {n}

%p fi

%p elif b1 then C

%p else NULL

%p fi

%p end proc:

%p CC[3]:= {{}}:

%p for n from 4 to 30 do

%p CC[n]:= map(extend,CC[n-1],n,PT(n));

%p od:

%p 2,4,seq(8*nops(CC[n]),n=3..30);

%K nonn

%O 1,1

%A _Robert Israel_, May 04 2016