login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A125712 Number of permutations of 1..2n in which the sum of every two adjacent elements is a prime number, including the sum of first and last elements. 0
2, 8, 12, 32, 960, 12288, 40320, 1296384, 13862592 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

For 2n=4 we have a(2) = 8. One of the permutations is 1 4 3 2. Let's check: 1 + 4 = 5 is a prime number; 4 + 3 = 7 is a prime number; 3 + 2 = 5 is a prime number; 2 + 1 = 3 is a prime number; so we say it's a legal permutation.

a(n) = 4*n*A051252(n), n>1. - Vladeta Jovovic, Feb 02 2007

As explicitly checked for 2<=n<=9, a(n)=4*n*A051252(n). This is twice the length of the permutation multiplied by A051252(n), where the factor 4n counts the permutations generated by any of the 2n cyclic shifts or any of the 2n cyclic shifts followed by reversal. The exception is for n=1, where reversal and shift yield the same image of the permutation. - R. J. Mathar, Nov 02 2007

LINKS

Table of n, a(n) for n=1..9.

EXAMPLE

a(2) = 8 because we can generate 8 different permutations:

1 2 3 4

1 4 3 2

2 1 4 3

2 3 4 1

3 2 1 4

3 4 1 2

4 1 2 3

4 3 2 1

in which the sum of every two adjacent elements is a prime number, including the sum of first and last elements.

PROG

/* I write the program in C++, but it's not very efficient. I hope someone can improve the algorithm. */ #include <vector> #include <iostream> #include <algorithm> using namespace std; const bool isPRIME[41] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 }; int smartP_3(int n, bool p){ vector<int> arr(n - 1); for(int i = n - 2; i >= 0; --i) arr[i] = i + 2; int cnt = 0, last_i = (n > 2 ? n - 3 : 0); ostream_iterator<int> out(cout, " "); do{ if(!isPRIME[1 + arr[0]] || !isPRIME[1 + arr[n - 2]]) continue; int i = last_i; for(; i < n - 2 && isPRIME[arr[i] + arr[i + 1]]; ++i); if(i == n - 2){ for(i = 0; i < last_i && isPRIME[arr[i] + arr[i + 1]]; ++i); if(i == last_i){ cnt += n; if(p){ cout<<"1 "; copy(arr.begin(), arr.end(), out); cout<<endl; } }else last_i = i; }else last_i = i; }while(next_permutation(arr.begin(), arr.end())); return cnt; } int main() { int n; while(cin>>n){ if(n <= 20 && n > 1){ long start = clock(); cout<<smartP_3(n, false)<<endl; cout<<"Time: "<<(clock() - start)<<" ms"<<endl; } } }

CROSSREFS

Sequence in context: A306898 A069185 A037197 * A062290 A176961 A078541

Adjacent sequences:  A125709 A125710 A125711 * A125713 A125714 A125715

KEYWORD

nonn,more

AUTHOR

DoZerg (daidodo(AT)gmail.com), Feb 01 2007

EXTENSIONS

Can be extended using A051252.

a(8) and a(9) from R. J. Mathar, Nov 02 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 17:50 EDT 2019. Contains 324330 sequences. (Running on oeis4.)