A093714 a(n) = smallest number coprime to a(n-1), not equal to a(n-1)+1, and not occurring earlier; a(1)=1.

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

Offset: 1

Author

Reinhard Zumkeller, Apr 12 2004

Keywords

• nonn

Comments

Lexicographically earliest infinite sequence of distinct positive numbers such that gcd(a(n-1), a(n)) = 1, a(n) != a(n-1) + 1. - N. J. A. Sloane, May 02 2022

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

Comments from N. J. A. Sloane, May 02 2022: (Start)

Proof that this is a permutation of the natural numbers.

1. As usual for a "lexicographically earliest sequence" of this class, there is a function B(k) such that a(n) > k for all n > B(k).

2. For any prime p, p divides a(n) for some n. [Suppose not. Using 1, find n_0 such that a(n) > p^2 for all n >= n_0. But if a(n) > p^2, then p is a smaller choice for a(n+1), contradiction.]

3. For any prime p, p divides infinitely many terms. [Suppose not. Let p^i be greater than any multiple of p in the sequence. Go out a long way, and find a term greater than p^i. Then p^i is a smaller candidate for the next term. Contradiction.]

4. Every prime p appears naked. [If not, using 3, find a large multiple of p, G*p, say. But then p would have been a smaller candidate than G*p. Contradiction.]

5. The next term after a prime p is the smallest number not yet in the sequence which is relatively prime to p. Suppose k is missing from the sequence, and find a large prime p that does not divide k. Then the term after p will be k. So every number appears.

This completes the proof.

Conjecture 1: If p is a prime >= 3, p-1 appears after p.

Conjecture 2: If p is a prime, the first term divisible by p is p itself.

Conjecture 3: If a(n) = p is a prime >= 5, then n < p.

(End)

Coincides with A352588 for n >= 17. - Scott R. Shannon, May 02 2022

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A085229, A347113, A352588, A352928 (smallest missing number).

A352929 gives indices of prime terms, A352930 = first differences, A352931 = a(n)-n. See also A352932.

See Comments in A109812 for a set-theory analog.

Programs

Mathematica

nn = 120; c[] = 0; a[1] = c[1] = 1; u = 2; Do[k = u; While[Nand[c[k] == 0, CoprimeQ[#, k], k != # + 1], k++] &@ a[i - 1]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 2, nn}]; Array[a, nn] (* _Michael De Vlieger, May 02 2022 *)

Python

from math import gcd
from itertools import islice
def agen(): # generator of terms
    an, aset, mink = 1, {1}, 2
    while True:
        yield an
        k = mink
        while k in aset or gcd(an, k) != 1 or k-an == 1: k += 1
        an = k
        aset.add(an)
        while mink in aset: mink += 1
print(list(islice(agen(), 72))) # Michael S. Branicky, May 02 2022