A387759 Lexicographically earliest infinite sequence of distinct positive numbers such that, for n > 2, a(n) shares a factor with a(n-1) and is coprime to a(n-2) if a(n-1) < a(n-2), else it is coprime to a(n-1) and shares a factor with a(n-2) if a(n-1) > a(n-2).. Start with a(1) = 1, a(2) = 4, a(3) = 9.

1, 4, 9, 10, 21, 20, 22, 15, 25, 6, 8, 27, 14, 16, 35, 12, 26, 33, 28, 32, 49, 18, 34, 39, 38, 40, 57, 44, 46, 55, 24, 51, 50, 52, 45, 63, 65, 36, 56, 69, 58, 62, 87, 68, 70, 153, 74, 76, 111, 80, 82, 75, 81, 85, 42, 48, 77, 30, 54, 95, 66, 72, 121, 60, 64

Offset

1,2

Comments

The sequence uses the selection rules for a(n) of either A098550 or A336957 if a(n-1) is greater than or less than a(n-2) respectively. To ensure the sequence is infinite, if a(n-1) is less than a(n-2) then, if a(n) is less than a(n-1) it must contain a prime factor not in a(n-1), else if a(n) is more than a(n-1) then a(n-1) must contain a prime factor not in a(n).

Similar to A336957, no term can be a prime. If it were, then if it was less than a(n-1), a(n+1) would have to be a multiple of the prime, hence larger, but then a(n+2) would not exist. If it was more than a(n-1), then it is coprime to a(n-1) which implies it must share a factor with a(n-2), which means a(n-2) is larger than a(n-1) also. But that is not possible as that would have forced the prime to share a factor with a(n-1), which it does not.

Unlike A336957, however, prime powers can be terms since they can be larger than the preceding term, hence the selection rules of A098550 are then used for a(n+1) which are not affected by the prime factors of the terms. Prime powers smaller than the preceding term are not found as they would either lead to the next term not existing, or, if such a term did exist, it would be smaller than the prime power and would have been chosen instead of it.

Of the terms studied there are no fixed points other than the first, and it is likely none exist. The sequence is conjectured to contain all positive integers other than the primes.

Links

Scott R. Shannon, Table of n, a(n) for n = 1..10000

Scott R. Shannon, Image of the first 100000 terms. The colors are graduated across the spectrum to show the total number of prime factors of each term, with orange being two prime factors. The thin green line is a(n) = n.

Example

a(6) = 20 as a(5) = 21 > a(4) = 10, and 20 is an unused number and shares a factor with 10 while being coprime to 21. Note that 8, which is less than 21, also has these properties, but choosing 8 would halt the sequence as there are no terms for a(7) that are less than 8 that share a factor with it but not 21, while those larger than 8 would have to be a multiple of 2, which means a(8) would not exist.
a(11) = 8 as a(10) = 6 < a(9) = 25, and 8 is an unused number and shares a factor with 6 while being coprime to 25. Note that, as 8 is larger than 6 and 6 contains a prime factor not in 8, choosing 8 does not halt the sequence.

Crossrefs

Cf. A387758, A387682, A336957, A098550, A387231.

Sequence in context: A245096 A352097 A354853 * A119718 A263648 A051884

Adjacent sequences: A387756 A387757 A387758 * A387760 A387761 A387762

Keyword

nonn

Author

Scott R. Shannon, Sep 07 2025

Status

approved