Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find a minimal set of Pythagorean triples that cannot be coloured with three colours such that all triples have all three colours; see http://math.stackexchange.com/questions/1816353.
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class Question1816353 {
final static int max = 111;
final static Random random = new Random ();
static int [] colours = new int [max + 1];
static List<int []> triples;
public static void main (String [] args) {
triples = new ArrayList<int[]> ();
List<int []> allTriples = new ArrayList<int []> ();
for (int a = 1;a <= max;a++)
for (int b = a + 1;b <= max;b++)
for (int c = b + 1;c <= max;c++)
if (a * a + b * b == c * c)
allTriples.add (new int [] {a,b,c});
List<int []> requiredTriples = new ArrayList<int []> ();
List<int []> optionalTriples = new ArrayList<int []> ();
for (int i = 0;i < allTriples.size ();i++) {
triples = new ArrayList<int []> (allTriples);
triples.remove (i);
(check () ? requiredTriples : optionalTriples).add (allTriples.get (i));
}
int [] types = new int [optionalTriples.size ()];
Arrays.fill (types,1);
for (int n = 0;n <= 8;n++)
new Multiset (types).traverseSubsets (n,new MultisetHandler () {
public void handle (int [] multiset,BigInteger multiplicity) {
triples = new ArrayList<int []> (requiredTriples);
for (int i = 0;i < multiset.length;i++)
if (multiset [i] == 1)
triples.add (optionalTriples.get (i));
if (!check ()) {
System.out.println ("minimal configuration (" + triples.size () + "):");
for (int [] triple : triples)
System.out.println ("(" + triple [0] + "," + triple [1] + "," + triple [2] + ")");
System.out.println ();
}
}
});
outer:
for (;;) {
triples = new ArrayList<int []> (allTriples);
int nfailures = 0;
inner:
for (;;) {
int [] removed = triples.remove (random.nextInt (triples.size ()));
if (check ()) {
triples.add (0,removed);
if (++nfailures > 20) {
List<int []> left = new ArrayList<int []> (triples);
for (int i = 0;i < left.size ();i++) {
triples = new ArrayList<int []> (left);
triples.remove (i);
if (!check ()) {
nfailures = 0;
continue inner;
}
}
int [] [] a = left.toArray (new int [left.size ()] []);
Arrays.sort (a,new Comparator<int []>() {
public int compare (int [] o1,int [] o2) {
for (int i = 2;i >= 0;i--) {
int diff = o1 [i] - o2 [i];
if (diff != 0)
return diff;
}
return 0;
}
});
System.out.println ("minimal configuration (" + a.length + "):");
for (int [] triple : a)
System.out.println ("(" + triple [0] + "," + triple [1] + "," + triple [2] + ")");
System.out.println ();
continue outer;
}
}
else
nfailures = 0;
}
}
}
static int [] [] ps = {
{1,2,3},
{1,3,2},
{2,1,3},
{2,3,1},
{3,1,2},
{3,2,1}
};
static boolean check () {
return recurse (0);
}
static boolean recurse (int i) {
if (i == triples.size ())
return true;
int [] triple = triples.get (i);
int c1 = colours [triple [0]];
int c2 = colours [triple [1]];
int c3 = colours [triple [2]];
outer:
for (int [] p : ps) {
for (int j = 0;j < 3;j++)
if (colours [triple [j]] != 0 && colours [triple [j]] != p [j])
continue outer;
for (int j = 0;j < 3;j++)
colours [triple [j]] = p [j];
boolean success = recurse (i + 1);
colours [triple [0]] = c1;
colours [triple [1]] = c2;
colours [triple [2]] = c3;
if (success)
return true;
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment