# Permutations Coprime &...

[Edwin Clark]

On Sun, 16 Mar 2003, Leroy Quet wrote:

> I have discussed a less-limiting variation of this problem before 
> (sans the a(k-1)+a(k+1) coprime to a(k) condition).
> 
> For every positive integer n, what are the number of permutations,
> a(1),a(2),a(3),...,a(n),
> of {1,2,3,...,n}
> 
> where GCD(a(k),a(k+1)) = 1 for all k, 1<=k<=n-1;
> 
> AND where, as well,
> GCD(a(k),a(k-1)+a(k+1)) = 1 for all k, 2<=k<=n-1?
> 
> I think the sequence begins:
> 1, 2, 2, 2,...
> 

Was this a trick question? :-)

The sequence is 

          1, 2, 2, 2, 4, 0, 0, 0, 0, . . 

with all zeros from n = 6 onward.

Note that you cannot have two consecutive even numbers
and you cannot have "odd, even, odd" in such a permutation. 

--Edwin Clark