Author |
Topic: prime number pairings (Read 418 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
prime number pairings
« on: Jun 20th, 2009, 12:56pm » |
 Quote  Modify
|
I need to prove that for every N>1 the integers from 1 to N can be arranged in an order such that
the sum of any two consecutive numbers is a prime.
For example, if I take the first 10 numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
I can rearrange them as follows: 9, 8, 3, 4, 1, 2, 5, 6, 7, 10
And If I take the next batch of 10 numbers, i can rearrange them as:
10, 19, 12, 17, 20, 11, 18, 13, 16, 15
So, from 1 to 20 I have:
9, 8, 3, 4, 1, 2, 5, 6, 7, 10, 19, 12, 17, 20, 11, 18, 13, 16, 15
I took me about 15 minutes to do this ... that's a long time. And it doesn't help me to prove what I need to prove, that is, for every N>1, I can do this arrangement
If I need to continue this, say up to N=100, it is easier to do it in tens ... I mean from 1 to 10, then from 10 to 20, etc.
Is there a more efficient way to do this?
|
| « Last Edit: Jun 20th, 2009, 12:59pm by Benny » |
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: prime number pairings
« Reply #1 on: Jun 20th, 2009, 1:20pm » |
Quote Modify
|
What I would try to do is come up with ways of rearranging the numbers so that very few different sums appear; since we do not expect most numbers to be prime, we need to make sure that there are many fewer different sums than there are numbers. Here's one rearrangement that works for N=10, for instance:
1 10 3 8 5 6 7 4 9 2
We get only two different sums, namely 11 and 13. This same strategy should work whenever N+1 and N+3 are both prime; for instance it will work for N = 40 or N = 100. If the twin prime conjecture is true, then we can at least do the arrangement for infinitely many N.
For other choices of N, you would need a different strategy. Do you have reason to believe the statement is true? It would actually surprise me a bit if a proof of this result is known for all N, just because we know so little about primes.
Your method of extending by tens will eventually fail, since making a sequence between N and N + 10 requires that there be a prime number between 2N + 1 and 2N + 19; once N is large there need not be such a prime.
|
| « Last Edit: Jun 20th, 2009, 1:56pm by Obob » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: prime number pairings
« Reply #2 on: Jun 20th, 2009, 3:03pm » |
Quote Modify
|
on Jun 20th, 2009, 1:20pm, Obob wrote:| We get only two different sums, namely 11 and 13. This same strategy should work whenever N+1 and N+3 are both prime; for instance it will work for N = 40 or N = 100. |
|
You can also adapt to a few other case, like 30, by breaking it up into multiple pieces, the first using twin primes 11 and 13, the other twin primes 41 and 43
1 10 3 8 5 6 7 4 9 2 -- 11 30 13 28 15 26 17 24 19 22 21 20 23 18 25 16 27 14 29 12
You can use any combination of twin primes, I think. Not sure how to characterize the N's it works for though; but it becomes quite a lot.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: prime number pairings
« Reply #3 on: Jun 20th, 2009, 3:15pm » |
Quote Modify
|
That's a nice trick, towr.
Of course though, to try to prove the result in general, one cannot use anything relating to the existence of twin primes.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: prime number pairings
« Reply #4 on: Jun 20th, 2009, 3:53pm » |
Quote Modify
|
on Jun 20th, 2009, 1:20pm, Obob wrote:
........... Do you have reason to believe the statement is true?
|
|
I'm not sure about this ... I just enjoy working in number theory.
Quote:
Your method of extending by tens will eventually fail, .... |
|
Yes, I suspected that eventually it would fail ... but for what value of N ... I'm experimenting here.
Suppose it works from N=90 to N=100, then after that it doesn't ... I figure that knowing this breaking point would be an interesting thing to know ... and maybe beyond that point increase the size of the interval, or some other better idea ... that's why I posted this problem in this forum.
Thanks, guys, for your input.
Quote:
since making a sequence between N and N + 10 requires that there be a prime number between 2N + 1 and 2N + 19; once N is large there need not be such a prime. |
|
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: prime number pairings
« Reply #5 on: Jun 20th, 2009, 6:32pm » |
Quote Modify
|
The whole idea of trying to build up the sequence piece by piece (for instance 10 at a time) doesn't seem very useful though. For instance if you need a sequence for N = 93, you probably can't just take any sequence for N = 90 and add on three more numbers.
Unless you found this as a problem somewhere, I would expect this to either be false or essentially unprovable.
|
| « Last Edit: Jun 20th, 2009, 6:33pm by Obob » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print