A377078 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

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.

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.

EXAMPLE

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.

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*)

PROG

(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