login
A093714
a(n) = smallest number coprime to a(n-1), not equal to a(n-1)+1, and not occurring earlier; a(1)=1.
31
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,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
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
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
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.
Sequence in context: A093715 A277911 A085229 * A353904 A353780 A080261
KEYWORD
nonn
AUTHOR
Reinhard Zumkeller, Apr 12 2004
STATUS
approved