wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> prime number pairings
        
(Message started by: BenVitale on Jun 20^th, 2009, 12:56pm)

Title: prime number pairings
Post by BenVitale on Jun 20^th, 2009, 12:56pm

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?

Title: Re: prime number pairings
Post by Obob on Jun 20^th, 2009, 1:20pm

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.

Title: Re: prime number pairings
Post by towr on Jun 20^th, 2009, 3:03pm

on 06/20/09 at 13:20:18, 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.

Title: Re: prime number pairings
Post by Obob on Jun 20^th, 2009, 3:15pm

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.

Title: Re: prime number pairings
Post by BenVitale on Jun 20^th, 2009, 3:53pm

on 06/20/09 at 13:20:18, 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.

Title: Re: prime number pairings
Post by Obob on Jun 20^th, 2009, 6:32pm

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.