A354224 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.

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, 33, 26, 29, 25, 31, 34, 27, 32, 40, 38, 37, 36, 42, 35, 41, 39, 43, 46, 48, 44, 47, 45, 56, 52, 54, 50, 53, 51, 60, 49, 63, 62, 59, 55, 61, 58, 57, 66, 70, 64, 67

Offset: 1

Author

Rémy Sigrist, May 20 2022

Keywords

• nonn

Comments

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

Examples

			The first terms are:
  n   a(n)  gcd(n, a(n))
  --  ----  ------------
   1     1             1
   2     2             2
   3     3             3
   4     6             2
   5     5             5
   6     4             2
   7     7             7
   8    10             2
   9    12             3
  10     8             2
  11    11            11
  12     9             3
  13    13            13
  14    16             2
		

Links

• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A238758.

Programs

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)))

Python

from math import gcd
from sympy import isprime
from itertools import count, islice
def agen(): # generator of terms
    aset, mink = {1}, 2; yield 1
    for n in count(2):
        k = mink
        while k in aset or not isprime(gcd(n, k)): k += 1
        aset.add(k); yield k
        while mink in aset: mink += 1
print(list(islice(agen(), 67))) # Michael S. Branicky, May 23 2022

Formula

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