Consecutive semiprimes

A semiprime is a number that is the product of exactly two (not necessarily distinct) primes. Examples of semiprimes are 6 = 2 × 3 , 6=2 \times 3, 35 = 5 × 7 , 35=5 \times 7, and 121 = 11 × 11 121=11 \times 11 .

It's easy to find pairs { 21 , 22 } \{21,22\} and triplets { 85 , 86 , 87 } \{85,86,87\} of consecutive semiprimes on this list of semiprimes up to 187.

Is there a run of consecutive semiprimes longer than three numbers?

Yes, there is no limit to the length of such a run Yes, but there is a limit to how long the run can be No, there are no runs longer than three numbers

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

15 solutions

Jeremy Galvagni
Apr 15, 2018

4 is a semiprime, but 3 and 5 are not.

Suppose there was a list of 4 consecutive semiprimes. One of them would be a multiple of 4. Say n*4. But this multiple of 4 cannot be a semiprime for n>1 because it has at least three factors. Therefore the answer is No, there are no strings longer than three.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
noprimes = [j for i in range(2, 8) for j in range(i*2, 10000, i)]
primes = [x for x in range(2, 10000) if x not in noprimes]

def pairs(s):
        result = []
        for p1 in range(len(s)):
                for p2 in range(p1,len(s)):
                        result.append([s[p1],s[p2]])
        return result

def longestrun(my_l):
    set_ = set()
    contigs = {}
    size = 1
    for key, val in enumerate(my_l):
        if key > 0:
            if val == my_l[key - 1] + 1:
                size += 1
                contigs[size] = val
            else:
                set_.update([size])
                size = 1
    set_.update([size])
    return max(set_), contigs
pairings = pairs(primes)
prod = 0
all_prods = []

for pair in pairings:
    prior_prod = prod
    prod = pair[0] * pair[1]
    all_prods.append(prod)        
print longestrun(sorted(all_prods)) 

1
2
3, 
ex.    1: 19981,    2: 19982,   3: 19983

Michael Fitzgerald - 3 years, 1 month ago

Log in to reply

Programming can also be used to solve this . You should put this up as another solution to this problem .

Nashita Rahman - 3 years, 1 month ago

Log in to reply

How can a program prove non-existence of a run of 4 or more? Suppose this run of 4 or more only occurs when the numbers involved are 1000 digits long. This program won't find that run, even not if given a billion times longer to run.

A program like this can be used to find a run that does work, if it occurs early enough. And it can prove that no such run exists below for instance 1,000,000,000 (if the search limits would be extended).

Roland van Vliembergen - 3 years, 1 month ago

Think about this. If the even number were to be 2x n (n equaling a prime number, obviously) the other factor would be odd. But the next even number, the n would equal an even number, making divisible by 4. 4 is not a prime number.

Thai Food - 3 years, 1 month ago

I’m dumb lol

Amitha Murali - 3 years, 1 month ago

Respected Sir and everyone , Please excuse me for posting this comment . Rather than saying that this is a comment this a burning issue in my heart . Please take it seriously .

I have a dream getting 100 or more up votes for an individual solution . I wrote a solution for the question water shadows (which is adjacent to this question) 6 days ago (on 21 April) . When I wrote the solution I thought it is a good one and will definitely accomplish my dream .

I am extremely happy when I saw that the question is in one of the problems of the week . I thought I am nearer to my dream because nobody posted any solution at that time expect me to this question and my solution is a clear and good one . But after these four days I am extremely sad because even more than 11,000 people solved that question only 83 people are discussing solutions . As a result at present I am only left now with 45 up votes . Although my solution deserves more than 100 up votes due silly reasons it is unable to accomplish my dream .

At first when I solved this question (infinite squares) on Monday morning I solved in the manner you did . I thought to post the solution but when I saw you have already posted the same solution (and now you got 299 up votes) . But I didn't worry at that time because I had hope that my solution to water shadows question will definitely cross 100 up votes .

Once see the up votes to the top solutions for the 5 questions of the problems of this week and see how odd it looks :

Infinite squares - Jason Dyer - 349 up votes

Water shadows - Ram Mohith - 57 up votes (see how odd it looks)

Third problem - Zain Majumder - 167 up votes

Fourth problem - Jeremy Galvagni - 129 up votes

Fifth problem - Micheal Mendrin - 250 upvotes

My point is that please try to discuss solutions to every question you solved and try to up vote the solution you admire as much as possible . If you do that many people like me will acheive what they deserve .

Please try to understand my problem .

Ram Mohith - 3 years, 1 month ago

Log in to reply

When a person submits a problem they are immediately offered an opportunity to enter a solution. I do this right away. This makes my solution the first one you see. This makes it most likely to get upvotes.

This particular problem is quite simple. Many people submitted solutions, but they don't differ much. That splits the votes. Note mine is also low.

Jeremy Galvagni - 3 years, 1 month ago

Log in to reply

129 is not low. It depends on your expectations.

If you want your problem to stand out, make them understand, make them intrigued, and they will upvote. Easier said than done, of course.

Steven Jim - 3 years, 1 month ago
Rishabh Bhardwaj
Apr 22, 2018

Simple,

Let suppose those numbers are a a , a + 1 a+1 , a + 2 a+2 , a + 3 a+3 .

Start: Except 4 itself, any number that is divisible by 4 will be of the form 4xm i.e. 2x2xm. It means it has 'at least' 3 primes.

Case 1: Dividing a a by 4 gives remainder 0.

Case 2: Dividing a a by 4 gives remainder 1.

Case 3: Dividing a a by 4 gives remainder 2.

Case 4: Dividing a a by 4 gives remainder 3.

Explained: In case 1: a a is divisible by 4; case 2: a + 3 a+3 is divisible by 4; case 3: a + 2 a+2 is divisible by 4; and case 4: a + 1 a+1 is divisible by 4.

Hence any sequence of 4 consecutive numbers would have a number that is divisible by 4 (two 2's) and at least one other prime. (e.g. 87,88,89,90: 88 is divisible by 2, 2, and 11 and one more 2).

Concluded: Hence we don't have any sequence of 4 or more numbers with all of them being semiprime.

:)

Please let me know if further clarification needed... :)

Rishabh Bhardwaj - 3 years, 1 month ago

As far as i understand consecutive means that one semi prime is followed by the closest next semi prime. There is no rule which states that the next semi prime should be n+1, although the example suggests so. But the example is just conveniently in showing that a next semi prime can be n+1, but there is no clue that is should be n+1. So imo there are infinitely long strings of semi prime numbers which can be ordered in a consecutive manner.

René de Torbal - 3 years, 1 month ago

Log in to reply

Hi! The question asks about consecutive numbers which are all semi-primes. Please don't confuse it with closest semi-primes. If this would be the case, there can be infinite length sequence.

"Think! What's the point in asking such a question?, I mean why would someone ask if it's not consecutive numbers but closest semi-primes. It quite obvious that infinite semi-primes exists, and so length of the string!"

Rishabh Bhardwaj - 3 years, 1 month ago

The question asks about consecutive number which are all semi-primes. Please don't confuse it with closest semi-primes. If this would be the case, there can be infinite length sequence.

Rishabh Bhardwaj - 3 years, 1 month ago
Soumil Baksi
Apr 22, 2018

A string longer than 3 means there are even multiples of two consecutive numbers. As two consecutive numbers cannot be prime, a string longer than 3 doesn't exist

EDIT: One exception to my solution is 2 and 3, which are the only two consecutive primes. But that string would be for something from 4 to 6, and as they are not biprimes, we can safely conclude our result

2 and 3 are consecutive numbers aren't they?

Ssom Lastname - 3 years, 1 month ago

Log in to reply

except that no two consecutive primes

Soumil Baksi - 3 years, 1 month ago

Can you please explain your idea with an example? I guess there is no mention of semi-primes in your solution. TIA.

Rishabh Bhardwaj - 3 years, 1 month ago
Jackie Ealy
Apr 23, 2018

Any list of 4 consecutive numbers will include a number divisible by 4. Any number divisible by 4 is also divisible by 2 so it is not a semi-prime.

Yes - the above is all that is needed.

Thomas Sutcliffe - 3 years, 1 month ago

Perfectly...sweet and small answer

Satyam singh - 3 years, 1 month ago
Josh Taylor
Apr 23, 2018

If there was a run of four semiprimes then two of them would be consecutive evens. Call these 2n and 2(n+1). Either n or n+1 has to be even. So one of the semiprimes would have to be 2 times an even number, which means is contains another factor of 2, which means it is not semiprime.

So, by contradiction, there can be no runs of semiprimes longer than three.

This is my solution also!

Inksa Inkeroinen - 3 years, 1 month ago
  • A list of more than 3 consecutive semiprimes contains at least 2 even numbers.
  • To get an even semiprime, you need to multiply a prime times 2, since you can only get an even number from multiplication if one of the factors is even and 2 is the only even prime.
  • Let the first even semiprime be p r i m e 1 2 = n \boxed{prime_1 * 2 = n} and the next one p r i m e 2 2 = n + 2 \boxed{prime_2 * 2 = n + 2}
  • From this we can see that the distance between those primes needs to be 1. Because all primes except 2 are odd and adding 1 to any odd number results in an even one, we get that p r i m e 2 prime_2 needs to be even and so, cannot be prime. Therefore, no list of more than 3 consecutive semiprimes is possible.
Abhishek Sinha
May 21, 2018

In any four consecutive numbers, there will be two numbers which are even and differ by 2 2 . Since they are semi-primes, they are of the form 2 p 2p and 2 ( p + 1 ) 2(p+1) , where p p and p + 1 p+1 are primes. Clearly, the only choice for p p is p = 2 p=2 . However, none of the possible sequences { 4 , 5 , 6 , 7 } \{4,5,6,7\} or, { 3 , 4 , 5 , 6 } \{3,4,5,6\} constitute a run of semiprimes.

Let's check if we can do four consecutive semiprimes. Any consecutive list of four numbers will contain two evens and two odds. The two evens will be 2 × x 2 \times x and 2 × ( x + 1 ) 2 \times (x+1) , where x x and x + 1 x+1 are primes. We see that two consecutive primes ( x x and x + 1 x+1 ) are needed: the only consecutive primes are 2 2 and 3 3 . Plugging in, we get the lists ( 4 , 5 , 6 , 7 ) (4, 5, 6, 7) and ( 3 , 4 , 5 , 6 ) (3, 4, 5, 6) , but 3 3 , 5 5 , and 7 7 are all primes, not semiprimes. So the answer is N O \boxed {NO}

Your solution makes the assumption that 2 consecutive primes are needed. This may be so, but how do you come to that conclusion? You may view my solution above, which reaches the same answer to the initial question, but I've not been able to understand your basic assumption of the need for consecutive primes to check for a different solution. Thank you in advance, in case you can help me to understand!

Jackie Ealy - 3 years, 1 month ago

Log in to reply

It is not an assumption. Think about it: all primes except 2 are odd, so the only way to reach an even semiprime number is multiplying 2 by any other prime. Since the two evens in a list with four consecutive numbers are two consecutive evens, then they are 2x and 2(x+1). The problem requires x and x+1 to be primes which is only possible if they are 2 and 3.

A Former Brilliant Member - 3 years, 1 month ago

So... did you get it?

A Former Brilliant Member - 3 years, 1 month ago
Peter Macgregor
Apr 23, 2018

Here is a proof by contradiction.

Suppose there is a run of four consecutive semi-primes.

Then it contains two consecutive even numbers. Let's call them 2n and 2(n+1).

Since these numbers are in the run, they are semi primes, which means that n and (n+1) are primes.

The only two consecutive integers which are prime are 2 and 3, so n=2.

So the two even numbers in the run are 4 and 6.

The number 5 which is sandwiched between them is also in the run.

But 5 is not a semiprime!

Can we have a run of four semiprimes, one of which is not a semiprime??

Contradiction!

So we conclude that the original bold supposition is false.

And so there is no run of four semiprimes \boxed{\text{there is no run of four semiprimes}}

If there are four consecutive semiprime numbers, the sequence has to be: Even/odd/even/odd or odd/even/odd/even Beyond number two, there is no other even prime number. And i can not reach an even one as product of two odds. So, due to the fact that there is only one even prime number, there are no runs longer than three numbers.

If I understand your solution, it discusses prime numbers and not semi-primes. I would really appreciate if you explain it clearly. Sharing new ideas is great! :)

Rishabh Bhardwaj - 3 years, 1 month ago
Ong Zi Qian
Apr 27, 2018

For any consecutive numbers with length more than 4, there m u s t must have at least a number is multiple of 4 4 .

If these consecutive semiprimes have 4 in it, noted that 3 3 and 5 5 is a prime, therefore consecutive semiprimes with 4 4 in it has only length of 1.

If these consecutive numbers contains other multiple of 4 4 (let us say that one of them is m m ) , then m = 4 n = 2 2 × n m=4n=2^2 \times n . Since n 1 n \neq 1 , therefore m m is not a semiprime.

Conclusion: there are no run of consecutive semiprimes longer than three numbers.

Heidar Saleh
Apr 27, 2018

For each 3 consecutive semiprimes, the 1st and 3rd number have to be odd and the 2nd number has to be even (with a single 2 factor times a prime). If we observe the 4th number it will always have another 2 factor which will prevent it of being a prime.

Gabriel Vasto
Apr 24, 2018

There's no such run. Let's consider the following sequence: n , n+1 , n+2 , n+3 . In this sequence, we must have two even numbers such that the difference betwenn then is 2. Let's say that n and n+2 are this numbers. So: n=2q n+2=2q' , where q and q' are both primes. This lead us to 2q=2q'-2 , and hence q'=q+1 , which only holds true if q=2 , because any prime greater than two would be odd, hence q+1 would be even and can't be a prime.

Divyansh Singhal
Apr 24, 2018

One of the four must be a multiple of 4 & that multiple won't be a semiprime. So no longer strings than 3

Piero Sarti
Apr 24, 2018

We know that since a multiple of 2 2 occurs every two consecutive integers, therefore either n n or n + 1 n+1 is a multiple of 2 2 .

Since we are talking about consecutive integers if we let n + 1 = 2 × p 1 n + 1 = 2\times p_1 where p 1 p_1 is prime other than two, then the next multiple of two will be n + 3 = 2 × ( p 1 + 1 ) n + 3 = 2\times (p_1 + 1) . But p 1 + 1 p_1 + 1 is even and therefore we can write it as p 1 = 2 × p 2 p_1 = 2\times p_2 which would mean that n + 3 n + 3 is not semiprime. This also means that if we want a set of 3 consecutive semiprimes, our starting value in the chain n n cannot be even.

As a result we can say that the maximum length for consecutive numbers which are semiprime is 3 3 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...