RDKGames
Badges: 20
Rep:
?
#1
Report Thread starter 3 years ago
#1
Consider a set of k primes where each successive prime is d more than the previous prime

This set can be denoted \{ p, p+d,p+2d, ..., p+(k-1)d \}

How can I begin to show that there exist no other sets with d=2, k>2 apart from \{ 3,5,7 \} ??
0
reply
anosmianAcrimony
Badges: 20
Rep:
?
#2
Report 3 years ago
#2
This isn't a rigorous mathematical proof, but more a logical narrowing-down. All primes are odd except for 2. No primes end in the number 5, except for 5, because anything else that ends in 5 is divisible by 5 and hence not prime. Any set of primes where each successive prime was 2 more than the last one would have to have last digits from among these, in order: 1, 3, 5, 7, 9. There is no way of doing that without including 5 as a last digit. Hence the only way to do it is {3, 5, 7}.


Nevermind, that doesn't work. You could still have a run of primes where the last digits went 7, 9, 1 or 9, 1, 3. I may still have generally been on the right track, though; perhaps there is some way of showing that if the last digits went 7, 9, 1 or 9, 1, 3 that one of those would have to be divisible by something?

Actually I think I have just worked it out. If you take any number, it is either a multiple of 3 or you can add either 2 or 4 to make it a multiple of 3. So it's impossible to have three numbers generated by adding 2 and 4 to a given number and not have at least one of them be divisible by 3. Again, I don't know how to write that up as a proper proof.

Why the heck am I studying biochemistry and not maths again? This stuff is so much fun!
6
reply
Pangol
Badges: 15
Rep:
?
#3
Report 3 years ago
#3
You need three consecutive odd numbers, all of which are prime.

As the first one is prime, it is not a multiple of 3. What are the implications of this for the other "primes" in your list? Think about the numbers before and after the first one in your list.
1
reply
DFranklin
Badges: 18
Rep:
?
#4
Report 3 years ago
#4
(Original post by Pangol)
~
Bit of a full solution - want to edit it down to a hint?
0
reply
Pangol
Badges: 15
Rep:
?
#5
Report 3 years ago
#5
(Original post by DFranklin)
Bit of a full solution - want to edit it down to a hint?
Fair enough - significantly trimmed!
1
reply
RDKGames
Badges: 20
Rep:
?
#6
Report Thread starter 3 years ago
#6
(Original post by anosmianAcrimony)
This isn't a rigorous mathematical proof, but more a logical narrowing-down. All primes are odd except for 2. No primes end in the number 5, except for 5, because anything else that ends in 5 is divisible by 5 and hence not prime. Any set of primes where each successive prime was 2 more than the last one would have to have last digits from among these, in order: 1, 3, 5, 7, 9. There is no way of doing that without including 5 as a last digit. Hence the only way to do it is {3, 5, 7}.


Nevermind, that doesn't work. You could still have a run of primes where the last digits went 7, 9, 1 or 9, 1, 3. I may still have generally been on the right track, though; perhaps there is some way of showing that if the last digits went 7, 9, 1 or 9, 1, 3 that one of those would have to be divisible by something?

Actually I think I have just worked it out. If you take any number, it is either a multiple of 3 or you can add either 2 or 4 to make it a multiple of 3. So it's impossible to have three numbers generated by adding 2 and 4 to a given number and not have at least one of them be divisible by 3. Again, I don't know how to write that up as a proper proof.

Why the heck am I studying biochemistry and not maths again? This stuff is so much fun!
(Original post by Pangol)
You need three consecutive odd numbers, all of which are prime.

As the first one is prime, it is not a multiple of 3. What are the implications of this for the other "primes" in your list? Think about the numbers before and after the first one in your list.
Ah thank you, it's much more straightforward than I thought at first.

Is there a concrete way to show that if a prime ends in a 7 or a 9, then either p+2 or p+4 will not be prime?? I can't seem to show this
0
reply
Pangol
Badges: 15
Rep:
?
#7
Report 3 years ago
#7
(Original post by RDKGames)
Is there a concrete way to show that if a prime ends in a 7 or a 9, then either p+2 or p+4 will not be prime?? I can't seem to show this
Doesn't the result we've been talking about tell you that if p is a prime then either p+2 or p+4 will not be prime, regarless of the last digit of p? Have I misunderstood you, or are you interested in a different kind of proof?
0
reply
RDKGames
Badges: 20
Rep:
?
#8
Report Thread starter 3 years ago
#8
(Original post by Pangol)
Doesn't the result we've been talking about tell you that if p is a prime then either p+2 or p+4 will not be prime, regarless of the last digit of p? Have I misunderstood you, or are you interested in a different kind of proof?
It's okay I figured it out, ignore that part
0
reply
Zacken
Badges: 22
Rep:
?
#9
Report 3 years ago
#9
(Original post by anosmianAcrimony)
Actually I think I have just worked it out. If you take any number, it is either a multiple of 3 or you can add either 2 or 4 to make it a multiple of 3. So it's impossible to have three numbers generated by adding 2 and 4 to a given number and not have at least one of them be divisible by 3. Again, I don't know how to write that up as a proper proof.
Now that the OP has his answer, your idea is correct. Formally, since p is prime and >3 then p = 1 mod 3 or p = 2 mod 3. So either p+2 = 0 mod 3 or p+4 = 0 mod 3.
0
reply
RDKGames
Badges: 20
Rep:
?
#10
Report Thread starter 3 years ago
#10
I find myself coming back to this but with a different question.

I need to formulate and explain the necessary conditions on d for the existence of such sets of k primes, for general k>5. I should give conditions on d that allow the existence of (a) one such set, and (b) more than one such set, for any given k. These conditions must be necessary but may not be sufficient.

Not quite sure where to start with this one.
0
reply
RichE
Badges: 15
Rep:
?
#11
Report 3 years ago
#11
(Original post by RDKGames)
I find myself coming back to this but with a different question.

I need to formulate and explain the necessary conditions on d for the existence of such sets of k primes, for general k>5. I should give conditions on d that allow the existence of (a) one such set, and (b) more than one such set, for any given k. These conditions must be necessary but may not be sufficient.

Not quite sure where to start with this one.
Thinking out loud a little - haven't solved the problem - but consider the case when k = 6 so that we have the numbers

p, p+d, p+2d, p+3d, p+4d, p+5d.

For many numbers - such as d = 23 - at least one of the above numbers will be a multiple of 5 and so not prime (unless it's 5 itself).

So firstly why is this the case? Secondly what (if anything) was special about 23? Then how can you generalize this?
0
reply
RDKGames
Badges: 20
Rep:
?
#12
Report Thread starter 3 years ago
#12
(Original post by RichE)
Thinking out loud a little - haven't solved the problem - but consider the case when k = 6 so that we have the numbers

p, p+d, p+2d, p+3d, p+4d, p+5d.

For many numbers - such as d = 23 - at least one of the above numbers will be a multiple of 5 and so not prime (unless it's 5 itself).

So firstly why is this the case? Secondly what (if anything) was special about 23? Then how can you generalize this?
The reason for the case that one of the number is a mult of 5 is due to the fact that if p\neq 5 then p \not\equiv 0 \mod 5

So p can be expressed p \equiv r \mod 5 where r is an integer between 1 and 4

Now for your case of d=23 (which is also a prime itself, but I'm not sure how this fact helps, if at all)
p \equiv r \mod 5
p+d \equiv (r+3) \mod 5
p+2d \equiv (r+1) \mod 5
p+3d \equiv (r+4) \mod 5
p+4d \equiv (r+2) \mod 5
p+5d \equiv r \mod 5

Now obviously one of r+1,r+2,r+3,r+4 must be equal to 0 thus a member is a mult of 5.

I'm having trouble with the actual generalisation of this but I do understand it
0
reply
RichE
Badges: 15
Rep:
?
#13
Report 3 years ago
#13
(Original post by RDKGames)
I'm having trouble with the actual generalisation of this but I do understand it
I suppose one way to start would be to try to discount what d won't work for k=6 (or maybe a specific larger k). Note I didn't have to focus on mod 5, it just served my purposes.

PS note your argument above works as well for d=28 and d=33 as for d=23. And the argument wouldn't have been much different for d=22.
0
reply
RDKGames
Badges: 20
Rep:
?
#14
Report Thread starter 3 years ago
#14
(Original post by RichE)
I suppose one way to start would be to try to discount what d won't work for k=6 (or maybe a specific larger k). Note I didn't have to focus on mod 5, it just served my purposes.

PS note your argument above works as well for d=28 and d=33 as for d=23. And the argument wouldn't have been much different for d=22.
It doesn't work if d=5?? Or even if d is a mult. of 5?
0
reply
RichE
Badges: 15
Rep:
?
#15
Report 3 years ago
#15
(Original post by RDKGames)
It doesn't work if d=5?? Or even if d is a mult. of 5?
Exactly. But remember I might have chosen to look at things mod 3 to address d=5.
0
reply
RDKGames
Badges: 20
Rep:
?
#16
Report Thread starter 3 years ago
#16
(Original post by RichE)
Exactly. But remember I might have chosen to look at things mod 3 to address d=5.
So then d couldn't be a multiple of 3.

And in general, for there to exist one such set for any given k>5, d \not\equiv 0 \mod (k-1) is a necessary condition??
0
reply
RichE
Badges: 15
Rep:
?
#17
Report 3 years ago
#17
(Original post by RDKGames)
So then d couldn't be a multiple of 3.

And in general, for there to exist one such set for any given k>5, d \not\equiv 0 \mod (k-1) is a necessary condition??
Can't we do better than that? Going back to the previous k=6 example can't we exclude d being coprime with 6,5,4,3,2? (At least for there being more than one such set.) This then is equivalent to not having 2 or 3 or 5 as a factor.
0
reply
RDKGames
Badges: 20
Rep:
?
#18
Report Thread starter 3 years ago
#18
(Original post by RichE)
Can't we do better than that? Going back to the previous k=6 example can't we exclude d being coprime with 6,5,4,3,2? (At least for there being more than one such set.) This then is equivalent to not having 2 or 3 or 5 as a factor.
I don't quite understand this. So d cannot have primes up to k as factors in order for there to exist more than one such set? Why?
0
reply
RichE
Badges: 15
Rep:
?
#19
Report 3 years ago
#19
(Original post by RDKGames)
I don't quite understand this. So d cannot have primes up to k as factors in order for there to exist more than one such set? Why?
Go back to the k=6 case. If you consider each of p, p+d,...,p+5d mod 5 then you get a full set of residues mod 5 when d is not a multiple of 5. So the list can all be primes only by p being 5 - certainly you can't then have two such lists.
0
reply
RDKGames
Badges: 20
Rep:
?
#20
Report Thread starter 3 years ago
#20
(Original post by RichE)
Go back to the k=6 case. If you consider each of p, p+d,...,p+5d mod 5 then you get a full set of residues mod 5 when d is not a multiple of 5. So the list can all be primes only by p being 5 - certainly you can't then have two such lists.
I understand that, so generally for more than one such set we have the condition on d such that d \not\equiv 0 \mod n, \forall n\in \{2,3,5,...,k \} for k>5 (ie. n is a prime up to k)?
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Are you travelling in the Uni student travel window (3-9 Dec) to go home for Christmas?

Yes (117)
28.26%
No - I have already returned home (56)
13.53%
No - I plan on travelling outside these dates (81)
19.57%
No - I'm staying at my term time address over Christmas (40)
9.66%
No - I live at home during term anyway (120)
28.99%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise