Permutations Of Relative-Primality

Leroy Quet qqquet at
Fri Nov 1 02:52:39 CET 2002

Just posted this to sci.math:

Let {a(k)} be a permutation of {1,2,3,...,n}.

How many permutions of 1-through-n are there such that

GCD( sum{k=1 to m} a(k) , a(m+1) ) = 1

for all positive integers m <= n-1 ?

The sequence begins: 1, 2, 2, 8,....     (*)

(This sequence is too short to do an easy search on the EIS.)

Two things:

For n >= 2, a(1) can be exchanged with a(2), so the n'th term of the 
sequence (*) is even.

Also, a(n) must be relatively prime with n(n+1)/2.

Leroy Quet

More information about the SeqFan mailing list