Puzzle – Semiprimes
2007 February 7
A semiprime is a number with exactly two prime factors. 6 is the smallest semiprime (3*2). There can be no largest. (The largest would be the product of the two largest primes, but because we can always find larger primes…)
- What is the longest possible string of consecutive semiprimes? Why?
- Is there a greatest string of semiprimes of that length?
- What is the highest string of semiprimes you can find?
This is a great question. The longest possible string of consecutive semiprimes is 3: a string of 4 semiprimes would require 2 even members, 2k and 2k + 2. These each have a factor of 2, so their other factors (k and k + 1) must also be prime. The only consecutive primes are 2 and 3, but 4 is not a semiprime (and 5 is not, so 4 and 6 couldn’t be in a string of consecutive semiprimes anyhow). A string of 3 semiprimes is conceivable: one of them must be divisble by 3 and the center one must be divisible by 2. The smallest such example is 33-34-35. Then we have 85-86-87 and 93-94-95. The largest I found included the number corresponding to the year of my birth. (I admit, I cheated and used Mathematica to generate these more quickly.)
I don’t have an answer for number 2: they must get rarer and rarer (since we need a prime to multiply 2 by, and primes get rarer and rarer as you get larger), but I suspect it would be very difficult to prove either that there is a largest or that there are infinitely many such triples.
Another way to look at (1) is that every 4th number is divisble by 4=2*2, thus cannot be a semiprime. Thus, the length of the maximum string is upper bounded by 3. Since a string of this length exists, that is the maximum length.
In each of these strings, one number has to be a multiple of 2, and one other has to be a multiple of 3. The third number will be a multiple of 2 other primes. So, to search this, I made a list of primes, mutliplied by 2 and 3, sorted the results. I picked consecutive numbers in the sorted list and looked one below and one above to see if it was a semiprime. Was able to get a string starting with something close to close to 2 million by looking at all primes less than 1 million. The trend seemed to hold; I found something starting close to 200,000 when looking at all primes less than 100,000. Thus, I suspect that there are infinitely many triples.
Clueless
i agree with jbl – great question!
Of course, following your own ‘what if’ and modify and generalize approach, we have to ask about ‘tri-primes’, like 30, that are the product of 3 distinct primes! Using the same ‘in any string of 4 numbers, one must be divisible by 4′ logic, we know there cannot be more than a string of 3 tri-primes, but even finding a string of 2 might be fairly challenging without software. Happy searching!
These questions demonstrate once again why number theory or ‘Higher Arithmeric’ as it was once called, is still one of the most stimulating parts of mathematics and in fact was the ‘prime’ reason I decided to become a mathematician…
Now you’ve compelled me to include one of these on my blog today, a variation on a famous sequence of primes that seems to defy randomness.
Semiprime:
Does anyone knows of an upper-bound on the Nth semiprime? that is a function upperbound(N) such that:
(Nth semiprime) <= upperbound(N)
Where can I find a distribution of semiprimes for each 1,000
numbers up to one million?
(*&*&(*&*(&)(*&)(*&EEEEEEEEEnnDD$#^$#^%$#^$#^%$
4=2*2 is considered to be a semiprime, although it is not a squarefree semiprime.
First-100 2-primes:
{4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 106 111 115 118 119 121 122 123 129 133 134 141 142 143 145 146 155 158 159 161 166 169 177 178 183 185 187 194 201 202 203 205 206 209 213 214 215 217 218 219 221 226 235 237 247 249 253 254 259 262 265 267 274 278 287 289 291 295 298 299 301 302 303 305 309 314}_100
First-100 squarefree 2-primes:
{6 10 14 15 21 22 26 33 34 35 38 39 46 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 106 111 115 118 119 122 123 129 133 134 141 142 143 145 146 155 158 159 161 166 177 178 183 185 187 194 201 202 203 205 206 209 213 214 215 217 218 219 221 226 235 237 247 249 253 254 259 262 265 267 274 278 287 291 295 298 299 301 302 303 305 309 314 319 321 323 326 327 329 334}_100
Thank you! “Square-free semi-primes”….