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