A085229 Smallest number which is coprime to n and to a(n-1), and is not yet in the sequence; a(1)=1.

1, 3, 2, 5, 4, 7, 6, 11, 8, 9, 10, 13, 12, 17, 14, 15, 16, 19, 18, 23, 20, 21, 22, 25, 24, 29, 26, 27, 28, 31, 30, 37, 32, 33, 34, 35, 36, 41, 38, 39, 40, 43, 42, 47, 44, 45, 46, 49, 48, 53, 50, 51, 52, 55, 54, 59, 56, 57, 58, 61, 60, 67, 62, 63, 64, 65, 66, 71, 68

Offset

1,2

Comments

Permutation of natural numbers with inverse A085230: a(A085230(n))=A085230(a(n))=n.

From Michael De Vlieger, Apr 13 2022: (Start)

Theorem 1: 2 | a(2k+1) for k > 0, consequence of the lexically earliest and coprimality axioms. Even numbers appear in order as a consequence of the latter axiom and since numbers are either even or odd.

Corollary: the only fixed point is a(1) = 1.

Theorem 2: Generally, if prime p | a(n) then p is coprime to a(n +/- 1). For p = 2, 2 | a(2k+1) for k > 0 since 2 is the smallest prime. For odd p it is not necessarily true that given p | a(n) -> p | a(n+2) or p | a(n-2), since there may be a smaller m such that (a(n-1), m) = 1, q | m for prime q < p, and is not in a(1..n-1).

For these reasons, if we also set a(2) = 3, then we need not also check (n, a(n)) = 1, since it isn't possible. If we do not check (n, a(n)) = 1 and set a(2) = 3, 2 would follow 1 since 1 is coprime to all numbers.

Theorem 3: 3 | a(3k+1) for k > 1. Proof: For even k, 6 | a(3k+1), i.e., 6 | a(n) : n mod 6 = 1, and it is easy to see that since even numbers appear in order in the sequence, these even multiples of 3 are also in order. Because 3 | a(n) : n mod 6 = 1, we cannot have 3 | a(n) for n congruent to 0 or 2 (mod 6). Furthermore, we know that 2 | a(n) for n congruent to 3 or 5 (mod 6). So 3 | a(n) odd : n mod 6 = 4, that is, 3 | a(3k+1) for k > 1.

Theorem 4: Odd primes q set records. Proof: (q, a(n-1)) = 1 as a consequence of lexically earliest axiom that rules out equality, and by the definition of prime. 2 is displaced on account of the axiom that bans equality between n and a(n). Therefore, whereupon q is the smallest unused odd number, it enters the sequence.

A consequence of theorems 1 and 3 is that powers of 2 and those of 3 excepting 3 itself do not set records, since their adjacency is governed by a(n-1). The powers of other primes do set records since coprimality does not depend on multiplicity.

The smallest composite record is a(24) = 25. Smallest record m with omega(m) > 1 is a(54) = 55. Powers of 2 and 3 are absent from records for n <= 2^20. (End)

Links

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

Michael De Vlieger, Annotated log-log scatterplot of a(n) for n = 1..256, showing records in red, local minima in blue, and highlighting fixed points in amber and primes in green.

Amit Kumar Basistha and Eugen J. Ionascu, A special sequence and primorial numbers, arXiv:2302.02838 [math.NT], 2023.

Index entries for sequences that are permutations of the natural numbers

Mathematica

nn = 10000; c[_] = 0; a[1] = c[1] = 1; a[2] = 3; c[3] = u = 2; Do[k = u; While[Nand[c[k] == 0, CoprimeQ[a[i-1], k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 3, nn}]; Array[a, nn] (* Michael De Vlieger, Apr 13 2022 *)

Prog

(Python)
from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    an, aset = 1, {1}
    for n in count(2):
        yield an
        k = 1
        while k in aset or any(gcd(t, k) != 1 for t in [n, an]): k+= 1
        aset.add(k)
        an = k
print(list(islice(agen(), 69))) # Michael S. Branicky, Apr 13 2022

Crossrefs

Cf. A079578, A084937, A093714.

Sequence in context: A085230 A093715 A277911 * A093714 A353904 A353780

Adjacent sequences: A085226 A085227 A085228 * A085230 A085231 A085232

Keyword

nonn

Author

Reinhard Zumkeller, Jun 22 2003

Status

approved