A377078 Lexicographically earliest infinite sequence of distinct positive integers such that, for n > 2, a(n) shares a factor with a(n-2) mod a(n-1).

2, 3, 4, 6, 8, 9, 10, 12, 5, 14, 15, 16, 18, 20, 21, 22, 24, 11, 26, 33, 13, 7, 27, 28, 30, 32, 25, 35, 40, 42, 34, 36, 17, 38, 51, 19, 39, 57, 45, 46, 48, 23, 44, 69, 50, 76, 52, 54, 56, 58, 49, 60, 63, 55, 62, 65, 31, 66, 93, 64, 29, 68, 87, 70, 85, 72, 78, 74, 80, 37, 75, 111, 81, 82, 84, 41, 86, 123, 43, 148, 129, 95, 88, 77, 99, 91, 92, 98, 90, 94

Offset: 1

Author

Scott R. Shannon, Oct 15 2024

Keywords

• nonn

Comments

To ensure the sequence is infinite a(n) must be chosen so that a(n-1) mod a(n) is not 0 or 1. In the first 100000 terms the fixed points are 119, 205, 287, and it is likely no more exist. It is conjectured all numbers > 1 appear in the sequence.

Examples

			a(4) = 6 as a(2) mod a(3) = 3 mod 4 = 3, and 6 is the earliest unused number that shares a factor with 3.
a(12) = 16 as a(10) mod a(11) = 14 mod 15 = 14, and 16 shares a factor with 14. Note that 7 is unused and shares a factor with 14 but a(11) mod 7 = 1, so choosing a(12) = 7 would mean a(13) would not exist.
		

Links

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

Crossrefs

Cf. A064413, A359557, A270139, A027749.

Programs

Mathematica

a[1] = 2; a[2] = 3; hs = {a[1], a[2]}; pool = Range[4, 1000];
a[n_] := a[n] = Module[{m, pos}, pool = Complement[pool, hs];m = Mod[a[n - 2], a[n - 1]]; pos = FirstPosition[pool, _?(Mod[a[n - 1], #] > 1 && GCD[#, m] > 1 &)][[1]]; AppendTo[hs, pool[[pos]]]; pool[[pos]]]
Array[a, 90, 1] (* Shenghui Yang, Oct 16 2024*)

Python

from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    an2, an1, aset, m = 2, 3, {2, 3}, 4
    yield from [2, 3]
    while True:
        t = an2%an1
        an = next(k for k in count(m) if k not in aset and an1%k > 1 and gcd(k, t) > 1)
        yield an
        aset.add(an)
        while m in aset: m += 1
        an2, an1 = an1, an
print(list(islice(agen(), 90))) # Michael S. Branicky, Oct 15 2024