Guest User

PrimeGridSearch.java

a guest
May 5th, 2019
162
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