cp's OEIS Frontend

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

%I A093714 #44 Feb 07 2023 05:54:56
%S A093714 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 A093714 26,31,24,35,32,37,28,33,38,41,30,43,34,39,44,47,36,49,40,51,46,45,52,
%U A093714 55,42,53,48,59,50,57,56,61,54,65,58,63,62,67,60,71,64,69,68,73,66,79
%N A093714 a(n) = smallest number coprime to a(n-1), not equal to a(n-1)+1, and not occurring earlier; a(1)=1.
%C A093714 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 A093714 Permutation of natural numbers with inverse A093715: a(A093715(n))=A093715(a(n))=n.
%C A093714 Comments from _N. J. A. Sloane_, May 02 2022: (Start)
%C A093714 Proof that this is a permutation of the natural numbers.
%C A093714 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 A093714 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 A093714 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 A093714 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 A093714 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 A093714 This completes the proof.
%C A093714 Conjecture 1: If p is a prime >= 3, p-1 appears after p.
%C A093714 Conjecture 2: If p is a prime, the first term divisible by p is p itself.
%C A093714 Conjecture 3: If a(n) = p is a prime >= 5, then n < p.
%C A093714 (End)
%C A093714 Coincides with A352588 for n >= 17. - _Scott R. Shannon_, May 02 2022
%H A093714 Michael De Vlieger, <a href="/A093714/b093714.txt">Table of n, a(n) for n = 1..10000</a>
%H A093714 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%t A093714 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 A093714 (Python)
%o A093714 from math import gcd
%o A093714 from itertools import islice
%o A093714 def agen(): # generator of terms
%o A093714     an, aset, mink = 1, {1}, 2
%o A093714     while True:
%o A093714         yield an
%o A093714         k = mink
%o A093714         while k in aset or gcd(an, k) != 1 or k-an == 1: k += 1
%o A093714         an = k
%o A093714         aset.add(an)
%o A093714         while mink in aset: mink += 1
%o A093714 print(list(islice(agen(), 72))) # _Michael S. Branicky_, May 02 2022
%Y A093714 Cf. A085229, A347113, A352588, A352928 (smallest missing number).
%Y A093714 A352929 gives indices of prime terms, A352930 = first differences, A352931 = a(n)-n. See also A352932.
%Y A093714 See Comments in A109812 for a set-theory analog.
%K A093714 nonn
%O A093714 1,2
%A A093714 _Reinhard Zumkeller_, Apr 12 2004