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.
distance d = 1,887,270
= 2 × 3 × 5 × 7 × 11 × 19 × 43
p = 13, p^2 - 1 = 168
1st term: 13,298,267
1) 13298267 = 17 × 782251
2) 15185537 = 1109 × 13693
3) 17072807 = 199 × 85793
4) 18960077 = 4157 × 4561
5) 20847347 = 467 × 44641
6) 22734617 = 211 × 107747
7) 24621887 = 2267 × 10861
8) 26509157 = 811 × 32687
9) 28396427 = 37 × 767471
10) 30283697 = 59 × 513283
11) 32170967 = 4651 × 6917
12) 34058237 = 263 × 129499
13) 35945507 = 13 × 2765039
14) 37832777 = 3727 × 10151
15) 39720047 = 2081 × 19087
16) 41607317 = 4783 × 8699
17) 43494587 = 23 × 1891069
18) 45381857 = 17 × 2669521
19) 47269127 = 4013 × 11779
20) 49156397 = 101 × 486697
21) 51043667 = 449 × 113683
22) 52930937 = 479 × 110503
23) 54818207 = 29 × 1890283
24) 56705477 = 7177 × 7901
25) 58592747 = 2141 × 27367
26) 60480017 = 13 × 4652309
27) 62367287 = 127 × 491081
28) 64254557 = 139 × 462263
29) 66141827 = 53 × 1247959
30) 68029097 = 31 × 2194487
I searched for an arithmetic sequence of length L=30 of semiprimes,
all less than 10^8 using as my starting-point the constraints
on the distance between the semiprimes, d. d cannot be odd, since
for an odd d, a list L of no more than 3 semiprimes is possible.
Since d is thus even, and the maximum length of such a list is
given by p^2-1, where p is the smallest prime not a factor of d,
d must include the prime factors of 2,3, and 5, and so be a multiple
of 30.
I generated a list of the first 3 million primes, all < 10^8 / 2.
I also prepared a logical array of length 10^8, and set it
to all false. I think using "logical" variables allowed the program to
run fast enough to make the solution possible.
By multiplying the prime list by itself, I simply set all array values
indexed by semiprimes to true. There were about 17 million trues,
or about 17% of the array. I then ran combs over this array of all
possible d and all their possible d-1 phases where d is any
multiple of 30, from 30 to 3333330 ( ~ 10^8 / 30) and looked for
any sequence of 30 trues in a row. It took about 18 hours of computer
time to run. Logicals were crucial for speed because the machine was
working using basic "and" circuits on the truth bits. E.g., I did not
hear the familiar roar of the computer's fan working on a hard problem,
to keep the straining FPU cool - the FPU was idle!
1.3 10^13 truth values were examined. The code is here and here
In retrospect, I could have just worried about prime factors greater than or equal to 7. That would have populated the "truth" array at a 13% rather than 17% level, but would not have sped up the checking). However, I should have limited the "phases" of the combs
to odd numbers only, which would have cut the search time in half.
Since the factor 2 is not present in the SPs of the solution, all relevant SPs are odd and so the sequence starts on an odd number.
Edited on November 27, 2022, 11:40 am
solution
