OFFSET

1,2

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

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

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

PROG

(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

CROSSREFS

KEYWORD

nonn

AUTHOR

Reinhard Zumkeller, Apr 12 2004

STATUS

approved