%I #40 May 02 2022 21:05:46
%S 1,2,5,3,7,4,9,8,11,6,13,10,17,12,19,14,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,70,81,74,77
%N a(1) = 1, a(2) = 2; for n > 2, a(n) is the smallest positive number that has not yet appeared that is coprime to a(n-1) but does not equal a(n-1)+1.
%C Theorem: This is a permutation of the natural numbers. The proof is essentially the same as for A093714. - _N. J. A. Sloane_, May 02 2022
%C Coincides with A093714 for n >= 17. - _Scott R. Shannon_, May 02 2022.
%C In the first 100 million terms the sequence's values are concentrated along the line a(n) = n, resulting in 1160 fixed points in this range. However the last fixed point in this range is a(1034312), with the sequence oscillating above and below the line a(n) = n from then on. It is unknown if this behavior continues or if more fixed points eventually appear.
%C The largest offset in the first 100 million terms from the line a(n) = n is a(45902952) = 45902981, with an offset of 29. In this range a number is rejected as the next term on 207 occasions as it equals a(n-1)+1.
%C Beyond a(4) = 3 the primes appear in their natural order.
%C From _Michael De Vlieger_, May 01 2022: (Start)
%C Theorem: if prime p | a(n-1) then p does not divide a(n). Proof: primes either divide or are coprime to a given number. We say numbers m and n are coprime iff gcd(m,n) = 1. Suppose p | a(n-1) and p | a(n), then p | m, where m = gcd(a(n-1), a(n)). By definition of prime and divisor, m > 1, a contradiction.
%C Corollary: even terms do not appear adjacently in the sequence, however we may have runs of odd terms.
%C Theorem: fixed point a(n) = n implies a(n) and n have the same parity. Proof: a(n) = n iff a(n) mod n = 0, since n | n. Suppose prime q|n yet gcd(a(n), q) = 1, then a(n) != n, a contradiction.
%C Observation: there are 9 runs of odd terms for n = 1..2^28, one of 3 odd terms {5, 3, 7}, the rest of 2. Fixed points appear in intervals [1, 3], [4, 17], [78, 1787], [15022, 38123], and [45053, 1036043]. The last run of odd terms for n <= 2^28 begins at n = 1036043. Is there another run of odd terms that will begin a new interval that harbors fixed points? (End)
%H Michael De Vlieger, <a href="/A352588/b352588.txt">Table of n, a(n) for n = 1..10000</a>
%e a(3) = 5 as a(2) = 2, and the smallest unused number coprime to 2 that does not equal 2+1=3 is 5.
%t nn = 76; c[_] = 0; a[1] = c[1] = 1; a[2] = c[2] = 2; u = 3
%t 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, 3, nn}]; Array[a, nn] (* _Michael De Vlieger_, May 01 2022 *)
%Y Cf. A064413, A093714, A121216, A347113.
%K nonn
%O 1,2
%A _Scott R. Shannon_, Apr 29 2022
|