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,2

Comments

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

Links

Table of n, a(n) for n=1..67.

Index entries for sequences that are permutations of the natural numbers

Formula

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

Example

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

Prog

(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

Crossrefs

Cf. A238758.

Sequence in context: A122308 A122307 A188568 * A305418 A284459 A106451

Adjacent sequences: A354221 A354222 A354223 * A354225 A354226 A354227

Keyword

nonn

Author

Rémy Sigrist, May 20 2022

Status

approved