A383069 Lexicographically earliest sequence of distinct positive integers such that a(a(n)) shares a factor with a(a(n-1)).

2, 3, 6, 1, 7, 8, 10, 5, 11, 35, 14, 9, 15, 22, 33, 12, 13, 16, 18, 19, 21, 24, 17, 39, 20, 27, 38, 23, 30, 34, 25, 29, 36, 26, 40, 42, 28, 68, 247, 45, 31, 69, 32, 46, 50, 58, 37, 43, 44, 52, 41, 62, 47, 55, 74, 48, 59, 54, 215, 49, 56, 1147, 51, 65, 82, 53, 70, 92, 145, 94, 57, 73, 118

Offset: 1

Author

Scott R. Shannon, Apr 15 2025

Keywords

• nonn

Comments

The majority of the terms are concentrated along a line a(n) ~ 0.91*n, although sparser lines of concentration also exist. Almost all terms are less than 2*n, although there are large outliers that equal the product of two large primes and are much larger than this range.

It is likely 4 is the only positive integer not to appear. Interestingly if we force the sequence to be composed of only terms greater than 1, the only term that differs is a(4), which becomes 4 instead of 1, with all other terms remaining the same.

In the first 10000 terms the only fixed points are 21 and 104. It is unknown if more exist.

Examples

			a(1) = 2. The first term cannot be 1 as that would force a(2) to share a factor with a(a(1)) = 1, so the next smallest unused number, 2, is chosen.
a(2) = 3. The second term cannot be 1 as that would force a(a(2)) = a(1) = 1 to share a factor with a(a(1)) = a(1) = 2, so the next smallest unused number, 3, is chosen. This now forces a(a(2)) = a(3) to share a factor with a(a(1)) = a(2) = 3.
a(3) = 6. This is the smallest unused number that is a multiple of 3, which was forced by the previous a(1) = 2 and a(2) = 3.
a(4) = 1. As this term has not been previous referenced, 1 can be chosen. Note this eliminates 4 as a possible term for the remainder of the sequence as a(4) cannot share a factor with any other number. Note that as a(a(4)) = a(1) = 2, a(5) must be an index to an even number.
a(5) = 7. As previously noted, no term can be 4, and a(5) must be an index to an even number, so it cannot be 5 itself. The number 6 has been used, so that leaves 7 as the smallest possible choice. Note this now forces a(7) to share a factor with a(a(4)) = a(1) = 2.
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..10000
• Scott R. Shannon, Image of the first 10000 terms for a(n) <= 20000. The green line is a(n) = n.

Crossrefs

Cf. A378098, A064413, A378116, A378030.