# PrimeGridSearch.java

a guest
May 5th, 2019
288
0
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) {
31. }
32. }
33. factorLists.put(i, factorList);
35. for (int j = 0; j < primes.length; j++) {
36. if (i % primes[j] == 0) {
37. mask += 1 << j;
38. }
39. }
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);
81. int factorCount = 0;
82. while (mask > 0) {
83. factorCount++;
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;
153. for (int value : values) {
154. excess *= 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. }