A352588 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.

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, 26, 31, 24, 35, 32, 37, 28, 33, 38, 41, 30, 43, 34, 39, 44, 47, 36, 49, 40, 51, 46, 45, 52, 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

Offset: 1

Author

Scott R. Shannon, Apr 29 2022

Keywords

• nonn

Comments

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

Coincides with A093714 for n >= 17. - Scott R. Shannon, May 02 2022.

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.

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.

Beyond a(4) = 3 the primes appear in their natural order.

From Michael De Vlieger, May 01 2022: (Start)

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.

Corollary: even terms do not appear adjacently in the sequence, however we may have runs of odd terms.

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.

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)

Examples

			a(3) = 5 as a(2) = 2, and the smallest unused number coprime to 2 that does not equal 2+1=3 is 5.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A064413, A093714, A121216, A347113.

Programs

Mathematica

nn = 76; c[_] = 0; a[1] = c[1] = 1; a[2] = c[2] = 2; u = 3
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 *)