A354225 Lexicographically earliest sequence of distinct positive integers such that a(1) = 1 and for any n > 1, n / gcd(n, a(n)) and a(n) / gcd(n, a(n)) are prime.

1, 3, 2, 6, 7, 4, 5, 12, 15, 14, 13, 8, 11, 10, 9, 24, 19, 27, 17, 28, 33, 26, 29, 16, 35, 22, 18, 20, 23, 42, 37, 48, 21, 38, 25, 54, 31, 34, 51, 56, 43, 30, 41, 52, 63, 58, 53, 32, 77, 70, 39, 44, 47, 36, 65, 40, 69, 46, 61, 84, 59, 74, 45, 96, 55, 78, 71

Offset

1,2

Comments

This sequence is a self-inverse permutation of the positive integers that preserves the number of prime divisors (with or without multiplicity).

Links

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Michael De Vlieger, Annotated log-log plot of a(n), n = 1..2^14, showing records in red, local minima in blue, highlighting primes in green, fixed points in gold, and composite prime powers in magenta.

Index entries for sequences that are permutations of the natural numbers

Formula

a(prime(2*n)) = prime(2*n-1) (where prime(n) denotes the n-th prime number).

Example

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

Mathematica

nn = 120; c[_] = 0; a[1] = c[1] = 1; u = 2; Do[k = u; While[Nand[c[k] == 0, AllTrue[{i/#, k/#}, PrimeQ] &@ GCD[i, k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[k == u, While[c[u] > 0, u++]], {i, 2, nn}]; Array[a, nn] (* Michael De Vlieger, May 22 2022 *)

Prog

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

Crossrefs

Cf. A122280.

Sequence in context: A375183 A377355 A371961 * A154445 A165199 A371962

Adjacent sequences: A354222 A354223 A354224 * A354226 A354227 A354228

Keyword

nonn

Author

Rémy Sigrist, May 20 2022

Status

approved