Largest 3 consecutive semiprimes?
Moderators: gmalivuk, Moderators General, Prelates
Largest 3 consecutive semiprimes?
Hello xkcd fans,
A question occurred to me last night for which I have been unable to find the answer, and I thought if there is a board that can help, it is this one. Does anyone know the largest three consecutive integers that are all a product of exactly 2 prime numbers (aka "semiprimes")? The largest I have been able to come up with so far is <141, 142, 143>, but I don't know/remember enough number theory to be able to get anywhere near to proving this is the largest such set possible, nor indeed whether the opposite (i.e. there are an infinite number of such sets) is in fact true. The latter possibility seems unlikely to me given that semiprimes become rarer and rarer the higher you go, and the fact that to get a set of 3 consecutive semiprimes you can only look "in between" multiples of 4. On the other hand, given there are an infinite number of primes there are of course also an infinite number of semiprimes, so perhaps it is in fact true.
So, does anyone else find this problem interesting and can anyone help with a proof of either hypothesis? Thanks in advance.
A question occurred to me last night for which I have been unable to find the answer, and I thought if there is a board that can help, it is this one. Does anyone know the largest three consecutive integers that are all a product of exactly 2 prime numbers (aka "semiprimes")? The largest I have been able to come up with so far is <141, 142, 143>, but I don't know/remember enough number theory to be able to get anywhere near to proving this is the largest such set possible, nor indeed whether the opposite (i.e. there are an infinite number of such sets) is in fact true. The latter possibility seems unlikely to me given that semiprimes become rarer and rarer the higher you go, and the fact that to get a set of 3 consecutive semiprimes you can only look "in between" multiples of 4. On the other hand, given there are an infinite number of primes there are of course also an infinite number of semiprimes, so perhaps it is in fact true.
So, does anyone else find this problem interesting and can anyone help with a proof of either hypothesis? Thanks in advance.
Re: Largest 3 consecutive semiprimes?
Larger ones that work:
201, 202, 203, 213, 214, 215, 217, 218, 219, 301, 302, 303, 393, 394, 395, 445, 446, 447, 633, 634, 635, 697, 698, 699, 841, 842, 843, 921, 922, 923, 1041, 1042, 1043, 1137, 1138, 1139, 1261, 1262, 1263, 1345, 1346, 1347, 1401, 1402, 1403, 1641, 1642, 1643, 1761, 1762, 1763, 1837, 1838, 1839, 1893, 1894, 1895, 1941, 1942, 1943, 1981, 1982, 1983
Here is the Ruby script I made to find them:
Interesting question, though. I will look at it some more.
201, 202, 203, 213, 214, 215, 217, 218, 219, 301, 302, 303, 393, 394, 395, 445, 446, 447, 633, 634, 635, 697, 698, 699, 841, 842, 843, 921, 922, 923, 1041, 1042, 1043, 1137, 1138, 1139, 1261, 1262, 1263, 1345, 1346, 1347, 1401, 1402, 1403, 1641, 1642, 1643, 1761, 1762, 1763, 1837, 1838, 1839, 1893, 1894, 1895, 1941, 1942, 1943, 1981, 1982, 1983
Here is the Ruby script I made to find them:
Code: Select all
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
semiprimes=[]
triplets=[]
0.upto(primes.length  1) do x
index = x
while index<(primes.length  1) && (primes[x]*primes[index] < 2*primes[primes.length  1])
semiprimes.push(primes[x]*primes[index])
index+=1
end
end
semiprimes.sort!
# find triplets
2.upto(semiprimes.length1) do x
if semiprimes[x2]+2 == semiprimes[x] && semiprimes[x1]+1 == semiprimes[x]
triplets.push(semiprimes[x2], semiprimes[x1], semiprimes[x])
end
end
print triplets.join(", ")
Interesting question, though. I will look at it some more.
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: Largest 3 consecutive semiprimes?
It's worth having a look at the OEIS's A056809, which has a list of 10000 triplets of semiprimes, the largest of which is <5991157, 5991158, 5991159>. Finiteness seems unlikely (but unproven).

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Largest 3 consecutive semiprimes?
Dead Cat wrote:So, does anyone else find this problem interesting and can anyone help with a proof of either hypothesis? Thanks in advance.
That is probably about as difficult as the twin prime problem, which has not been solved yet. Another idea that I had was that {213,214,215} and {217,218,219} are 'consecutive' triplets of semiprimes, are there any more consecutive triplets like this?
Edit: I looked through your list, and I found more examples: {213,214,215,217,218,219} is the original, but the next one doesn't occur until {143097,143098,143099,143101,143102,143013}, no wonder I didn't find any until now.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 Proginoskes
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Largest 3 consecutive semiprimes?
tomtom2357 wrote:That is probably about as difficult as the twin prime problem, which has not been solved yet.
A new milestone has been reached, though: Terrence Tao recently proved that every odd number is the sum of at most five primes.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Largest 3 consecutive semiprimes?
Proginoskes wrote:tomtom2357 wrote:That is probably about as difficult as the twin prime problem, which has not been solved yet.
A new milestone has been reached, though: Terrence Tao recently proved that every odd number is the sum of at most five primes.
Umm, isn't that the goldbach conjecture, and not the twin prime conjecture?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Largest 3 consecutive semiprimes?
Proginoskes wrote:tomtom2357 wrote:That is probably about as difficult as the twin prime problem, which has not been solved yet.
A new milestone has been reached, though: Terrence Tao recently proved that every odd number is the sum of at most five primes.
...41 is the sum of 2, 3, 5, 7, 11, and 13 though?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5957
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Largest 3 consecutive semiprimes?
xkcdfan wrote:Proginoskes wrote:tomtom2357 wrote:That is probably about as difficult as the twin prime problem, which has not been solved yet.
A new milestone has been reached, though: Terrence Tao recently proved that every odd number is the sum of at most five primes.
...41 is the sum of 2, 3, 5, 7, 11, and 13 though?
Its also 41 (one prime), 2 + 2 + 37, 5 + 5 + 5 + 3 + 23 etc etc etc.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Proginoskes
 Posts: 313
 Joined: Mon Nov 14, 2011 7:07 am UTC
 Location: Sitting Down
Re: Largest 3 consecutive semiprimes?
tomtom2357 wrote:Proginoskes wrote:tomtom2357 wrote:That is probably about as difficult as the twin prime problem, which has not been solved yet.
A new milestone has been reached, though: Terrence Tao recently proved that every odd number is the sum of at most five primes.
Umm, isn't that the goldbach conjecture, and not the twin prime conjecture?
Yeah. (Smacks head.) **** flu ...

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Largest 3 consecutive semiprimes?
Proginoskes wrote:tomtom2357 wrote:Proginoskes wrote:tomtom2357 wrote:That is probably about as difficult as the twin prime problem, which has not been solved yet.
A new milestone has been reached, though: Terrence Tao recently proved that every odd number is the sum of at most five primes.
Umm, isn't that the goldbach conjecture, and not the twin prime conjecture?
Yeah. (Smacks head.) **** flu ...
However, that is an interesting accomplishment!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Largest 3 consecutive semiprimes?
Great responses everyone, thanks! I suspected it would be a difficult problem (to prove the case one way or the other) but my mathematical training was insufficient to see just how difficult it might be. I can see that coming anywhere near a proof is way beyond me so I now don't need to waste any more time on it! Interestingly, the OEIS page linked to by NathanielJ is slightly different from my original formulation, in that I stipulated the product of two distinct primes, whereas they count squares of primes as being valid  but including the latter is probably more interesting mathematically.
 Talith
 Proved the Goldbach Conjecture
 Posts: 848
 Joined: Sat Nov 29, 2008 1:28 am UTC
 Location: Manchester  UK
Re: Largest 3 consecutive semiprimes?
I can't see the latter case really throwing off any of the more important questions though, such as how any nsequence is distributed or if there are infinitely many such sequences (unless some bizarre clustering happens around the squares of primes, which seems unlikely). When it comes to proving any of these results though, it may be easier to not throw out semiprimes which are squares.
Re: Largest 3 consecutive semiprimes?
Talith wrote:I can't see the latter case really throwing off any of the more important questions though, such as how any nsequence is distributed or if there are infinitely many such sequences (unless some bizarre clustering happens around the squares of primes, which seems unlikely). When it comes to proving any of these results though, it may be easier to not throw out semiprimes which are squares.
Agreed  that is what I intended to convey with my previous post, which was obviously not clear.

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Largest 3 consecutive semiprimes?
I have another question, are there any 7 consecutive 3almost primes? The three even numbers, when divided by 2, form a semiprime triplet, so that narrows it down, but I haven't found any.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

 Posts: 8
 Joined: Wed Jul 18, 2012 11:27 pm UTC
Re: Largest 3 consecutive semiprimes?
tomtom2357 wrote:I have another question, are there any 7 consecutive 3almost primes? The three even numbers, when divided by 2, form a semiprime triplet, so that narrows it down, but I haven't found any.
I checked using the primes under 3000 and found only these two sixchains:
2522, 2523, 2524, 2525, 2526, 2527
4921, 4922, 4923, 4924, 4925, 4926
No sevens yet.
Re: Largest 3 consecutive semiprimes?
Okay, so you've got six primes, p, q, r, s, t and u, where p*q+1=r*s and r*s+1=t*u.
The lowest triple is <33, 34, 35>. Since 4 cannot be part of such a triple, no triple may include a multiple of 4. Therefore, p*q1 and t*u+1 must both be multiples of 4.
Therefore, r*s is even. Therefore, either r or s must be 2. Let us assign r=2. (Incidentally, there can therefore only be one possible semiprime triplet per prime number; as soon as a value is assigned to s, there's only one possible set of numbers, Therefore the number of semiprime triplets cannot be greater than the number of primes. Which is infinite, so it doesn't help much...).
Of our three consecutive numbers, one must be a multiple of 3. If the middle number is a multiple of 3, it must be 6 (but <5, 6, 7> is not a sequence of semiprimes). Therefore, either the first or the last number must be a multiple of 3.
So we have two possibilities: either <3*q; 2*s; t*u> or <p*q; 2*s; 3*u> where (p, q, s, t, u) are all prime. There are examples of both sorts in the list.
Now, if I take s, and multiply it by 2/3, then I'll get a fraction, a number equal to a whole number plus either 1/3 or 2/3. If s*2/3 is equal to a whole number (w) plus 1/3 (and therefore s=3n+2 for some integer n), then there may be a sequence of the form <3*w, 2*s, t*u> if w is prime; but there is no other possible sequence. If s*2/3 is equal to a whole number (w) plus 2/3 (and therefore s=3n+1 for some integer n), then there may be a sequence of the form <p*q, 2*s, 3*(w+1)> if (w+1) is prime, but there are no other possible sequences.
So. In the case where s=3n+2 for integer n, w=(2n+4/3)1/3 = 2n+1 and the possible sequence is <3*(2n+1); 2*(3n+2); t*u>. In this case, n must be odd (or (3n+2) is not prime).
In the case where s=3n+1 for integer n, w=(2n+2/3)2/3 = 2n and the potential sequence is <p*q; 2*(3n+1), 3*(2n+1)>. In this case, n must be even (or 3n+1 is not prime).
The lowest triple is <33, 34, 35>. Since 4 cannot be part of such a triple, no triple may include a multiple of 4. Therefore, p*q1 and t*u+1 must both be multiples of 4.
Therefore, r*s is even. Therefore, either r or s must be 2. Let us assign r=2. (Incidentally, there can therefore only be one possible semiprime triplet per prime number; as soon as a value is assigned to s, there's only one possible set of numbers, Therefore the number of semiprime triplets cannot be greater than the number of primes. Which is infinite, so it doesn't help much...).
Of our three consecutive numbers, one must be a multiple of 3. If the middle number is a multiple of 3, it must be 6 (but <5, 6, 7> is not a sequence of semiprimes). Therefore, either the first or the last number must be a multiple of 3.
So we have two possibilities: either <3*q; 2*s; t*u> or <p*q; 2*s; 3*u> where (p, q, s, t, u) are all prime. There are examples of both sorts in the list.
Now, if I take s, and multiply it by 2/3, then I'll get a fraction, a number equal to a whole number plus either 1/3 or 2/3. If s*2/3 is equal to a whole number (w) plus 1/3 (and therefore s=3n+2 for some integer n), then there may be a sequence of the form <3*w, 2*s, t*u> if w is prime; but there is no other possible sequence. If s*2/3 is equal to a whole number (w) plus 2/3 (and therefore s=3n+1 for some integer n), then there may be a sequence of the form <p*q, 2*s, 3*(w+1)> if (w+1) is prime, but there are no other possible sequences.
So. In the case where s=3n+2 for integer n, w=(2n+4/3)1/3 = 2n+1 and the possible sequence is <3*(2n+1); 2*(3n+2); t*u>. In this case, n must be odd (or (3n+2) is not prime).
In the case where s=3n+1 for integer n, w=(2n+2/3)2/3 = 2n and the potential sequence is <p*q; 2*(3n+1), 3*(2n+1)>. In this case, n must be even (or 3n+1 is not prime).

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Largest 3 consecutive semiprimes?
If any 7chains exist, then they are of two different types, because the first number can be 1 or 2(mod3). We should solve each case separately.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Largest 3 consecutive semiprimes?
7chains exist. I threw together a piece of C code and did a quick bruteforce search. The lowest sequence found was (211673; 211674; 211675; 211676; 211677; 211678; 211679)  the highest prime factor in that sequence was 52919.
Sequences:
Code:
Sequences:
Spoiler:
Code:
Spoiler:

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Largest 3 consecutive semiprimes?
So, are you sure those are the lowest 7chains? Also, can there be two 7chains that are next to each other (by this I mean the two chains are only separated by one multiple of 8)? Does any of this generalize to 2^{n}1 chains of nalmost primes?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Largest 3 consecutive semiprimes?
tomtom2357 wrote:So, are you sure those are the lowest 7chains?
If smaller 7chains exist, then there is a bug in my program. It's not impossible.
To put that lowest sequence in terms of prime factors:
(7*11*2749; 2*3*35279; 5*5*8467; 2*2*52919; 3*37*1907; 2*109*971; 13*19*857)
tomtom2357 wrote:Also, can there be two 7chains that are next to each other (by this I mean the two chains are only separated by one multiple of 8)?
I don't see why not. The central number in each chain is always four times a prime, so it would have to be centered around a pair of twin primes. My program didn't find any such pairs, but I may simply not have searched high enough
tomtom2357 wrote:Does any of this generalize to 2^{n}1 chains of nalmost primes?
Hmmm. The central number would always have to be a prime number p multiplied by 2^{n1}. p cannot be 2, or 3 (because 2^{n1} multiplied by such a low prime, plus one, must result in a number with fewer prime factors). For given n, in fact, there should be a lower bound for p which increases with increasing n.
For n=2, the lowest sequence is (33, 34, 35); p=17.
For n=3, the lowest sequence I found had p=52919.
This suggests that p may grow very quickly with increasing n.
Since the central number, C, cannot be a multiple of 3, there are therefore two cases; either C+1 is a multiple of 3, or C1 is a multiple of 3. At least one number in the list must be a multiple of each number below 2^{n}.
Who is online
Users browsing this forum: Bing [Bot], Google Feedfetcher and 0 guests