Largest 3 consecutive semi-primes?

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Largest 3 consecutive semi-primes?

Postby Dead Cat » Wed Feb 08, 2012 10:18 pm UTC

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.
Dead Cat
 
Posts: 4
Joined: Tue Feb 07, 2012 6:11 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby Coding » Thu Feb 09, 2012 8:19 pm UTC

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.
User avatar
Coding
 
Posts: 47
Joined: Thu Sep 15, 2011 6:59 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby NathanielJ » Thu Feb 09, 2012 9:23 pm UTC

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
User avatar
NathanielJ
 
Posts: 880
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby tomtom2357 » Fri Feb 10, 2012 2:16 pm UTC

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.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Largest 3 consecutive semi-primes?

Postby Proginoskes » Sat Feb 11, 2012 8:20 am UTC

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.
User avatar
Proginoskes
 
Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Largest 3 consecutive semi-primes?

Postby tomtom2357 » Sat Feb 11, 2012 8:30 am UTC

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.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Largest 3 consecutive semi-primes?

Postby xkcdfan » Sun Feb 12, 2012 2:34 am UTC

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?
User avatar
xkcdfan
 
Posts: 121
Joined: Wed Jul 30, 2008 5:10 am UTC

Re: Largest 3 consecutive semi-primes?

Postby jestingrabbit » Sun Feb 12, 2012 2:54 am UTC

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.
User avatar
jestingrabbit
 
Posts: 5470
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Largest 3 consecutive semi-primes?

Postby Proginoskes » Sun Feb 12, 2012 7:19 am UTC

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 ...
User avatar
Proginoskes
 
Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Largest 3 consecutive semi-primes?

Postby tomtom2357 » Sun Feb 12, 2012 7:24 am UTC

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! :D
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Largest 3 consecutive semi-primes?

Postby Dead Cat » Wed Feb 15, 2012 12:49 pm UTC

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.
Dead Cat
 
Posts: 4
Joined: Tue Feb 07, 2012 6:11 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby Talith » Wed Feb 15, 2012 1:58 pm UTC

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.
User avatar
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?

Postby Dead Cat » Wed Feb 15, 2012 5:31 pm UTC

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.
Dead Cat
 
Posts: 4
Joined: Tue Feb 07, 2012 6:11 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby tomtom2357 » Sat Jul 21, 2012 5:54 am UTC

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.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Largest 3 consecutive semi-primes?

Postby Cups of Gold » Sun Jul 22, 2012 2:02 am UTC

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.
Cups of Gold
 
Posts: 8
Joined: Wed Jul 18, 2012 11:27 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby CCC » Sun Jul 22, 2012 10:29 am UTC

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).
CCC
 
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby tomtom2357 » Mon Jul 23, 2012 5:27 am UTC

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.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Largest 3 consecutive semi-primes?

Postby CCC » Mon Jul 23, 2012 9:06 am UTC

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);
    }
}
CCC
 
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC

Re: Largest 3 consecutive semi-primes?

Postby tomtom2357 » Mon Jul 23, 2012 12:18 pm UTC

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.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Largest 3 consecutive semi-primes?

Postby CCC » Mon Jul 23, 2012 1:12 pm UTC

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.
CCC
 
Posts: 46
Joined: Thu Jun 14, 2012 12:29 pm UTC


Return to Mathematics

Who is online

Users browsing this forum: No registered users and 7 guests