# Permutations Coprime &...

[Leroy Quet]

Uggg!!! I should have thought about this only two seconds more!!!

Thanks,
Leroy Quet


>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