SHARE
TWEET

PrimeGridSearch.java

a guest May 5th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.stream.Collectors;
  6.  
  7. public class PrimeGridSearch {
  8.     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};
  9.     // the actual gap between the product of the 25 primes and the largest number possible is close to 4332.
  10.     // we use 4350 to be absolutely certain to not miss anything due to rounding errors.
  11.     // to extend the search space to look for grids with 24 primes, use 4350 * 97. similarly, use 4350 * 97 * 89 for 23 primes, etc.
  12.     static final int THRESHOLD = 4350;
  13.     static final Map<Integer, List<Integer>> factorLists = new HashMap<>();
  14.     // an array of bit masks for values based on prime factorisation, for efficiency improvements in calculating common divisors and full grid factor counts.
  15.     static int[] masks = new int[10000];
  16.     // a map for holding lists of valid values by grid configuration. e.g. the key "1_1" corresponds to {1010, 1011, , ..., 1110, ..., 1919}
  17.     static final Map<String, List<Integer>> patternLists = new HashMap<>();
  18.     // represents an unknown digit for pattern matching
  19.     static final int BLANK = -1;
  20.     // holds the gap for a given combination of first row and first column after it has been calculated once
  21.     static double[] gaps = new double[10009000];
  22.  
  23.     public static void main(String[] a) {
  24.         long start = System.currentTimeMillis();
  25.         int maxCount = 0;
  26.         for (int i = 1; i < 10000; i++) {
  27.             List<Integer> factorList = new ArrayList<>();
  28.             for (int prime : primes) {
  29.                 if (i % prime == 0) {
  30.                     factorList.add(prime);
  31.                 }
  32.             }
  33.             factorLists.put(i, factorList);
  34.             int mask = 0;
  35.             for (int j = 0; j < primes.length; j++) {
  36.                 if (i % primes[j] == 0) {
  37.                     mask += 1 << j;
  38.                 }
  39.             }
  40.             masks[i] = mask;
  41.         }
  42.         for (int i = 0; i < 1331; i++) {
  43.             int digit0 = i / 121;
  44.             int digit1 = (i % 121) / 11;
  45.             int digit2 = i % 11;
  46.             String pattern = (digit0 == 10 ? "_" : "" + digit0) + (digit1 == 10 ? "_" : "" + digit1) + (digit2 == 10 ? "_" : "" + digit2);
  47.             patternLists.put(pattern, factorLists.keySet().stream().filter(e -> digit0 == 10 || digit0 == getDigit(e, 0))
  48.                     .filter(e -> digit1 == 10 || digit1 == getDigit(e, 1)).filter(e -> digit2 == 10 || digit2 == getDigit(e, 2))
  49.                     .sorted().collect(Collectors.toList()));
  50.         }
  51.         System.out.println("Preprocessing time: " + (System.currentTimeMillis() - start) + " ms");
  52.         for (int r0 : getPatternList(BLANK, BLANK, BLANK)) {
  53.             if (isThresholdExceeded(r0)) {
  54.                 continue;
  55.             }
  56.             for (int c0 : getPatternList(getDigit(r0, 0), BLANK, BLANK)) {
  57.                 if (isThresholdExceeded(r0, c0)) {
  58.                     continue;
  59.                 }
  60.                 for (int r1 : getPatternList(getDigit(c0, 1), BLANK, BLANK)) {
  61.                     if (isThresholdExceeded(r0, c0, r1)) {
  62.                         continue;
  63.                     }
  64.                     for (int c1 : getPatternList(getDigit(r0, 1), getDigit(r1, 1), BLANK)) {
  65.                         int d1 = getDigit(r0, 3) * 1000 + getDigit(r1, 2) * 100 + getDigit(c1, 2) * 10 + getDigit(c0, 3);
  66.                         if (isThresholdExceeded(r0, c0, r1, c1, d1)) {
  67.                             continue;
  68.                         }
  69.                         for (int r2 : getPatternList(getDigit(c0, 2), getDigit(c1, 2), BLANK)) {
  70.                             if (isThresholdExceeded(r0, c0, r1, c1, d1, r2)) {
  71.                                 continue;
  72.                             }
  73.                             for (int c2 : getPatternList(getDigit(r0, 2), getDigit(r1, 2), getDigit(r2, 2))) {
  74.                                 if (isThresholdExceeded(r0, c0, r1, c1, d1, r2, c2)) {
  75.                                     continue;
  76.                                 }
  77.                                 for (int r3 : getPatternList(getDigit(c0, 3), getDigit(c1, 3), getDigit(c2, 3))) {
  78.                                     int c3 = getDigit(r0, 3) * 1000 + getDigit(r1, 3) * 100 + getDigit(r2, 3) * 10 + getDigit(r3, 3);
  79.                                     int d0 = getDigit(r0, 0) * 1000 + getDigit(r1, 1) * 100 + getDigit(r2, 2) * 10 + getDigit(r3, 3);
  80.                                     int mask = masks[r0] | masks[r1] | masks[r2] | masks[r3] | masks[d0] | masks[d1] | masks[c0] | masks[c1] | masks[c2] | masks[c3];
  81.                                     int factorCount = 0;
  82.                                     while (mask > 0) {
  83.                                         factorCount++;
  84.                                         mask = mask & (mask - 1);
  85.                                     }
  86.                                     if (factorCount >= maxCount) {
  87.                                         maxCount = factorCount;
  88.                                         System.out.println(factorCount + " factors");
  89.                                         System.out.println(r0 + " " + factorLists.get(r0));
  90.                                         System.out.println(r1 + " " + factorLists.get(r1));
  91.                                         System.out.println(r2 + " " + factorLists.get(r2));
  92.                                         System.out.println(r3 + " " + factorLists.get(r3));
  93.                                         System.out.println(d0 + " " + factorLists.get(d0));
  94.                                         System.out.println(d1 + " " + factorLists.get(d1));
  95.                                         System.out.println(c0 + " " + factorLists.get(c0));
  96.                                         System.out.println(c1 + " " + factorLists.get(c1));
  97.                                         System.out.println(c2 + " " + factorLists.get(c2));
  98.                                         System.out.println(c3 + " " + factorLists.get(c3));
  99.                                     }
  100.                                 }
  101.                             }
  102.                         }
  103.                     }
  104.                 }
  105.             }
  106.         }
  107.         System.out.println("Total processing time: " + (System.currentTimeMillis() - start) + " ms");
  108.     }
  109.  
  110.     private static boolean isThresholdExceeded(int... values) {
  111.         double gap = JoinTest.THRESHOLD;
  112.         gap /= getExcess(values);
  113.         if (gap < 1) {
  114.             return true;
  115.         }
  116.         if (values.length == 1) {
  117.             gap *= getDigit(values[0], 0) + 1;
  118.             gap *= getDigit(values[0], 0) + 1;
  119.             gap *= getDigit(values[0], 0) + 1;
  120.             gap *= getDigit(values[0], 1) + 1;
  121.             gap *= getDigit(values[0], 2) + 1;
  122.             gap *= getDigit(values[0], 3) + 1;
  123.             gap *= getDigit(values[0], 3) + 1;
  124.             gap /= 10000000;
  125.             return gap < 1;
  126.         }
  127.         // multiplying by 1000 instead of 10000 indexes each pair uniquely, because we know the first digits are the
  128.         // same. this reduces the size of gaps by roughly an order of magnitude.
  129.         // there are more efficient ways to map this (order doesn't matter for 5 of the digits, so there's redundancy),
  130.         // but I've been unable to devise anything sufficiently computation-light to be worthwhile.
  131.         final int index = values[0] * 1000 + values[1];
  132.         if (gaps[index] == 0) {
  133.             double d = 1E10;
  134.             d /= getDigit(values[0], 0) + 1;
  135.             d /= getDigit(values[0], 0) + 1;
  136.             d /= getDigit(values[0], 0) + 1;
  137.             d /= getDigit(values[0], 1) + 1;
  138.             d /= getDigit(values[0], 2) + 1;
  139.             d /= getDigit(values[0], 3) + 1;
  140.             d /= getDigit(values[0], 3) + 1;
  141.             d /= getDigit(values[1], 1) + 1;
  142.             d /= getDigit(values[1], 2) + 1;
  143.             d /= getDigit(values[1], 3) + 1;
  144.             gaps[index] = d;
  145.         }
  146.         gap /= gaps[index];
  147.         return gap < 1;
  148.     }
  149.  
  150.     private static double getExcess(int[] values) {
  151.         double excess = 1;
  152.         int mask = 0;
  153.         for (int value : values) {
  154.             excess *= value;
  155.             mask |= masks[value];
  156.         }
  157.         for (int i = 0; i < primes.length; i++) {
  158.             if ((mask & (1 << i)) > 0) {
  159.                 excess /= primes[i];
  160.             }
  161.         }
  162.         return excess;
  163.     }
  164.  
  165.     private static int getDigit(int i, int index) {
  166.         switch (index) {
  167.             case 0:
  168.                 return i / 1000;
  169.             case 1:
  170.                 return (i % 1000) / 100;
  171.             case 2:
  172.                 return (i % 100) / 10;
  173.             case 3:
  174.                 return i % 10;
  175.             default:
  176.                 throw new RuntimeException("Unsupported index: " + index);
  177.         }
  178.     }
  179.  
  180.     private static List<Integer> getPatternList(int i, int j, int k) {
  181.         return patternLists.get((i == BLANK ? "_" : "" + i) + (j == BLANK ? "_" : "" + j) + (k == BLANK ? "_" : "" + k));
  182.     }
  183. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top