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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A086595 Number of ways to arrange the numbers 1..n in a circle (up to direction) such that every two adjacent numbers are relatively prime. 7
1, 1, 2, 2, 12, 4, 72, 72, 720, 576, 22032, 7776, 476928, 400896, 6352992, 8515584, 805146624, 279023616, 36481536000, 23627980800, 881012367360, 1065509240832, 192859121664000, 65362194432000, 10489384048435200, 12214493322854400, 981016943829811200, 937734333109862400, 268367392739686809600 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n) is also the number of permutations of 2..n such that every two adjacent numbers are relatively prime.

LINKS

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

FORMULA

For prime p, a(p)=A076220(p-1). - Max Alekseyev, Jun 13 2005

EXAMPLE

a(6) = 4 since there are 4 ways to arrange 1,2,3,4,5,6 in a circle such that every two adjacent numbers are relatively prime: 1-2-3-4-5-6-1, 1-4-3-2-5-6-1, 1-6-5-2-3-4-1, 1-6-5-4-3-2-1.

PROG

(PARI) { A086595(n) = my(d, A, r, M); A=matrix(n, n, i, j, gcd(i, j)==1); r=0; forstep(s=1, 2^n-1, 2, M=vecextract(A, s, s)^n; d=matsize(M)[1]; r+=(-1)^(n-d)*M[1, 1]); r } /* Alekseyev */

CROSSREFS

Cf. A076220.

Sequence in context: A241519 A288339 A288808 * A279718 A279671 A279179

Adjacent sequences:  A086592 A086593 A086594 * A086596 A086597 A086598

KEYWORD

nonn

AUTHOR

Lior Manor Jul 23 2003

EXTENSIONS

a(15)=6352992 and a(16)=8515584 from Ray Chandler and Joshua Zucker, Apr 10 2005

a(17)-a(29) from Max Alekseyev, Jun 13 2005, Jul 05 2014

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 10:59 EDT 2017. Contains 292518 sequences.