login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Lexicographically earliest sequence of distinct positive integers such that a(1) = 1 and for any n > 1, the greatest common divisor of n and a(n) is a prime number.
0

%I #12 Jun 07 2022 11:12:22

%S 1,2,3,6,5,4,7,10,12,8,11,9,13,16,18,14,17,15,19,22,24,20,23,21,30,28,

%T 33,26,29,25,31,34,27,32,40,38,37,36,42,35,41,39,43,46,48,44,47,45,56,

%U 52,54,50,53,51,60,49,63,62,59,55,61,58,57,66,70,64,67

%N Lexicographically earliest sequence of distinct positive integers such that a(1) = 1 and for any n > 1, the greatest common divisor of n and a(n) is a prime number.

%C This sequence is a self-inverse permutation of the positive integers.

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(n) = n iff n = 1 or n is a prime number.

%e The first terms are:

%e n a(n) gcd(n, a(n))

%e -- ---- ------------

%e 1 1 1

%e 2 2 2

%e 3 3 3

%e 4 6 2

%e 5 5 5

%e 6 4 2

%e 7 7 7

%e 8 10 2

%e 9 12 3

%e 10 8 2

%e 11 11 11

%e 12 9 3

%e 13 13 13

%e 14 16 2

%o (PARI) s=0; for (n=1, 67, for (v=1, oo, if (!bittest(s,v) && (n==1 || isprime(gcd(n,v))), print1 (v", "); s+=2^v; break)))

%o (Python)

%o from math import gcd

%o from sympy import isprime

%o from itertools import count, islice

%o def agen(): # generator of terms

%o aset, mink = {1}, 2; yield 1

%o for n in count(2):

%o k = mink

%o while k in aset or not isprime(gcd(n, k)): k += 1

%o aset.add(k); yield k

%o while mink in aset: mink += 1

%o print(list(islice(agen(), 67))) # _Michael S. Branicky_, May 23 2022

%Y Cf. A238758.

%K nonn

%O 1,2

%A _Rémy Sigrist_, May 20 2022