cp's OEIS Frontend

A085229 Smallest number which is coprime to n and to a(n-1), and is not yet in the sequence; a(1)=1.

%I A085229 #21 Feb 07 2023 12:43:46
%S A085229 1,3,2,5,4,7,6,11,8,9,10,13,12,17,14,15,16,19,18,23,20,21,22,25,24,29,
%T A085229 26,27,28,31,30,37,32,33,34,35,36,41,38,39,40,43,42,47,44,45,46,49,48,
%U A085229 53,50,51,52,55,54,59,56,57,58,61,60,67,62,63,64,65,66,71,68
%N A085229 Smallest number which is coprime to n and to a(n-1), and is not yet in the sequence; a(1)=1.
%C A085229 Permutation of natural numbers with inverse A085230: a(A085230(n))=A085230(a(n))=n.
%C A085229 From _Michael De Vlieger_, Apr 13 2022: (Start)
%C A085229 Theorem 1: 2 | a(2k+1) for k > 0, consequence of the lexically earliest and coprimality axioms. Even numbers appear in order as a consequence of the latter axiom and since numbers are either even or odd.
%C A085229 Corollary: the only fixed point is a(1) = 1.
%C A085229 Theorem 2: Generally, if prime p | a(n) then p is coprime to a(n +/- 1). For p = 2, 2 | a(2k+1) for k > 0 since 2 is the smallest prime. For odd p it is not necessarily true that given p | a(n) -> p | a(n+2) or p | a(n-2), since there may be a smaller m such that (a(n-1), m) = 1, q | m for prime q < p, and is not in a(1..n-1).
%C A085229 For these reasons, if we also set a(2) = 3, then we need not also check (n, a(n)) = 1, since it isn't possible. If we do not check (n, a(n)) = 1 and set a(2) = 3, 2 would follow 1 since 1 is coprime to all numbers.
%C A085229 Theorem 3: 3 | a(3k+1) for k > 1. Proof: For even k, 6 | a(3k+1), i.e., 6 | a(n) : n mod 6 = 1, and it is easy to see that since even numbers appear in order in the sequence, these even multiples of 3 are also in order. Because 3 | a(n) : n mod 6 = 1, we cannot have 3 | a(n) for n congruent to 0 or 2 (mod 6). Furthermore, we know that 2 | a(n) for n congruent to 3 or 5 (mod 6). So 3 | a(n) odd : n mod 6 = 4, that is, 3 | a(3k+1) for k > 1.
%C A085229 Theorem 4: Odd primes q set records. Proof: (q, a(n-1)) = 1 as a consequence of lexically earliest axiom that rules out equality, and by the definition of prime. 2 is displaced on account of the axiom that bans equality between n and a(n). Therefore, whereupon q is the smallest unused odd number, it enters the sequence.
%C A085229 A consequence of theorems 1 and 3 is that powers of 2 and those of 3 excepting 3 itself do not set records, since their adjacency is governed by a(n-1). The powers of other primes do set records since coprimality does not depend on multiplicity.
%C A085229 The smallest composite record is a(24) = 25. Smallest record m with omega(m) > 1 is a(54) = 55. Powers of 2 and 3 are absent from records for n <= 2^20. (End)
%H A085229 Michael De Vlieger, <a href="/A085229/b085229.txt">Table of n, a(n) for n = 1..10000</a>
%H A085229 Michael De Vlieger, <a href="/A085229/a085229.png">Annotated log-log scatterplot of a(n)</a> for n = 1..256, showing records in red, local minima in blue, and highlighting fixed points in amber and primes in green.
%H A085229 Amit Kumar Basistha and Eugen J. Ionascu, <a href="https://arxiv.org/abs/2302.02838">A special sequence and primorial numbers</a>, arXiv:2302.02838 [math.NT], 2023.
%H A085229 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%t A085229 nn = 10000; c[_] = 0; a[1] = c[1] = 1; a[2] = 3; c[3] = u = 2; Do[k = u; While[Nand[c[k] == 0, CoprimeQ[a[i-1], k]], k++]; Set[{a[i], c[k]}, {k, i}]; If[a[i] == u, While[c[u] > 0, u++]], {i, 3, nn}]; Array[a, nn] (* _Michael De Vlieger_, Apr 13 2022 *)
%o A085229 (Python)
%o A085229 from math import gcd
%o A085229 from itertools import count, islice
%o A085229 def agen(): # generator of terms
%o A085229     an, aset = 1, {1}
%o A085229     for n in count(2):
%o A085229         yield an
%o A085229         k = 1
%o A085229         while k in aset or any(gcd(t, k) != 1 for t in [n, an]): k+= 1
%o A085229         aset.add(k)
%o A085229         an = k
%o A085229 print(list(islice(agen(), 69))) # _Michael S. Branicky_, Apr 13 2022
%Y A085229 Cf. A079578, A084937, A093714.
%K A085229 nonn
%O A085229 1,2
%A A085229 _Reinhard Zumkeller_, Jun 22 2003