## Largest 3 consecutive semi-primes?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 4
Joined: Tue Feb 07, 2012 6:11 pm UTC

### Largest 3 consecutive semi-primes?

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 "semi-primes")? 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 semi-primes become rarer and rarer the higher you go, and the fact that to get a set of 3 consecutive semi-primes 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 semi-primes, 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.

Coding
Posts: 47
Joined: Thu Sep 15, 2011 6:59 pm UTC

### Re: Largest 3 consecutive semi-primes?

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:

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    endendsemiprimes.sort!# find triplets2.upto(semiprimes.length-1) do |x|    if semiprimes[x-2]+2 == semiprimes[x] && semiprimes[x-1]+1 == semiprimes[x]        triplets.push(semiprimes[x-2], semiprimes[x-1], semiprimes[x])    endendprint 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 semi-primes?

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).
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Largest 3 consecutive semi-primes?

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 semi-primes?

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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Largest 3 consecutive semi-primes?

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.

xkcdfan
Posts: 140
Joined: Wed Jul 30, 2008 5:10 am UTC

### Re: Largest 3 consecutive semi-primes?

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: 5965
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Largest 3 consecutive semi-primes?

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 semi-primes?

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 ...

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Largest 3 consecutive semi-primes?

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.

Posts: 4
Joined: Tue Feb 07, 2012 6:11 pm UTC

### Re: Largest 3 consecutive semi-primes?

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 semi-primes?

I can't see the latter case really throwing off any of the more important questions though, such as how any n-sequence 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.

Posts: 4
Joined: Tue Feb 07, 2012 6:11 pm UTC

### Re: Largest 3 consecutive semi-primes?

Talith wrote:I can't see the latter case really throwing off any of the more important questions though, such as how any n-sequence 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.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Largest 3 consecutive semi-primes?

I have another question, are there any 7 consecutive 3-almost 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.

Cups of Gold
Posts: 8
Joined: Wed Jul 18, 2012 11:27 pm UTC

### Re: Largest 3 consecutive semi-primes?

tomtom2357 wrote:I have another question, are there any 7 consecutive 3-almost 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 six-chains:

2522, 2523, 2524, 2525, 2526, 2527
4921, 4922, 4923, 4924, 4925, 4926

No sevens yet.

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: Largest 3 consecutive semi-primes?

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*q-1 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).

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Largest 3 consecutive semi-primes?

If any 7-chains 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.

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: Largest 3 consecutive semi-primes?

7-chains exist. I threw together a piece of C code and did a quick brute-force search. The lowest sequence found was (211673; 211674; 211675; 211676; 211677; 211678; 211679) - the highest prime factor in that sequence was 52919.

Sequences:

Spoiler:
(211673; 211674; 211675; 211676; 211677; 211678; 211679)
(298433; 298434; 298435; 298436; 298437; 298438; 298439)
(381353; 381354; 381355; 381356; 381357; 381358; 381359)
(460801; 460802; 460803; 460804; 460805; 460806; 460807)
(506521; 506522; 506523; 506524; 506525; 506526; 506527)
(568729; 568730; 568731; 568732; 568733; 568734; 568735)
(690593; 690594; 690595; 690596; 690597; 690598; 690599)
(705953; 705954; 705955; 705956; 705957; 705958; 705959)
(737633; 737634; 737635; 737636; 737637; 737638; 737639)
(741305; 741306; 741307; 741308; 741309; 741310; 741311)
(921529; 921530; 921531; 921532; 921533; 921534; 921535)
(1056529; 1056530; 1056531; 1056532; 1056533; 1056534; 1056535)
(1088521; 1088522; 1088523; 1088524; 1088525; 1088526; 1088527)
(1105553; 1105554; 1105555; 1105556; 1105557; 1105558; 1105559)
(1141985; 1141986; 1141987; 1141988; 1141989; 1141990; 1141991)
(1362313; 1362314; 1362315; 1362316; 1362317; 1362318; 1362319)
(2016721; 2016722; 2016723; 2016724; 2016725; 2016726; 2016727)
(2270633; 2270634; 2270635; 2270636; 2270637; 2270638; 2270639)
(2369809; 2369810; 2369811; 2369812; 2369813; 2369814; 2369815)
(2535721; 2535722; 2535723; 2535724; 2535725; 2535726; 2535727)
(2590985; 2590986; 2590987; 2590988; 2590989; 2590990; 2590991)
(2688833; 2688834; 2688835; 2688836; 2688837; 2688838; 2688839)
(2956681; 2956682; 2956683; 2956684; 2956685; 2956686; 2956687)
(2983025; 2983026; 2983027; 2983028; 2983029; 2983030; 2983031)
(3085201; 3085202; 3085203; 3085204; 3085205; 3085206; 3085207)
(3112193; 3112194; 3112195; 3112196; 3112197; 3112198; 3112199)
(3147553; 3147554; 3147555; 3147556; 3147557; 3147558; 3147559)
(3269161; 3269162; 3269163; 3269164; 3269165; 3269166; 3269167)
(3509465; 3509466; 3509467; 3509468; 3509469; 3509470; 3509471)
(3772321; 3772322; 3772323; 3772324; 3772325; 3772326; 3772327)
(3901681; 3901682; 3901683; 3901684; 3901685; 3901686; 3901687)
(3991793; 3991794; 3991795; 3991796; 3991797; 3991798; 3991799)

Code:

Spoiler:

Code: Select all

`#include <stdio.h>#include <math.h>int CountFactors(int TestMe){  int NumFactors=0, Count, Max;  while (TestMe%2==0)    {      NumFactors+=1;      TestMe/=2;    }  Max=(int)sqrt(TestMe)+1;  for (Count=3;Count<Max;Count+=2)    {      while (TestMe%Count==0)   {     NumFactors+=1;     TestMe/=Count;   }    }  if (TestMe>1)    NumFactors++; //A factor larger than was tested for  return NumFactors;}int SmallFactors(int TestMe){  if (TestMe%2==0)    return 1;  if (TestMe%3==0)    return 1;  if (TestMe%5==0)    return 1;  if (TestMe%7==0)    return 1;  return 0;}int Test(int TestMe){  int Central;  if (SmallFactors(TestMe))    return 0;  Central=TestMe*4;  if (CountFactors(Central+1)!=3)    return 0;  if (CountFactors(Central-1)!=3)    return 0;  if (CountFactors(Central+2)!=3)    return 0;  if (CountFactors(Central-2)!=3)    return 0;  if (CountFactors(Central+3)!=3)    return 0;  if (CountFactors(Central-3)!=3)    return 0;  if (CountFactors(Central)!=3)    return 0;  return 1;}void ShowSequence(int Tested){  int Central = 4*Tested;  printf("(%d; %d; %d; %d; %d; %d; %d)\n", Central-3, Central-2, Central-1, Central, Central+1, Central+2, Central+3);}int main(){  int Count;  for (Count=0;Count<100000;Count++)    {      if (Test(Count*10+1)) ShowSequence(Count*10+1);      if (Test(Count*10+3)) ShowSequence(Count*10+3);      if (Test(Count*10+7)) ShowSequence(Count*10+7);      if (Test(Count*10+9)) ShowSequence(Count*10+9);    }}`

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

### Re: Largest 3 consecutive semi-primes?

So, are you sure those are the lowest 7-chains? Also, can there be two 7-chains 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 2n-1 chains of n-almost primes?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

CCC
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

### Re: Largest 3 consecutive semi-primes?

tomtom2357 wrote:So, are you sure those are the lowest 7-chains?

If smaller 7-chains 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 7-chains 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 2n-1 chains of n-almost primes?

Hmmm. The central number would always have to be a prime number p multiplied by 2n-1. p cannot be 2, or 3 (because 2n-1 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 C-1 is a multiple of 3. At least one number in the list must be a multiple of each number below 2n.