A109813 Number of permutations of (the positive integers <= n and coprime to n), where each element of the permutations is coprime to its adjacent elements.

1, 1, 2, 2, 12, 2, 72, 24, 144, 12, 22032, 24, 476928, 480, 1728, 9600, 805146624, 720, 36481536000, 30240, 1728000, 312000, 192859121664000, 40320, 2159795404800, 46293120, 249684249600, 58423680

Offset: 1

Author

Leroy Quet, Aug 16 2005

Keywords

• more
• nonn

Comments

Sequence continues: a(29) = ?, 40320, ?, 1893397524480, 32006016000000, 478511953920, ?, 209018880, ?, 122634632171520, ?, 665481277440, ?, 399168000. - Franklin T. Adams-Watters, Sep 25 2006

Examples

			The integers coprime to 10 and <= 10 are (1,3,7,9).
Of the permutations of these integers, there are 12 permutations where all adjacent terms are coprime, i.e., where 3 and 9 are not adjacent. So the 10th term of the sequence is 12.
		

Crossrefs

Cf. A076220.

Programs

PARI

{A109813(x)=local(v, A, d, r, M, i, j); n=eulerphi(x); v=vector(n,i,0); j=0; for(i=1,x,if(gcd(i,x)==1,j++;v[j]=i)); A=matrix(n, n, i, j, gcd(v[i], v[j])==1); r=0; for(s=1, 2^n-1, M=vecextract(A, s, s)^(n-1); d=matsize(M)[1]; r+=(-1)^(n-d)*sum(i=1, d, sum(j=1, d, M[i, j]))); r} \\ Franklin T. Adams-Watters, Sep 25 2006

Extensions

More terms from Franklin T. Adams-Watters, Sep 25 2006