login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #44 Feb 07 2023 05:54:56

%S 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,

%T 26,31,24,35,32,37,28,33,38,41,30,43,34,39,44,47,36,49,40,51,46,45,52,

%U 55,42,53,48,59,50,57,56,61,54,65,58,63,62,67,60,71,64,69,68,73,66,79

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

%C 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

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

%C Comments from _N. J. A. Sloane_, May 02 2022: (Start)

%C Proof that this is a permutation of the natural numbers.

%C 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).

%C 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.]

%C 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.]

%C 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.]

%C 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.

%C This completes the proof.

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

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

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

%C (End)

%C Coincides with A352588 for n >= 17. - _Scott R. Shannon_, May 02 2022

%H Michael De Vlieger, <a href="/A093714/b093714.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

%o (Python)

%o from math import gcd

%o from itertools import islice

%o def agen(): # generator of terms

%o an, aset, mink = 1, {1}, 2

%o while True:

%o yield an

%o k = mink

%o while k in aset or gcd(an, k) != 1 or k-an == 1: k += 1

%o an = k

%o aset.add(an)

%o while mink in aset: mink += 1

%o print(list(islice(agen(), 72))) # _Michael S. Branicky_, May 02 2022

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

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

%Y See Comments in A109812 for a set-theory analog.

%K nonn

%O 1,2

%A _Reinhard Zumkeller_, Apr 12 2004