// 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 g2_irreps_big { static int UPPER_BOUND_FACTOR = 5000000; static double[] cachedLogs = new double[UPPER_BOUND_FACTOR]; static int[] cums = {0, 32}; static BigInteger bigDenom = new BigInteger("120"); 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("b104599.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; } if (Math.abs(lastLog-cur.log) > 1e-12) { // System.out.println(ComputeIrrepInteger(cur.coordinates)); // System.out.println(ComputeIrrepInteger(lastCoord)); ind++; writer.println(ComputeIrrepInteger(cur.coordinates)); } lastLog = cur.log; lastCoord = cur.coordinates; // multithread? for (int i = 0; i < 2; 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) { // System.out.println(toArray(coords1)); // System.out.println(toArray(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 << 32L) - 1L)) + 1; int x1 = toIntExact((coords >> 32L) & ((1L << 32L) - 1L)) + 1; ArrayList al = new ArrayList(); al.add(x0);al.add(x1); return al; } public static double ComputeIrrep(long coords) { // note these are shifted up by one int x0 = toIntExact(coords & ((1L << 32L) - 1L)) + 1; int x1 = toIntExact((coords >> 32L) & ((1L << 32L) - 1L)) + 1; double total = 0; total += cachedLogs[x0]; total += cachedLogs[x1]; total += cachedLogs[x0+x1]; total += cachedLogs[x0+2*x1]; total += cachedLogs[x0+3*x1]; total += cachedLogs[2*x0+3*x1]; 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 << 32L) - 1L)) + 1; int x1 = toIntExact((coords >> 32L) & ((1L << 32L) - 1L)) + 1; BigInteger total = BigInteger.ONE; total = total.multiply(BigInteger.valueOf(x0)); total = total.multiply(BigInteger.valueOf(x1)); total = total.multiply(BigInteger.valueOf(x0+x1)); total = total.multiply(BigInteger.valueOf(x0+2*x1)); total = total.multiply(BigInteger.valueOf(x0+3*x1)); total = total.multiply(BigInteger.valueOf(2*x0+3*x1)); total = total.divide(bigDenom); return total; } }