/** * @author Joseph Likar * last edited 2023-09-06 */ import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.File; import java.io.IOException; import java.math.BigInteger; import java.nio.file.Files; import java.util.*; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.TimeUnit; import static java.math.BigInteger.*; /** * The special cases when (m, r)q and r = 1 or 2 */ enum SpecialQseq { NONE, ONE, TWO } public class Main { /** * This is a dictionary that contains locks to prevent recalculating a result */ public static final HashMap<Integer, Set<Integer>> outstandingRequests = new HashMap<>(); public static final HashMap<Integer, HashMap<Integer, QSequence>> cachedQs = new HashMap<>(); /** * values calculated by either previous runs or other algorithms */ public static final HashMap<Integer, BigInteger> knownAnswers = new HashMap<Integer, BigInteger>() {{ // original OEIS value put(25, valueOf(663)); // highest value calculated by my enumeration algo put(200, new BigInteger("627939054875")); // highest value calculated by js implementation of this algo put(500, new BigInteger("241616090679682707123")); // highest value calculated by this algo put(1000, new BigInteger("1832848313729278216858958831133")); }}; public static int GOAL; public static BigInteger[] results; public static Integer completions = 0; /** * @param args provide maximum n to calculate */ public static void main(String[] args) { ExecutorService reaper = Executors.newWorkStealingPool(12); final long start = System.currentTimeMillis(); if (args.length > 0) GOAL = Integer.parseInt(args[0]); else GOAL = 25; // init lookup dict for (int i = 6; i <= GOAL; i++) { outstandingRequests.put(i, new HashSet<>()); cachedQs.put(i, new HashMap<>()); } final ArrayList<MyThread> tasks = new ArrayList<>(GOAL - 1); results = new BigInteger[GOAL + 1]; for (int i = 0; i <= GOAL; i++) { results[i] = ZERO; } for (int usedNumbers = 2; usedNumbers <= GOAL; usedNumbers++) { MyThread newThred = new MyThread(usedNumbers); tasks.add(newThred); reaper.submit(newThred); } reaper.shutdown(); try { reaper.awaitTermination(Long.MAX_VALUE, TimeUnit.MINUTES); } catch (InterruptedException e) { throw new RuntimeException(e); } System.out.println("I have been awakened"); // sum up all results for (int i = tasks.size() - 1; i >= 0; i--) { if (tasks.get(i).completed) { BigInteger[] taskResults = tasks.remove(i).results; for (int j = 0; j <= GOAL; j++) { results[j] = results[j].add(taskResults[j]); } } } for (int i = 0; i <= GOAL; i++) { System.out.println(i + " " + results[i]); } for (Map.Entry<Integer, BigInteger> entry : knownAnswers.entrySet()) { if (entry.getKey() < results.length && results[entry.getKey()].compareTo(entry.getValue()) != 0) throw new RuntimeException("You suck"); } System.out.println(System.currentTimeMillis() - start); } } class MyThread implements Runnable { public final BigInteger[] results; /** * The number of numbers that need to be used and still result in a partition less than {@link Main#GOAL} */ final int MY_N; public boolean completed = false; // init MyThread(int arg) { MY_N = arg; results = new BigInteger[Main.GOAL + 1]; Arrays.fill(results, ZERO); } /** * Notes on how this works: * <p> * This method generates all the primitive families of partitions. * These families first require having a median that has a majority of entries. * In the event of an odd number of entries, then there must be at least one number above and below the median in the case where the median has (n + 1) / 2 entries */ @Override public void run() { // any partition with fewer than this many entries as the median value will always fail final int baseMedianSize = (int) Math.ceil(MY_N / 2.0); // baseMedianSize case handled later for (int medianSize = baseMedianSize + 1; medianSize < MY_N; medianSize++) { if (Main.GOAL - 1 >= 3 * (MY_N - medianSize)) countForFamily(MY_N, medianSize, 1, MY_N - medianSize); for (int medianValue = 2; medianValue * medianSize + (MY_N - medianSize) <= Main.GOAL; medianValue++) { for (int upperNumbers = 0; upperNumbers + medianSize <= MY_N && upperNumbers * (medianValue + 1) <= Main.GOAL - medianValue * medianSize - (MY_N - (medianSize + upperNumbers)) && Main.GOAL - 1 >= 3 * upperNumbers; upperNumbers++) { countForFamily(MY_N, medianSize, medianValue, upperNumbers); } } } for (int medianValue = 1; medianValue * MY_N <= Main.GOAL; medianValue++) { results[medianValue * MY_N] = results[medianValue * MY_N].add(ONE); } // baseMedianSize case handled here if (MY_N % 2 == 1) { for (int medianValue = 2; medianValue * baseMedianSize + (MY_N - baseMedianSize) <= Main.GOAL; medianValue++) { for (int upperNumbers = 1; upperNumbers + baseMedianSize < MY_N; upperNumbers++) { countForFamily(MY_N, baseMedianSize, medianValue, upperNumbers); } } } completed = true; synchronized (Main.completions) { Main.completions++; System.out.println(Main.completions + " \r"); } } /** * @param n Number of numbers to use * @param medianSize Number of numbers in the median * @param medianValue Value of the median * @param upperNumbers Number of numbers above the median */ public void countForFamily(final int n, final int medianSize, final int medianValue, final int upperNumbers) { final int realMedianValue = medianSize * medianValue; final int bottomNumbers = n - (upperNumbers + medianSize); if (upperNumbers * (medianValue + 1) > Main.GOAL - realMedianValue - bottomNumbers) return; final int baseTopValue = upperNumbers * (medianValue + 1); final QSequence bottomQ = QSequence.getSequence(bottomNumbers + (medianValue - 1) - 1, bottomNumbers); final QSequence topQ = QSequence.getSequence(Main.GOAL - 1 - 2 * upperNumbers, upperNumbers); // convolve and add all valid Q coeff pairs for (int baseOffset = 0; baseOffset < bottomQ.sequenceLength && baseOffset <= bottomNumbers * (medianValue - 2) && baseTopValue + realMedianValue + bottomNumbers + baseOffset <= Main.GOAL; baseOffset++) { final BigInteger bottomVal = bottomQ.get(baseOffset); for (int topOffset = 0; topOffset < topQ.sequenceLength && baseTopValue + realMedianValue + bottomNumbers + baseOffset + topOffset <= Main.GOAL; topOffset++) { results[baseTopValue + realMedianValue + bottomNumbers + baseOffset + topOffset] = results[baseTopValue + realMedianValue + bottomNumbers + baseOffset + topOffset].add(bottomVal.multiply(topQ.get(topOffset))); } } } } class QSequence { private static final String Q_LOOKUP_DIR = "qbookup"; public final int sequenceLength; public final SpecialQseq especial; private final BigInteger[] partialArray; private QSequence(BigInteger[] partialArray, int sequenceLength) { this(partialArray, sequenceLength, SpecialQseq.NONE); } private QSequence(BigInteger[] partialArray, int sequenceLength, SpecialQseq speciality) { this.partialArray = partialArray; this.sequenceLength = sequenceLength; this.especial = speciality; } public static QSequence generateFromFull(BigInteger[] fullArray) { return new QSequence(Arrays.copyOf(fullArray, fullArray.length % 2 == 0 ? fullArray.length / 2 : fullArray.length / 2 + 1), fullArray.length); } public static QSequence getSequence(final int m, int r) { synchronized (Main.cachedQs) { if (Main.cachedQs.containsKey(m) && Main.cachedQs.get(m).containsKey(r)) return Main.cachedQs.get(m).get(r); } if (m < 0) return new QSequence(null, 1, SpecialQseq.ONE); if (m == r || r == 0) return new QSequence(null, 1, SpecialQseq.ONE); r = Math.min(r, m - r); if (r == 1) { return new QSequence(null, m, SpecialQseq.ONE); } else if (r == 2) { return new QSequence(null, 2 * m - 3, SpecialQseq.TWO); } // check if the recursive algorithm will be inexpensive, if it will be expensive, then just calculate directly if (!(new File(Q_LOOKUP_DIR + File.pathSeparator + (m - 1) + File.pathSeparator + (r - 1)).exists() && new File(Q_LOOKUP_DIR + File.pathSeparator + (m - 1) + File.pathSeparator + (Math.min(r, m - 1 - r))).exists())) return directCalculate(m, r); while (true) { synchronized (Main.outstandingRequests) { try { if (Main.outstandingRequests.get(m).contains(r)) { // System.out.println("Holding for " + m + " " + r); } else { Main.outstandingRequests.get(m).add(r); break; } } catch (Exception e) { System.out.println("interrept"); throw new RuntimeException(e); } } try { Thread.sleep(10); } catch (InterruptedException e) { System.out.println("Insomniac"); throw new RuntimeException(e); } } QSequence out = readFromDisk(m, r); if (out != null) { synchronized (Main.outstandingRequests) { Main.outstandingRequests.get(m).remove(r); } synchronized (Main.cachedQs) { Main.cachedQs.get(m).put(r, out); } return out; } out = getSequence(m - 1, r - 1).addOther(r, getSequence(m - 1, r)).writeToDisk(m, r); synchronized (Main.outstandingRequests) { Main.outstandingRequests.get(m).remove(r); } synchronized (Main.cachedQs) { Main.cachedQs.get(m).put(r, out); } return out; } public static QSequence directCalculate(int m, int r) { r = Math.min(r, m - r); if (m < 0) return new QSequence(null, 1, SpecialQseq.ONE); if (m == r || r == 0) return new QSequence(null, 1, SpecialQseq.ONE); r = Math.min(r, m - r); if (r == 1) { return new QSequence(null, m, SpecialQseq.ONE); } else if (r == 2) { return new QSequence(null, 2 * m - 3, SpecialQseq.TWO); } while (true) { synchronized (Main.outstandingRequests) { try { if (!Main.outstandingRequests.get(m).contains(r)) { Main.outstandingRequests.get(m).add(r); break; } } catch (Exception e) { System.out.println("interrept"); throw new RuntimeException(e); } } try { Thread.sleep(10); } catch (InterruptedException e) { System.out.println("Insomniac"); throw new RuntimeException(e); } } QSequence out = readFromDisk(m, r); if (out != null) { synchronized (Main.outstandingRequests) { Main.outstandingRequests.get(m).remove(r); } synchronized (Main.cachedQs) { Main.cachedQs.get(m).put(r, out); } return out; } BigInteger[] bigTop = new BigInteger[m + 1]; Arrays.fill(bigTop, ZERO); bigTop[0] = ONE; bigTop[m] = ONE.negate(); for (int em = m - 1; em >= m - r + 1; em--) { BigInteger[] bigCopy = bigTop; bigTop = new BigInteger[bigCopy.length + em]; Arrays.fill(bigTop, bigCopy.length, bigTop.length, ZERO); System.arraycopy(bigCopy, 0, bigTop, 0, bigCopy.length); for (int i = 0; i < bigCopy.length; i++) { int windex = bigTop.length - bigCopy.length + i; bigTop[windex] = bigTop[windex].subtract(bigCopy[i]); } } BigInteger[] bigBot = new BigInteger[2]; Arrays.fill(bigBot, ZERO); bigBot[0] = ONE; bigBot[1] = ONE.negate(); for (int em = 2; em <= r; em++) { BigInteger[] bigCopy = bigBot; bigBot = new BigInteger[bigCopy.length + em]; Arrays.fill(bigBot, bigCopy.length, bigBot.length, ZERO); System.arraycopy(bigCopy, 0, bigBot, 0, bigCopy.length); for (int i = 0; i < bigCopy.length; i++) { int windex = bigBot.length - bigCopy.length + i; bigBot[windex] = bigBot[windex].subtract(bigCopy[i]); } } out = QSequence.generateFromFull(QSequence.syntheticDivision(bigTop, bigBot)).writeToDisk(m, r); synchronized (Main.outstandingRequests) { Main.outstandingRequests.get(m).remove(r); } synchronized (Main.cachedQs) { Main.cachedQs.get(m).put(r, out); } return out; } private static BigInteger[] syntheticDivision(BigInteger[] bigTop, BigInteger[] bigBot) { BigInteger[] out = new BigInteger[bigTop.length - bigBot.length + 1]; for (int i = bigTop.length - 1; i >= bigBot.length - 1; i--) { BigInteger newCoeff = bigTop[i].divide(bigBot[bigBot.length - 1]); out[i - bigBot.length + 1] = newCoeff; for (int j = 0; j < bigBot.length; j++) { bigTop[i - j] = bigTop[i - j].subtract(bigBot[bigBot.length - j - 1].multiply(newCoeff)); } } return out; } public static QSequence readFromDisk(final int m, final int r) { final File infile = new File(Q_LOOKUP_DIR + File.pathSeparator + m + File.pathSeparator + r); if (!infile.exists()) { return null; } try { BigInteger[] bigOut = new BigInteger[(int) Math.ceil((r * (m - r) + 1) / 2.0)]; bigOut[0] = ONE; bigOut[1] = ONE; bigOut[2] = valueOf(2); BufferedInputStream bis = new BufferedInputStream(Files.newInputStream(infile.toPath())); for (int i = 3; i < bigOut.length; i++) { int nextSize = bis.read() + 1; byte[] bia = new byte[nextSize]; for (int j = 0; j < nextSize; j++) { bia[j] = (byte) bis.read(); } bigOut[i] = new BigInteger(bia); } bis.close(); return new QSequence(bigOut, r * (m - r) + 1); } catch (IOException e) { System.out.println("failed to read"); throw new RuntimeException(e); } } public QSequence writeToDisk(final int m, final int r) { final File outfile = new File(Q_LOOKUP_DIR + File.pathSeparator + m + File.pathSeparator + r); if (!outfile.getParentFile().exists()) { outfile.getParentFile().mkdirs(); } else if (outfile.exists()) { return this; } try { outfile.createNewFile(); BufferedOutputStream fos = new BufferedOutputStream(Files.newOutputStream(outfile.toPath())); for (int i = 3; i < partialArray.length; i++) { byte[] bao = partialArray[i].toByteArray(); fos.write((byte) ((bao.length - 1) & 0xFF)); fos.write(bao); } fos.flush(); fos.close(); } catch (IOException e) { System.out.println("Smthn went wrong in writing"); throw new RuntimeException(e); } return this; } public QSequence addOther(int offset, QSequence other) { BigInteger[] outArr = new BigInteger[Math.max(offset + other.sequenceLength, sequenceLength)]; for (int i = 0; i < offset; i++) { outArr[i] = get(i); } for (int i = offset; i < sequenceLength && i - offset < other.sequenceLength; i++) { outArr[i] = get(i).add(other.get(i - offset)); } if (offset + other.sequenceLength < sequenceLength) { for (int i = offset + other.sequenceLength; i < sequenceLength; i++) { outArr[i] = get(i); } } else if (offset + other.sequenceLength > sequenceLength) { for (int i = sequenceLength - offset; i < other.sequenceLength; i++) { outArr[i + offset] = other.get(i); } } return generateFromFull(outArr); } public BigInteger get(int index) { if (index < 0 || index >= sequenceLength) { System.out.println("failed to get"); throw new IndexOutOfBoundsException(index + " out of bounds for sequence of length " + sequenceLength); } switch (this.especial) { case NONE: return partialArray[Math.min(index, sequenceLength - index - 1)]; case ONE: return ONE; case TWO: return valueOf(1 + Math.min(index / 2, (sequenceLength - index - 1) / 2)); default: throw new IllegalStateException("This should never happen"); } } }