login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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(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: A089827 A222089 A182763 * A119311 A305183 A112992

Adjacent sequences:  A272706 A272707 A272708 * A272710 A272711 A272712

KEYWORD

nonn

AUTHOR

Robert Israel, May 04 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 25 13:50 EDT 2019. Contains 326324 sequences. (Running on oeis4.)