Problems & Puzzles: Puzzles

Puzzle 262.  Semiprimes in arithmetic progression


Hartley  wrote (Prime Curios!, 13298267):

Each of the 30 numbers 13298267 + 1887270 k, k=0..29 is a "semiprime" (a product of two primes). There is no longer Arithmetic Progression of semiprimes whose terms are all less than 10^8


1. Do you devise a systematic approach in order to get larger progressions?

2. Find a larger progression, lets say 50, 100 and 200, semiprimes in A.P.




J. K. Andersen wrote this:

1. Computing all small semi primes is easy compared to finding long arithmetic progressions among them. A progression of at least 25 semi primes must have difference divisible by 5# = 30 to avoid factors 2^2, 3^2 and 5^2. To get a higher density (around 43% semi primes) I used 11# = 2310 in the form c+2310x, where c<2310 has no factor <=11. For each c, a byte array (faster than bit

operations) was set to 0 or 1 at position x to indicate semi primes. A small x interval fitting in the cache memory was tested at a time, without looking for progressions spanning more than one interval. For every pair of semi primes with difference small enough to potentially extend to 30 semi primes within an x interval, array lookup was used to see how many semi primes were in arithmetic progression.

2. The complexity grows exponentially and 50 semi primes seems infeasible. 100 is completely out of the question, although I guess arbitrarily long progressions exist. The best I found in a few hours was 8 more cases with 30 and 2 with 31: 1852175623 + 6054510 k, k=0..30 2522638201 + 445830 k, k=0..30 The search was not exhaustive.


Giovanni Resta wrote (March 19, 08):

I found one progression of length 35: 71243983 + k*39029760 for k=0,...,34,
and some progressions of length 32, like 3900258487+k*103330920 and 25354741 + k*95795700, for k=0,...,31.


Records   |  Conjectures  |  Problems  |  Puzzles