Skip to content

Puzzle – Semiprimes

February 7, 2007 am28 8:16 am

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…)

  1. What is the longest possible string of consecutive semiprimes? Why?
  2. Is there a greatest string of semiprimes of that length?
  3. What is the highest string of semiprimes you can find?
9 Comments leave one →
  1. JBL permalink
    February 7, 2007 pm28 9:21 pm 9:21 pm

    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.

  2. Clueless permalink
    February 8, 2007 am28 5:32 am 5:32 am

    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

  3. February 12, 2007 pm28 2:00 pm 2:00 pm

    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.

  4. Pierre Charland permalink
    February 4, 2008 am29 3:48 am 3:48 am

    Semiprime:
    Does anyone knows of an upper-bound on the Nth semiprime? that is a function upperbound(N) such that:
    (Nth semiprime) <= upperbound(N)

  5. JM Bergot permalink
    February 27, 2008 am29 1:19 am 1:19 am

    Where can I find a distribution of semiprimes for each 1,000
    numbers up to one million?

    (*&*&(*&*(&)(*&)(*&EEEEEEEEEnnDD$#^$#^%$#^$#^%$

  6. Pierre Charland permalink
    March 17, 2008 am31 12:37 am 12:37 am

    4=2*2 is considered to be a semiprime, although it is not a squarefree semiprime.

  7. Pierre Charland permalink
    March 17, 2008 am31 12:41 am 12:41 am

    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

  8. March 17, 2008 am31 8:16 am 8:16 am

    Thank you! “Square-free semi-primes”….

  9. Thomas permalink
    January 25, 2011 am31 4:49 am 4:49 am

    I was looking at strings of semiprimes and I noticed something interesting, there are only 2 strings of 3 semiprimes that are right next to each other (separated only by the multiple of 4), 213, 214, 215, 217, 218, 219.

Leave a Reply to Dave Marain Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: