A Permutation Involving Coprimality

[Alec Mihailovs]

> From: Leroy Quet [mailto:qq-quet at mindspring.com]
> Sent: Monday, August 23, 2004 12:02 PM
> 
> I just submitted the following sequence to the EIS:
> 
> 
> %I A000001
> %S A000001 1,3,5,2,7,4,9,11,6,13,8,15,17,10
> %N A000001 a(1) = 1; a(n) = lowest positive integer which is not among
> earlier terms of sequence, is coprime with a(n-1), is not equal to
> a(n-1)+1, and is not equal to a(n-1)-1.
> %C A000001 A permutation of the positive integers.
> %e A000001 a(8) = 11 because, among the positive integers not
occurring
> earlier in the sequence (6,8,10,11,12,...), 11 is the lowest which is
> coprime to a(7)=9, is not a(7)+1=10, and is not a(7)-1=8.
> %Y A000001 A093714
> %O A000001 1
> %K A000001 ,more,nonn,
> %A A000001 Leroy Quet (qq-quet at mindspring.com), Aug 23 2004
> 
> 
> Maybe someone could extend the sequence, if the want, and also submit
the
> inverse permutation.

Here are the extension and the inverse permutation, 

%I A099999
%S A099999 1, 3, 5, 2, 7, 4, 9, 11, 6, 13, 8, 15, 17, 10, 19, 12, 23,
14, 25, 16, 21, 26, 29, 18, 31, 20, 27, 22, 35, 24, 37, 28, 33, 38, 41,
30, 43, 32, 39, 34, 45, 47, 36, 49, 40, 51, 44, 53, 42, 55, 46, 57, 50,
59, 48, 61, 52, 63, 58, 65, 54, 67, 56, 69, 62, 71, 60, 73, 64, 75, 68,
77, 72, 79, 66, 83, 70, 81, 74, 85, 76, 87, 80, 89, 78, 95, 82, 91, 86,
93, 88, 97, 84, 101, 90, 103, 92, 99, 94, 105, 107, 96, 109, 98, 111,
100, 113, 102, 115, 104, 119, 106, 117, 110, 123, 112, 121, 108, 125,
114, 127, 116, 129, 118, 131, 120, 133, 122, 135, 124, 137, 126, 139,
128, 141, 130, 147, 134, 143, 136, 145, 132, 149, 138, 151, 140, 153,
142, 155, 144, 157, 146, 159, 148, 161, 150, 163, 152, 165, 158, 167,
154, 169, 160, 171, 164, 173, 156, 175, 162, 179, 166, 177, 170, 181,
168, 185, 172, 183, 176, 189, 178, 187, 174, 191, 180, 193, 182, 197,
184, 195, 188, 199, 186, 203, 190, 201, 194, 205, 192 
%p A099999 A:=proc(n) option remember; local t, S; 
S:=({$1..1000} minus {seq(A(i),i=1..n-1)}) minus {A(n-1)-1,A(n-1)+1}; 
t:=min(S[]); while igcd(A(n-1),t)>1 do S:=S minus {t}; t:=min(S[])
od; 
t end: A(1):=1: seq(A(n), n=1..200);
%O A099999 1
%K A099999 ,nonn,
%A A099999 Alec Mihailovs (alec at mihailovs.com), Aug 23 2004

%I A000001
%S A000001 1, 4, 2, 6, 3, 9, 5, 11, 7, 14, 8, 16, 10, 18, 12, 20, 13,
24, 15, 26, 21, 28, 17, 30, 19, 22, 27, 32, 23, 36, 25, 38, 33, 40, 29,
43, 31, 34, 39, 45, 35, 49, 37, 47, 41, 51, 42, 55, 44, 53, 46, 57, 48,
61, 50, 63, 52, 59, 54, 67, 56, 65, 58, 69, 60, 75, 62, 71, 64, 77, 66,
73, 68, 79, 70, 81, 72, 85, 74, 83, 78, 87, 76, 93, 80, 89, 82, 91, 84,
95, 88, 97, 90, 99, 86, 102, 92, 104, 98, 106, 94, 108, 96, 110, 100,
112, 101, 118, 103, 114, 105, 116, 107, 120, 109, 122, 113, 124, 111,
126, 117, 128, 115, 130, 119, 132, 121, 134, 123, 136, 125, 142, 127,
138, 129, 140, 131, 144, 133, 146, 135, 148, 139, 150, 141, 152, 137,
154, 143, 156, 145, 158, 147, 162, 149, 168, 151, 160, 153, 164, 155,
170, 157, 166, 159, 172, 161, 176, 163, 174, 165, 178, 167, 184, 169,
180, 173, 182, 171, 186, 175, 188, 179, 190, 177, 194, 183, 192, 181,
196, 185, 200, 187, 198, 191 
%N A000001 Permutation of natural numbers inverse to A09???? 
%e A000001 a(3)=2 because A09????(2)=3. 
%p A000001 A:=proc(n) option remember; local t, S; 
S:=({$1..1000} minus {seq(A(i),i=1..n-1)}) minus {A(n-1)-1,A(n-1)+1}; 
t:=min(S[]); while igcd(A(n-1),t)>1 do S:=S minus {t}; t:=min(S[])
od; 
t end: A(1):=1: L:=[seq(A(n),n=1..200)]:
a:=n-> if member(n,L,'p') then p else 0 fi: seq(a(n),n=1..195); 
%Y A000001 Cf. A09????. 
%O A000001 1 
%K A000001 ,nonn, 
%A A000001 Alec Mihailovs (alec at mihailovs.com), Aug 23 2004

Alec Mihailovs 
http://math.tntech.edu/alec/