Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.List;
- import java.util.Map;
- import java.util.stream.Collectors;
- public class PrimeGridSearch {
- static final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
- // the actual gap between the product of the 25 primes and the largest number possible is close to 4332.
- // we use 4350 to be absolutely certain to not miss anything due to rounding errors.
- // to extend the search space to look for grids with 24 primes, use 4350 * 97. similarly, use 4350 * 97 * 89 for 23 primes, etc.
- static final int THRESHOLD = 4350;
- static final Map<Integer, List<Integer>> factorLists = new HashMap<>();
- // an array of bit masks for values based on prime factorisation, for efficiency improvements in calculating common divisors and full grid factor counts.
- static int[] masks = new int[10000];
- // a map for holding lists of valid values by grid configuration. e.g. the key "1_1" corresponds to {1010, 1011, , ..., 1110, ..., 1919}
- static final Map<String, List<Integer>> patternLists = new HashMap<>();
- // represents an unknown digit for pattern matching
- static final int BLANK = -1;
- // holds the gap for a given combination of first row and first column after it has been calculated once
- static double[] gaps = new double[10009000];
- public static void main(String[] a) {
- long start = System.currentTimeMillis();
- int maxCount = 0;
- for (int i = 1; i < 10000; i++) {
- List<Integer> factorList = new ArrayList<>();
- for (int prime : primes) {
- if (i % prime == 0) {
- factorList.add(prime);
- }
- }
- factorLists.put(i, factorList);
- int mask = 0;
- for (int j = 0; j < primes.length; j++) {
- if (i % primes[j] == 0) {
- mask += 1 << j;
- }
- }
- masks[i] = mask;
- }
- for (int i = 0; i < 1331; i++) {
- int digit0 = i / 121;
- int digit1 = (i % 121) / 11;
- int digit2 = i % 11;
- String pattern = (digit0 == 10 ? "_" : "" + digit0) + (digit1 == 10 ? "_" : "" + digit1) + (digit2 == 10 ? "_" : "" + digit2);
- patternLists.put(pattern, factorLists.keySet().stream().filter(e -> digit0 == 10 || digit0 == getDigit(e, 0))
- .filter(e -> digit1 == 10 || digit1 == getDigit(e, 1)).filter(e -> digit2 == 10 || digit2 == getDigit(e, 2))
- .sorted().collect(Collectors.toList()));
- }
- System.out.println("Preprocessing time: " + (System.currentTimeMillis() - start) + " ms");
- for (int r0 : getPatternList(BLANK, BLANK, BLANK)) {
- if (isThresholdExceeded(r0)) {
- continue;
- }
- for (int c0 : getPatternList(getDigit(r0, 0), BLANK, BLANK)) {
- if (isThresholdExceeded(r0, c0)) {
- continue;
- }
- for (int r1 : getPatternList(getDigit(c0, 1), BLANK, BLANK)) {
- if (isThresholdExceeded(r0, c0, r1)) {
- continue;
- }
- for (int c1 : getPatternList(getDigit(r0, 1), getDigit(r1, 1), BLANK)) {
- int d1 = getDigit(r0, 3) * 1000 + getDigit(r1, 2) * 100 + getDigit(c1, 2) * 10 + getDigit(c0, 3);
- if (isThresholdExceeded(r0, c0, r1, c1, d1)) {
- continue;
- }
- for (int r2 : getPatternList(getDigit(c0, 2), getDigit(c1, 2), BLANK)) {
- if (isThresholdExceeded(r0, c0, r1, c1, d1, r2)) {
- continue;
- }
- for (int c2 : getPatternList(getDigit(r0, 2), getDigit(r1, 2), getDigit(r2, 2))) {
- if (isThresholdExceeded(r0, c0, r1, c1, d1, r2, c2)) {
- continue;
- }
- for (int r3 : getPatternList(getDigit(c0, 3), getDigit(c1, 3), getDigit(c2, 3))) {
- int c3 = getDigit(r0, 3) * 1000 + getDigit(r1, 3) * 100 + getDigit(r2, 3) * 10 + getDigit(r3, 3);
- int d0 = getDigit(r0, 0) * 1000 + getDigit(r1, 1) * 100 + getDigit(r2, 2) * 10 + getDigit(r3, 3);
- int mask = masks[r0] | masks[r1] | masks[r2] | masks[r3] | masks[d0] | masks[d1] | masks[c0] | masks[c1] | masks[c2] | masks[c3];
- int factorCount = 0;
- while (mask > 0) {
- factorCount++;
- mask = mask & (mask - 1);
- }
- if (factorCount >= maxCount) {
- maxCount = factorCount;
- System.out.println(factorCount + " factors");
- System.out.println(r0 + " " + factorLists.get(r0));
- System.out.println(r1 + " " + factorLists.get(r1));
- System.out.println(r2 + " " + factorLists.get(r2));
- System.out.println(r3 + " " + factorLists.get(r3));
- System.out.println(d0 + " " + factorLists.get(d0));
- System.out.println(d1 + " " + factorLists.get(d1));
- System.out.println(c0 + " " + factorLists.get(c0));
- System.out.println(c1 + " " + factorLists.get(c1));
- System.out.println(c2 + " " + factorLists.get(c2));
- System.out.println(c3 + " " + factorLists.get(c3));
- }
- }
- }
- }
- }
- }
- }
- }
- System.out.println("Total processing time: " + (System.currentTimeMillis() - start) + " ms");
- }
- private static boolean isThresholdExceeded(int... values) {
- double gap = JoinTest.THRESHOLD;
- gap /= getExcess(values);
- if (gap < 1) {
- return true;
- }
- if (values.length == 1) {
- gap *= getDigit(values[0], 0) + 1;
- gap *= getDigit(values[0], 0) + 1;
- gap *= getDigit(values[0], 0) + 1;
- gap *= getDigit(values[0], 1) + 1;
- gap *= getDigit(values[0], 2) + 1;
- gap *= getDigit(values[0], 3) + 1;
- gap *= getDigit(values[0], 3) + 1;
- gap /= 10000000;
- return gap < 1;
- }
- // multiplying by 1000 instead of 10000 indexes each pair uniquely, because we know the first digits are the
- // same. this reduces the size of gaps by roughly an order of magnitude.
- // there are more efficient ways to map this (order doesn't matter for 5 of the digits, so there's redundancy),
- // but I've been unable to devise anything sufficiently computation-light to be worthwhile.
- final int index = values[0] * 1000 + values[1];
- if (gaps[index] == 0) {
- double d = 1E10;
- d /= getDigit(values[0], 0) + 1;
- d /= getDigit(values[0], 0) + 1;
- d /= getDigit(values[0], 0) + 1;
- d /= getDigit(values[0], 1) + 1;
- d /= getDigit(values[0], 2) + 1;
- d /= getDigit(values[0], 3) + 1;
- d /= getDigit(values[0], 3) + 1;
- d /= getDigit(values[1], 1) + 1;
- d /= getDigit(values[1], 2) + 1;
- d /= getDigit(values[1], 3) + 1;
- gaps[index] = d;
- }
- gap /= gaps[index];
- return gap < 1;
- }
- private static double getExcess(int[] values) {
- double excess = 1;
- int mask = 0;
- for (int value : values) {
- excess *= value;
- mask |= masks[value];
- }
- for (int i = 0; i < primes.length; i++) {
- if ((mask & (1 << i)) > 0) {
- excess /= primes[i];
- }
- }
- return excess;
- }
- private static int getDigit(int i, int index) {
- switch (index) {
- case 0:
- return i / 1000;
- case 1:
- return (i % 1000) / 100;
- case 2:
- return (i % 100) / 10;
- case 3:
- return i % 10;
- default:
- throw new RuntimeException("Unsupported index: " + index);
- }
- }
- private static List<Integer> getPatternList(int i, int j, int k) {
- return patternLists.get((i == BLANK ? "_" : "" + i) + (j == BLANK ? "_" : "" + j) + (k == BLANK ? "_" : "" + k));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
