|
COMMENT
|
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 (vladeta(AT)Eunet.yu), 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 (mathar(AT)strw.leidenuniv.nl), Nov 02 2007
|
|
PROGRAM
|
/* 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; } } }
|
