A085229 - OEIS

%I #21 Feb 07 2023 12:43:46

%S 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 26,27,28,31,30,37,32,33,34,35,36,41,38,39,40,43,42,47,44,45,46,49,48,

%U 53,50,51,52,55,54,59,56,57,58,61,60,67,62,63,64,65,66,71,68

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

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

%C From _Michael De Vlieger_, Apr 13 2022: (Start)

%C 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 Corollary: the only fixed point is a(1) = 1.

%C 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 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 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 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 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 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 Michael De Vlieger, <a href="/A085229/b085229.txt">Table of n, a(n) for n = 1..10000</a>

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

%t 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 (Python)

%o from math import gcd

%o from itertools import count, islice

%o def agen(): # generator of terms

%o     an, aset = 1, {1}

%o     for n in count(2):

%o         yield an

%o         k = 1

%o         while k in aset or any(gcd(t, k) != 1 for t in [n, an]): k+= 1

%o         aset.add(k)

%o         an = k

%o print(list(islice(agen(), 69))) # _Michael S. Branicky_, Apr 13 2022

%Y Cf. A079578, A084937, A093714.

%K nonn

%O 1,2

%A _Reinhard Zumkeller_, Jun 22 2003