// Code by Jonathan Lee and Andy Huchala. import java.util.*; import java.math.*; import java.util.stream.*; import java.io.*; import static java.lang.Math.toIntExact; class Pair implements Comparable { public Pair(long coordinates, double log) { this.coordinates = coordinates; this.log = log; } public int compareTo(Object other) { if (this.log - ((Pair) other).log < 0) { return -1; } return 1; } public double log; public long coordinates; } public class e7_irreps { static int UPPER_BOUND_FACTOR = 5000000; static double[] cachedLogs = new double[UPPER_BOUND_FACTOR]; static int[] cums = {0, 7, 16, 23, 34, 40, 48, 57}; static BigInteger bigDenom = new BigInteger("19403468278119790545603479218421760000000000"); public static void main(String[] args) { for (int i = 1; i < UPPER_BOUND_FACTOR; i++) { cachedLogs[i] = Math.log(i); } long x = 0L; PriorityQueue fringe = new PriorityQueue(); HashSet seen = new HashSet(); int numToCompute = 1000000000; int numComputed = 0; double irrep = ComputeIrrep(x); fringe.add(new Pair(x, irrep)); double lastLog = 0.0; long lastCoord = -1; int ind = 0; try { PrintWriter writer = new PrintWriter("b121736.txt", "UTF-8"); while (numComputed++ < numToCompute) { if (numComputed % 250000 == 0) { // double high = 0.0; // for (Pair p : fringe) { // if (p.log > high) { // high = p.log; // } // } System.out.println(numComputed + ", " + fringe.size() + ", " + seen.size()); } Pair cur = fringe.poll(); seen.remove(cur.coordinates); // System.out.println(ind + " " + ComputeIrrepInteger(cur.coordinates)); if (ind >= 20000) { writer.close(); return; } boolean dupe = false; if (Math.abs(lastLog-cur.log) < 1e-12) { if (dimension_check(cur.coordinates,lastCoord)) { dupe = true; } } if (!dupe) { ind++; writer.println(ComputeIrrepInteger(cur.coordinates)); } lastLog = cur.log; lastCoord = cur.coordinates; for (int i = 0; i < 7; i++) { long newCoord = cur.coordinates + (1L << cums[i]); if (seen.contains(newCoord)) { continue; } double newIrrep = ComputeIrrep(newCoord); fringe.add(new Pair(newCoord, newIrrep)); seen.add(newCoord); } } } catch (FileNotFoundException e) {} catch (UnsupportedEncodingException e) {} } public static boolean dimension_check(long coords1, long coords2) { BigInteger dim = ComputeIrrepInteger(coords1); if (dim.equals(ComputeIrrepInteger(coords2))) { return true; } return false; } public static ArrayList toArray(long coords) { int x0 = toIntExact(coords & ((1L << 7L) - 1L)) + 1; int x1 = toIntExact((coords >> 7L) & ((1L << 9L) - 1L)) + 1; int x2 = toIntExact((coords >> 16L) & ((1L << 7L) - 1L)) + 1; int x3 = toIntExact((coords >> 23L) & ((1L << 11L) - 1L)) + 1; int x4 = toIntExact((coords >> 34L) & ((1L << 6L) - 1L)) + 1; int x5 = toIntExact((coords >> 40L) & ((1L << 8L) - 1L)) + 1; int x6 = toIntExact((coords >> 48L) & ((1L << 9L) - 1L)) + 1; ArrayList al = new ArrayList(); al.add(x0);al.add(x1);al.add(x2);al.add(x3);al.add(x4);al.add(x5);al.add(x6); return al; } public static double ComputeIrrep(long coords) { // note these are shifted up by one int x0 = toIntExact(coords & ((1L << 7L) - 1L)) + 1; int x1 = toIntExact((coords >> 7L) & ((1L << 9L) - 1L)) + 1; int x2 = toIntExact((coords >> 16L) & ((1L << 7L) - 1L)) + 1; int x3 = toIntExact((coords >> 23L) & ((1L << 11L) - 1L)) + 1; int x4 = toIntExact((coords >> 34L) & ((1L << 6L) - 1L)) + 1; int x5 = toIntExact((coords >> 40L) & ((1L << 8L) - 1L)) + 1; int x6 = toIntExact((coords >> 48L) & ((1L << 9L) - 1L)) + 1; double total = 0; total += cachedLogs[x0]; total += cachedLogs[x1]; total += cachedLogs[x2]; total += cachedLogs[x3]; total += cachedLogs[x4]; total += cachedLogs[x5]; total += cachedLogs[x6]; total += cachedLogs[x0 + x1]; total += cachedLogs[x1 + x2]; total += cachedLogs[x2 + x3]; total += cachedLogs[x2 + x6]; total += cachedLogs[x3 + x4]; total += cachedLogs[x4 + x5]; total += cachedLogs[x0 + x1 + x2]; total += cachedLogs[x1 + x2 + x3]; total += cachedLogs[x1 + x2 + x6]; total += cachedLogs[x2 + x3 + x4]; total += cachedLogs[x2 + x3 + x6]; total += cachedLogs[x3 + x4 + x5]; total += cachedLogs[x0 + x1 + x2 + x3]; total += cachedLogs[x0 + x1 + x2 + x6]; total += cachedLogs[x1 + x2 + x3 + x4]; total += cachedLogs[x1 + x2 + x3 + x6]; total += cachedLogs[x1 + 2*x2 + x3 + x6]; total += cachedLogs[x2 + x3 + x4 + x5]; total += cachedLogs[x2 + x3 + x4 + x6]; total += cachedLogs[x0 + x1 + x2 + x3 + x4]; total += cachedLogs[x0 + x1 + x2 + x3 + x6]; total += cachedLogs[x0 + x1 + 2*x2 + x3 + x6]; total += cachedLogs[x0 + 2*x1 + 2*x2 + x3 + x6]; total += cachedLogs[x1 + x2 + x3 + x4 + x5]; total += cachedLogs[x1 + x2 + x3 + x4 + x6]; total += cachedLogs[x1 + 2*x2 + x3 + x4 + x6]; total += cachedLogs[x1 + 2*x2 + 2*x3 + x4 + x6]; total += cachedLogs[x2 + x3 + x4 + x5 + x6]; total += cachedLogs[x0 + x1 + x2 + x3 + x4 + x5]; total += cachedLogs[x0 + x1 + x2 + x3 + x4 + x6]; total += cachedLogs[x0 + x1 + 2*x2 + x3 + x4 + x6]; total += cachedLogs[x0 + 2*x1 + 2*x2 + x3 + x4 + x6]; total += cachedLogs[x0 + x1 + 2*x2 + 2*x3 + x4 + x6]; total += cachedLogs[x0 + 2*x1 + 2*x2 + 2*x3 + x4 + x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 2*x3 + x4 + x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 2*x3 + x4 + 2*x6]; total += cachedLogs[x1 + x2 + x3 + x4 + x5 + x6]; total += cachedLogs[x1 + 2*x2 + x3 + x4 + x5 + x6]; total += cachedLogs[x1 + 2*x2 + 2*x3 + x4 + x5 + x6]; total += cachedLogs[x1 + 2*x2 + 2*x3 + 2*x4 + x5 + x6]; total += cachedLogs[x0 + x1 + x2 + x3 + x4 + x5 + x6]; total += cachedLogs[x0 + x1 + 2*x2 + x3 + x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 2*x2 + x3 + x4 + x5 + x6]; total += cachedLogs[x0 + x1 + 2*x2 + 2*x3 + x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 2*x2 + 2*x3 + x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 2*x3 + x4 + x5 + x6]; total += cachedLogs[x0 + x1 + 2*x2 + 2*x3 + 2*x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 2*x2 + 2*x3 + 2*x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 2*x3 + 2*x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 3*x3 + 2*x4 + x5 + x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 2*x3 + x4 + x5 + 2*x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 2*x3 + 2*x4 + x5 + 2*x6]; total += cachedLogs[x0 + 2*x1 + 3*x2 + 3*x3 + 2*x4 + x5 + 2*x6]; total += cachedLogs[x0 + 2*x1 + 4*x2 + 3*x3 + 2*x4 + x5 + 2*x6]; total += cachedLogs[x0 + 3*x1 + 4*x2 + 3*x3 + 2*x4 + x5 + 2*x6]; total += cachedLogs[2*x0 + 3*x1 + 4*x2 + 3*x3 + 2*x4 + x5 + 2*x6]; return total; } public static BigInteger ComputeIrrepInteger(long coords) { // >>> x = [7, 9, 7, 11, 6, 8, 9, 7] // >>> cum = [sum(x[:i]) for i in range(len(x))] // >>> for i in range(8): // ... print 'int x%d = (coords >> %d) & ((1 << %d) - 1);' % (i, cum[i], x[i]) int x0 = toIntExact(coords & ((1L << 7L) - 1L)) + 1; int x1 = toIntExact((coords >> 7L) & ((1L << 9L) - 1L)) + 1; int x2 = toIntExact((coords >> 16L) & ((1L << 7L) - 1L)) + 1; int x3 = toIntExact((coords >> 23L) & ((1L << 11L) - 1L)) + 1; int x4 = toIntExact((coords >> 34L) & ((1L << 6L) - 1L)) + 1; int x5 = toIntExact((coords >> 40L) & ((1L << 8L) - 1L)) + 1; int x6 = toIntExact((coords >> 48L) & ((1L << 9L) - 1L)) + 1; BigInteger total = BigInteger.ONE; total = total.multiply(BigInteger.valueOf(x0)); total = total.multiply(BigInteger.valueOf(x1)); total = total.multiply(BigInteger.valueOf(x2)); total = total.multiply(BigInteger.valueOf(x3)); total = total.multiply(BigInteger.valueOf(x4)); total = total.multiply(BigInteger.valueOf(x5)); total = total.multiply(BigInteger.valueOf(x6)); total = total.multiply(BigInteger.valueOf(x0 + x1)); total = total.multiply(BigInteger.valueOf(x1 + x2)); total = total.multiply(BigInteger.valueOf(x2 + x3)); total = total.multiply(BigInteger.valueOf(x2 + x6)); total = total.multiply(BigInteger.valueOf(x3 + x4)); total = total.multiply(BigInteger.valueOf(x4 + x5)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x3)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x6)); total = total.multiply(BigInteger.valueOf(x2 + x3 + x4)); total = total.multiply(BigInteger.valueOf(x2 + x3 + x6)); total = total.multiply(BigInteger.valueOf(x3 + x4 + x5)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x3)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x6)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x3 + x4)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x3 + x6)); total = total.multiply(BigInteger.valueOf(x1 + 2*x2 + x3 + x6)); total = total.multiply(BigInteger.valueOf(x2 + x3 + x4 + x5)); total = total.multiply(BigInteger.valueOf(x2 + x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x3 + x4)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x3 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + 2*x2 + x3 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 2*x2 + x3 + x6)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x3 + x4 + x5)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x1 + 2*x2 + x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x1 + 2*x2 + 2*x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x2 + x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x3 + x4 + x5)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + 2*x2 + x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 2*x2 + x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + 2*x2 + 2*x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 2*x2 + 2*x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 2*x3 + x4 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 2*x3 + x4 + 2*x6)); total = total.multiply(BigInteger.valueOf(x1 + x2 + x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x1 + 2*x2 + x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x1 + 2*x2 + 2*x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x1 + 2*x2 + 2*x3 + 2*x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + x2 + x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + 2*x2 + x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 2*x2 + x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + 2*x2 + 2*x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 2*x2 + 2*x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 2*x3 + x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + x1 + 2*x2 + 2*x3 + 2*x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 2*x2 + 2*x3 + 2*x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 2*x3 + 2*x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 3*x3 + 2*x4 + x5 + x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 2*x3 + x4 + x5 + 2*x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 2*x3 + 2*x4 + x5 + 2*x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 3*x2 + 3*x3 + 2*x4 + x5 + 2*x6)); total = total.multiply(BigInteger.valueOf(x0 + 2*x1 + 4*x2 + 3*x3 + 2*x4 + x5 + 2*x6)); total = total.multiply(BigInteger.valueOf(x0 + 3*x1 + 4*x2 + 3*x3 + 2*x4 + x5 + 2*x6)); total = total.multiply(BigInteger.valueOf(2*x0 + 3*x1 + 4*x2 + 3*x3 + 2*x4 + x5 + 2*x6)); total = total.divide(bigDenom); return total; } }