OFFSET
1,2
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)
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..10000
EXAMPLE
a(3) = 5 as a(2) = 2, and the smallest unused number coprime to 2 that does not equal 2+1=3 is 5.
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Scott R. Shannon, Apr 29 2022
STATUS
approved