Largest 3 consecutive semi-primes?

[Dead Cat]

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]

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

semiprimes.sort!
# find triplets
2.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])
    end
end

print triplets.join(", ")

Interesting question, though. I will look at it some more.

[NathanielJ]

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

[tomtom2357]

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.

[Proginoskes]

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]

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?

[xkcdfan]

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]

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.

[Proginoskes]

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]

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!

[Dead Cat]

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]

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.

[Dead Cat]

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]

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.

[Cups of Gold]

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]

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]

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.

[CCC]

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]

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

[CCC]

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)

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

Does any of this generalize to 2ⁿ-1 chains of n-almost primes?

Hmmm. The central number would always have to be a prime number p multiplied by 2^n-1. p cannot be 2, or 3 (because 2^n-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 2ⁿ.