mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-11-05, 20:13   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default Permutations Yielding Primes

I permuted the first 20 positive integers such that the sum or difference
of adjacent integers is prime. This is (perhaps not surprisingly) easy,
considering the number of primes < 20. Of course, odds and evens must
alternate. Given that, just how likely is this property? More generally,
is it always possible to permute the first N > 1 integers so that the sum or
difference of adjacent integers is prime? If not, how high can we go?
davar55 is offline   Reply With Quote
Old 2008-11-05, 23:57   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

718810 Posts
Default

For instance:

[1 2]

[1 2 3]

[1 2 3 4]

Quote:
Originally Posted by davar55 View Post
Of course, odds and evens must alternate.
Not necessarily, unless the sum or difference must be an odd prime.

[1 2 4 3 5]

[1 2 3 4 6 5]

[1 2 3 4 6 5 7]

[1 2 3 4 6 8 5 7]

[1 2 3 4 6 8 5 7 9]

[1 2 3 4 6 8 5 7 9 10]

[1 2 3 4 6 11 8 5 7 9 10]

[1 2 3 4 6 11 8 5 7 9 10 12]

[1 2 3 4 13 6 11 8 5 7 9 10 12]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 15]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 15 16]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 15 16]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 15 16 18]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 15 16 18 19]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 20 15 16 18 19]

[1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 20 15 16 18 19 21]

Last fiddled with by cheesehead on 2008-11-06 at 00:08
cheesehead is offline   Reply With Quote
Old 2008-11-06, 14:31   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default

You're right, if ANY prime is ok (including 2) then it's always easy,
e.g. [19,17,15,13,11,9,7,5,3,1,2,4,6,8,10,12,14,16,18,20].
My comment about alternation missed this.
davar55 is offline   Reply With Quote
Old 2008-11-07, 00:43   #4
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2·5·23 Posts
Default

Start with [1 6 3 8 5 2 7 4 9] which contains 1 to 9. Then repeat the 8 differences (which are all +/-3 or +/-5) forever. This gives an infinite solution, and finite solutions for all N of form 8m+1 or 8m. Other N values of form 8m+k can be reached by starting with a solution for k which ends with k, and then repeating the difference pattern.
Jens K Andersen is offline   Reply With Quote
Old 2008-11-07, 09:03   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

So, in order to be challenging the rule needs to require that a certain proportion of the formed primes be sums rather than differences.
cheesehead is offline   Reply With Quote
Old 2008-11-07, 12:45   #6
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

2×5×53 Posts
Default

Quote:
Originally Posted by cheesehead View Post
So, in order to be challenging the rule needs to require that a certain proportion of the formed primes be sums rather than differences.
Here's a solution for N=24 which uses only sums. Feel free to expand on that:

2 1 | 4 3 | 8 5 6 7 | 10 9 | 14 17 12 11 18 13 16 15 | 22 19 24 23 20 21 | ...

The pipe symbols mark sub-solutions for N=2, N=4, N=8, N=10, N=18, and N=24.
ckdo is offline   Reply With Quote
Old 2008-11-07, 18:15   #7
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

For prime sums, see http://primepuzzles.net/puzzles/puzz_176.htm which is about circles, corresponding to the first and last number in a sequence being adjacent.

See also A051252.

Last fiddled with by Jens K Andersen on 2008-11-07 at 18:19 Reason: Add OEIS link
Jens K Andersen is offline   Reply With Quote
Old 2008-11-08, 04:40   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

A055265 is related.
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
How To Find The Formula of This Permutations? dini Puzzles 0 2009-03-22 03:39
permutations davieddy Puzzles 27 2007-07-15 22:06
PrimeForm yielding few results - problem with equation? roger Information & Answers 1 2006-10-15 03:50
Number of n-element permutations with exactly k inversions tytus Math 3 2005-02-04 10:10

All times are UTC. The time now is 05:26.

Sat Oct 31 05:26:38 UTC 2020 up 51 days, 2:37, 2 users, load averages: 2.73, 2.19, 1.98

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.