API tools faq
paste
Advertisement
Guest User

PrimeGridSearch.java

a guest
May 5th, 2019
288
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.08 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!