30 semiprimes, each less than 10
8, form an arithmetic sequence with strictly positive common difference.
Determine all of them.
Note: A semiprime is the product of exactly two primes.
*** For an extra challenge only, find a semi-analytic solution (simple calculator + p&p) to this puzzle.
Although I was able to find the 30-long sequence of semiprimes by running combs
over the array, I still wanted to try, for fun, a different approach using
autocorrelation. I wondered if the answer would show up in the autocorrelation function of the
truth array, f(i).
The truth array (as from before) is an array indexed from 1 to 10^8
whose values are T of F depending on whether the index is a semiprimes (SP).
For this problem I excluded SPs that included 2, 3, or 5, by setting these SPs to F.
The autocorrelation of a function is sometimes called a periodogram
because recurring peaks that are evenly separated in a function
make a strong showing as a peak at the "lag" or tau of the separation. The ACF for f(x) is:
ACF(tau) = f * f = sum{for i=1,3,..., 10^8 -1} [f(i) f(i-tau)] where "*" is the convolution
operator.
I only considered taus that are multiples of 30. Still, the computation time for all these
was 10 hours, so the method is not a big speed-up.
I figured the 30-long streak of SPs separated by tau = 1,887,270 might show up as
a little bump in the ACF. This may have been wishful thinking: SPs populate 12%
of the array randomly, and there is no extra reward for the 30 peaks
making up an unbroken arithmetic sequence. Further, the 30 hits for that separation
(d=1,887,270) is diluted by all the other 1.8 million summations of this separation that
are phased differently. So, I was surprised when the correct period did show up
as a 3.7 sigma bump in the ACF. Of the 111,110 periods it was the
266th highest. (All the ones of 3.7 sigma and above are shown below.)
Does this method help find SP sequences? Well, somewhat. While it identifies
promising periods, the phase information is lost. I had a program look at the short
list of 314 3.7 sigma peaks or greater, for long unbroken sequences of SPs.
This took almost no computer time at all. The table below shows the solution
to this problem at line 266 in bold. The table lists the sigma and longest sequence of
SPs found for each period. 30 was the longest of all. But, the next longest known,
as recorded in S.C. Uselton's thesis (reference), 29 SPs long (d=152,220, start = 3,660,743)
did not make the list, coming in with sigma = 2. Another new entry, aside from length 30
is found, with length 28 and sigma of 4.6. It is noted that the 5-sigma ACF peak that tops
the list had a sequence only 19 hits long. So, I conclude the method has only
marginal utility. The programs are here and here.
1 sig=5.06 hits=19 d= 2312310 start=25679149
2 sig=4.94 hits=22 d= 2732730 start=27199769
3 sig=4.84 hits=21 d= 510510 start=61060093
4 sig=4.82 hits=22 d= 1021020 start=26356361
5 sig=4.82 hits=21 d= 1531530 start= 607381
6 sig=4.81 hits=20 d= 210210 start=48817001
7 sig=4.80 hits=21 d= 420420 start=27722549
8 sig=4.80 hits=25 d= 2042040 start= 9015157
9 sig=4.79 hits=23 d= 2552550 start=16407617
10 sig=4.79 hits=20 d= 1051050 start=13781203
11 sig=4.77 hits=22 d= 840840 start= 6515933
12 sig=4.77 hits=25 d= 630630 start=27839437
13 sig=4.75 hits=20 d= 1471470 start=40917007
14 sig=4.74 hits=21 d= 1261260 start= 9259763
15 sig=4.74 hits=22 d= 570570 start=49074911
16 sig=4.74 hits=22 d= 3063060 start=34529213
17 sig=4.73 hits=20 d= 1681680 start=33556447
18 sig=4.71 hits=25 d= 1891890 start=11624989
19 sig=4.71 hits=21 d= 2102100 start= 1013119
20 sig=4.71 hits=22 d= 1141140 start=37231771
21 sig=4.70 hits=22 d= 2522520 start=37277789
22 sig=4.70 hits=19 d= 1711710 start=52469611
23 sig=4.69 hits=21 d= 2942940 start=32780513
24 sig=4.69 hits=19 d= 3153150 start= 1351381
25 sig=4.66 hits=21 d= 2852850 start=18430253
26 sig=4.66 hits=20 d= 2282280 start= 2609837
27 sig=4.66 hits=18 d= 3023790 start=19785431
28 sig=4.60 hits=28 d= 690690 start= 522287
29 sig=4.55 hits=23 d= 1381380 start=49407983
30 sig=4.51 hits=19 d= 2072070 start= 4683163
31 sig=4.48 hits=21 d= 2762760 start= 7241321
32 sig=4.48 hits=20 d= 274890 start=25580279
33 sig=4.46 hits=24 d= 549780 start=49411553
34 sig=4.46 hits=21 d= 824670 start=62556797
35 sig=4.45 hits=20 d= 1374450 start=57988603
36 sig=4.44 hits=19 d= 870870 start=16823069
37 sig=4.42 hits=23 d= 1099560 start=68283541
38 sig=4.41 hits=21 d= 746130 start=36370387
39 sig=4.39 hits=20 d= 2748900 start= 2577587
40 sig=4.39 hits=21 d= 2474010 start=34566401
41 sig=4.39 hits=23 d= 1649340 start=60552109
42 sig=4.37 hits=24 d= 307230 start=33730219
43 sig=4.37 hits=20 d= 930930 start=77457649
44 sig=4.37 hits=20 d= 2199120 start=58155569
45 sig=4.37 hits=20 d= 1741740 start=44009113
46 sig=4.36 hits=22 d= 1861860 start=54237319
47 sig=4.36 hits=23 d= 2238390 start=13239263
48 sig=4.36 hits=22 d= 1492260 start=40870111
49 sig=4.36 hits=21 d= 1924230 start=14452709
50 sig=4.35 hits=20 d= 3298680 start=22627943
51 sig=4.35 hits=20 d= 2612610 start= 6277729
52 sig=4.34 hits=24 d= 614460 start= 5714281
53 sig=4.32 hits=20 d= 921690 start=20946253
54 sig=4.31 hits=21 d= 2792790 start= 3339911
55 sig=4.31 hits=22 d= 660660 start= 7396637
56 sig=4.31 hits=20 d= 2984520 start= 2103443
57 sig=4.29 hits=19 d= 990990 start=33785627
58 sig=4.29 hits=21 d= 1228920 start=64137679
59 sig=4.29 hits=22 d= 1536150 start=29639039
60 sig=4.29 hits=23 d= 330330 start=47177791
61 sig=4.28 hits=21 d= 1111110 start=62456543
62 sig=4.27 hits=21 d= 1651650 start=26536067
63 sig=4.27 hits=22 d= 2150610 start=46427531
64 sig=4.27 hits=26 d= 2457840 start=23751557
65 sig=4.27 hits=22 d= 1843380 start=43843529
66 sig=4.26 hits=25 d= 1321320 start= 4502087
67 sig=4.25 hits=20 d= 2765070 start= 2036003
68 sig=4.25 hits=22 d= 1231230 start= 4537933
69 sig=4.25 hits=22 d= 1981980 start=10732133
70 sig=4.24 hits=22 d= 1291290 start=68888993
71 sig=4.23 hits=22 d= 2222220 start=13037897
72 sig=4.23 hits=27 d= 2462460 start= 8450777
73 sig=4.22 hits=21 d= 780780 start=68729501
74 sig=4.22 hits=22 d= 390390 start=25066819
75 sig=4.22 hits=22 d= 2642640 start=41693507
76 sig=4.22 hits=22 d= 371910 start= 4624267
77 sig=4.22 hits=23 d= 3072300 start=20320603
78 sig=4.22 hits=22 d= 903210 start=26060123
79 sig=4.21 hits=19 d= 2972970 start=30629297
80 sig=4.20 hits=22 d= 324870 start=16409647
81 sig=4.20 hits=24 d= 1171170 start=13569821
82 sig=4.20 hits=20 d= 1806420 start=43745371
83 sig=4.20 hits=20 d= 2582580 start=21268141
84 sig=4.20 hits=19 d= 3303300 start= 1684183
85 sig=4.19 hits=20 d= 1561560 start=69391687
86 sig=4.19 hits=22 d= 1411410 start=50013767
87 sig=4.19 hits=20 d= 2342340 start=22448417
88 sig=4.19 hits=19 d= 2709630 start=19444027
89 sig=4.19 hits=20 d= 1487640 start=55666157
90 sig=4.18 hits=20 d= 743820 start=58308391
91 sig=4.17 hits=23 d= 1951950 start=22637819
92 sig=4.17 hits=23 d= 1115730 start=37329013
93 sig=4.16 hits=18 d= 1859550 start=58768777
94 sig=4.16 hits=23 d= 1591590 start= 7000369
95 sig=4.14 hits=22 d= 1771770 start=33540323
96 sig=4.14 hits=19 d= 2822820 start=31814087
97 sig=4.14 hits=18 d= 3123120 start=12773743
98 sig=4.14 hits=20 d= 1831830 start=57431027
99 sig=4.14 hits=20 d= 1299480 start=14571653
100 sig=4.13 hits=20 d= 974610 start= 4315979
101 sig=4.13 hits=20 d= 649740 start=33928961
102 sig=4.13 hits=20 d= 2598960 start=29011511
103 sig=4.12 hits=23 d= 881790 start=14445083
104 sig=4.12 hits=21 d= 2231460 start=15375179
105 sig=4.12 hits=20 d= 1624350 start=55287619
106 sig=4.12 hits=20 d= 3183180 start= 2665963
107 sig=4.11 hits=24 d= 1949220 start=31135037
108 sig=4.10 hits=21 d= 2603370 start=29973073
109 sig=4.10 hits=21 d= 2923830 start=41426443
110 sig=4.10 hits=23 d= 2274090 start= 9124847
111 sig=4.09 hits=22 d= 2012010 start=23290199
112 sig=4.09 hits=21 d= 1009470 start=37819933
113 sig=4.08 hits=18 d= 2975280 start=15100417
114 sig=4.08 hits=21 d= 1763580 start= 4874957
115 sig=4.08 hits=20 d= 2372370 start=29109617
116 sig=4.07 hits=19 d= 1138830 start=67625731
117 sig=4.07 hits=18 d= 3248700 start=41827717
118 sig=4.07 hits=23 d= 2018940 start=50453737
119 sig=4.06 hits=20 d= 363090 start=19817039
120 sig=4.06 hits=20 d= 2645370 start=14849221
121 sig=4.06 hits=19 d= 2132130 start=40706213
122 sig=4.06 hits=20 d= 2192190 start=16627307
123 sig=4.05 hits=21 d= 726180 start=11779969
124 sig=4.05 hits=20 d= 3028410 start=32848259
125 sig=4.05 hits=20 d= 468930 start=84915473
126 sig=4.05 hits=21 d= 2492490 start=11183929
127 sig=4.04 hits=19 d= 2672670 start=19131767
128 sig=4.04 hits=21 d= 1815450 start=19682107
129 sig=4.03 hits=19 d= 3033030 start=39526657
130 sig=4.03 hits=22 d= 2912910 start=28624469
131 sig=4.03 hits=22 d= 1089270 start=27225227
132 sig=4.03 hits=21 d= 30030 start=34450747
133 sig=4.02 hits=22 d= 1217370 start= 6263743
134 sig=4.02 hits=22 d= 1452360 start=41306857
135 sig=4.02 hits=19 d= 2434740 start=29352241
136 sig=4.02 hits=20 d= 150150 start=30360217
137 sig=4.01 hits=22 d= 937860 start=67925929
138 sig=4.01 hits=20 d= 540540 start= 178253
139 sig=4.01 hits=24 d= 180180 start=47380393
140 sig=4.01 hits=21 d= 60060 start=59947357
141 sig=4.01 hits=22 d= 2178540 start=24825631
142 sig=4.01 hits=22 d= 120120 start=10877491
143 sig=4.01 hits=20 d= 270270 start=14933851
144 sig=4.00 hits=20 d= 450450 start=64007117
145 sig=4.00 hits=22 d= 480480 start= 1667483
146 sig=4.00 hits=21 d= 1002540 start=19113929
147 sig=4.00 hits=23 d= 900900 start= 9270329
148 sig=4.00 hits=20 d= 240240 start=53484157
149 sig=4.00 hits=22 d= 2277660 start= 7683751
150 sig=4.00 hits=22 d= 1406790 start=10837063
151 sig=3.99 hits=20 d= 431970 start=45470197
152 sig=3.99 hits=22 d= 300300 start=76041611
153 sig=3.99 hits=19 d= 2344650 start=54126181
154 sig=3.99 hits=20 d= 960960 start=43651901
155 sig=3.99 hits=20 d= 1503810 start=47260229
156 sig=3.99 hits=22 d= 360360 start=72082051
157 sig=3.99 hits=20 d= 3213210 start= 2066851
158 sig=3.98 hits=21 d= 1875720 start=34721957
159 sig=3.98 hits=21 d= 600600 start=53211997
160 sig=3.98 hits=23 d= 501270 start=29791631
161 sig=3.98 hits=19 d= 3273270 start=33090193
162 sig=3.98 hits=21 d= 177870 start=43740479
163 sig=3.97 hits=20 d= 1067430 start= 5541569
164 sig=3.97 hits=21 d= 750750 start= 5493757
165 sig=3.97 hits=20 d= 2904720 start= 9902563
166 sig=3.97 hits=21 d= 533610 start=10349767
167 sig=3.97 hits=21 d= 2005080 start=16048807
168 sig=3.96 hits=19 d= 3282510 start=34725443
169 sig=3.96 hits=19 d= 2541630 start=20366813
170 sig=3.96 hits=19 d= 2506350 start= 1507339
171 sig=3.96 hits=21 d= 355740 start= 1294619
172 sig=3.96 hits=21 d= 90090 start=94550611
173 sig=3.96 hits=22 d= 2813580 start=38563909
174 sig=3.96 hits=21 d= 720720 start=25784179
175 sig=3.95 hits=19 d= 1272810 start= 6422869
176 sig=3.95 hits=20 d= 1610070 start=32612861
177 sig=3.95 hits=20 d= 3093090 start=17422661
178 sig=3.95 hits=23 d= 1201200 start=17332361
179 sig=3.95 hits=19 d= 1452990 start=57090967
180 sig=3.95 hits=19 d= 1621620 start=19672313
181 sig=3.94 hits=22 d= 810810 start=59230603
182 sig=3.94 hits=21 d= 711480 start=18760037
183 sig=3.94 hits=19 d= 3267810 start= 7532851
184 sig=3.94 hits=19 d= 863940 start=40854679
185 sig=3.94 hits=19 d= 1295910 start=53289491
186 sig=3.94 hits=22 d= 1081080 start= 761479
187 sig=3.93 hits=19 d= 1360590 start=27262343
188 sig=3.93 hits=21 d= 2252250 start=34144681
189 sig=3.93 hits=27 d= 1501500 start=51851519
190 sig=3.93 hits=21 d= 889350 start=34072541
191 sig=3.93 hits=23 d= 1921920 start= 4514161
192 sig=3.93 hits=19 d= 662970 start=61181167
193 sig=3.93 hits=24 d= 1351350 start= 2661311
194 sig=3.93 hits=23 d= 1441440 start= 1851281
195 sig=3.92 hits=19 d= 1245090 start=17490349
196 sig=3.92 hits=18 d= 3007620 start=30443869
197 sig=3.92 hits=19 d= 2545620 start=13791647
198 sig=3.92 hits=22 d= 1727880 start=17462713
199 sig=3.92 hits=21 d= 598290 start=61906193
200 sig=3.92 hits=18 d= 2432430 start= 5192731
201 sig=3.92 hits=19 d= 2702700 start=22240577
202 sig=3.92 hits=23 d= 2159850 start=52143691
203 sig=3.92 hits=21 d= 1801800 start=26089339
204 sig=3.91 hits=20 d= 1196580 start= 340343
205 sig=3.91 hits=21 d= 2591820 start= 2234273
206 sig=3.91 hits=19 d= 1956570 start= 3103099
207 sig=3.91 hits=20 d= 695310 start=52343407
208 sig=3.91 hits=22 d= 2402400 start=15443357
209 sig=3.91 hits=20 d= 2162160 start=18132337
210 sig=3.91 hits=21 d= 1067220 start=52071611
211 sig=3.91 hits=19 d= 2882880 start= 882983
212 sig=3.91 hits=22 d= 482790 start=66171779
213 sig=3.91 hits=21 d= 1422960 start= 9453067
214 sig=3.91 hits=19 d= 2905980 start=47057459
215 sig=3.91 hits=21 d= 879060 start=22928891
216 sig=3.90 hits=21 d= 439530 start=82473211
217 sig=3.90 hits=20 d= 2134860 start=55520627
218 sig=3.90 hits=19 d= 1794870 start= 8987329
219 sig=3.90 hits=23 d= 1688610 start=43461101
220 sig=3.89 hits=19 d= 1600830 start=10153079
221 sig=3.89 hits=19 d= 1778700 start=26395163
222 sig=3.89 hits=19 d= 3202290 start= 5163337
223 sig=3.89 hits=20 d= 3003000 start= 1530973
224 sig=3.89 hits=20 d= 2721180 start=11413273
225 sig=3.89 hits=20 d= 2134440 start= 2540297
226 sig=3.88 hits=20 d= 1325940 start=16626601
227 sig=3.88 hits=20 d= 1318590 start=68951153
228 sig=3.88 hits=20 d= 2393160 start=52758569
229 sig=3.88 hits=22 d= 1758120 start=56708861
230 sig=3.88 hits=21 d= 2991450 start=26398763
231 sig=3.87 hits=20 d= 2490180 start= 5874707
232 sig=3.87 hits=19 d= 2845920 start=11901833
233 sig=3.87 hits=21 d= 1390620 start=49391807
234 sig=3.86 hits=20 d= 1845690 start=21423443
235 sig=3.86 hits=23 d= 3243240 start= 548047
236 sig=3.86 hits=21 d= 1623930 start= 3196601
237 sig=3.85 hits=22 d= 2197650 start=27667567
238 sig=3.85 hits=21 d= 3220140 start=35435929
239 sig=3.85 hits=19 d= 3201660 start=16006537
240 sig=3.85 hits=22 d= 2637180 start=16194839
241 sig=3.84 hits=18 d= 759990 start=70693537
242 sig=3.84 hits=22 d= 1193010 start=42640543
243 sig=3.83 hits=20 d= 965580 start=70501213
244 sig=3.82 hits=20 d= 2081310 start=14030063
245 sig=3.82 hits=20 d= 2085930 start= 159587
246 sig=3.82 hits=22 d= 954030 start=70997693
247 sig=3.82 hits=20 d= 3247860 start= 6065971
248 sig=3.82 hits=22 d= 2668050 start=35389451
249 sig=3.82 hits=20 d= 3076710 start=28425937
250 sig=3.82 hits=20 d= 1988910 start=30892319
251 sig=3.82 hits=25 d= 1519980 start= 11381
252 sig=3.82 hits=19 d= 857010 start=57709583
253 sig=3.82 hits=21 d= 667590 start=25192597
254 sig=3.82 hits=20 d= 2651880 start=10988063
255 sig=3.81 hits=18 d= 2279970 start= 62863
256 sig=3.81 hits=21 d= 1448370 start= 5235959
257 sig=3.81 hits=18 d= 3314850 start=20418047
258 sig=3.81 hits=20 d= 1931160 start=49071973
259 sig=3.80 hits=19 d= 1540770 start=28087727
260 sig=3.80 hits=20 d= 3039960 start= 812803
261 sig=3.80 hits=22 d= 1345890 start=10206979
262 sig=3.80 hits=22 d= 2316930 start=14486389
263 sig=3.80 hits=20 d= 2781240 start=36057331
264 sig=3.79 hits=21 d= 2896740 start=38253539
265 sig=3.79 hits=21 d= 2413950 start=31444571
266 sig=3.79 hits=30 d= 1887270 start=13298267 *******
267 sig=3.79 hits=25 d= 2386020 start=16072327
268 sig=3.79 hits=20 d= 2395470 start=14380363
269 sig=3.79 hits=25 d= 1799490 start=44046791
270 sig=3.77 hits=23 d= 1714020 start= 5996597
271 sig=3.77 hits=25 d= 554190 start=24632563
272 sig=3.77 hits=19 d= 474810 start=87860077
273 sig=3.77 hits=21 d= 986370 start=19558277
274 sig=3.77 hits=18 d= 1908060 start=38909161
275 sig=3.76 hits=18 d= 2571030 start= 2272999
276 sig=3.76 hits=20 d= 1180410 start=52149917
277 sig=3.76 hits=20 d= 2216760 start=11144963
278 sig=3.75 hits=23 d= 1662570 start=17328091
279 sig=3.75 hits=21 d= 592410 start=17726437
280 sig=3.75 hits=22 d= 3081540 start=33677489
281 sig=3.75 hits=19 d= 2691780 start=50094997
282 sig=3.75 hits=19 d= 2866710 start=38434279
283 sig=3.74 hits=20 d= 2062830 start= 1109321
284 sig=3.74 hits=20 d= 2166780 start= 4044899
285 sig=3.74 hits=23 d= 2862090 start= 7551641
286 sig=3.74 hits=19 d= 1438710 start=57675959
287 sig=3.74 hits=19 d= 1647030 start=36655757
288 sig=3.74 hits=21 d= 2670360 start=22014511
289 sig=3.74 hits=18 d= 2296140 start=22095811
290 sig=3.74 hits=21 d= 2631090 start= 1951711
291 sig=3.74 hits=20 d= 949620 start=29281331
292 sig=3.73 hits=19 d= 2002770 start=40347323
293 sig=3.73 hits=20 d= 1108380 start=22329901
294 sig=3.73 hits=19 d= 1335180 start= 4072237
295 sig=3.73 hits=21 d= 1184820 start=69845707
296 sig=3.73 hits=19 d= 1148070 start= 319637
297 sig=3.73 hits=19 d= 1083390 start= 6924521
298 sig=3.73 hits=21 d= 3102330 start= 7685753
299 sig=3.72 hits=19 d= 584430 start=84212441
300 sig=3.72 hits=21 d= 2770950 start=30271607
301 sig=3.72 hits=19 d= 1972740 start=13205483
302 sig=3.72 hits=22 d= 2959110 start=15984293
303 sig=3.71 hits=22 d= 1168860 start= 1114403
304 sig=3.71 hits=20 d= 78540 start=60053711
305 sig=3.71 hits=19 d= 2788170 start=43514321
306 sig=3.71 hits=19 d= 2360820 start=27499579
307 sig=3.71 hits=22 d= 117810 start= 301307
308 sig=3.71 hits=20 d= 1342110 start=43308059
309 sig=3.71 hits=19 d= 3259410 start= 3754853
310 sig=3.71 hits=19 d= 235620 start=94488679
311 sig=3.71 hits=20 d= 1665510 start= 2743331
312 sig=3.71 hits=21 d= 39270 start=30751381
313 sig=3.70 hits=20 d= 1633170 start=17466347
314 sig=3.70 hits=19 d= 3294060 start=17554601
List sorted by sequence length, L, for the top 20 values
Rank L distance start ACF sigma
1 30 1887270 13298267 3.790 *****
2 28 690690 522287 4.604
3 27 1501500 51851519 3.933
4 27 2462460 8450777 4.229
5 26 2457840 23751557 4.270
6 25 1321320 4502087 4.264
7 25 1891890 11624989 4.715
8 25 2042040 9015157 4.796
9 25 1519980 11381 3.818
10 25 630630 27839437 4.767
11 25 2386020 16072327 3.787
12 25 1799490 44046791 3.785
13 25 554190 24632563 3.770
14 24 549780 49411553 4.462
15 24 1351350 2661311 3.928
16 24 307230 33730219 4.374
17 24 614460 5714281 4.335
18 24 1171170 13569821 4.203
19 24 1949220 31135037 4.107
20 24 180180 47380393 4.011
Edited on November 27, 2022, 2:15 pm
A different approach
