login
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).
3

%I #17 Oct 19 2024 10:49:39

%S 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,

%T 32,25,35,40,42,34,36,17,38,51,19,39,57,45,46,48,23,44,69,50,76,52,54,

%U 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

%N 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).

%C 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.

%H Scott R. Shannon, <a href="/A377078/b377078.txt">Table of n, a(n) for n = 1..10000</a>

%H Scott R. Shannon, <a href="/A377078/a377078.png">Image of the first 100000 terms</a>. The green line is a(n) = n.

%e 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.

%e 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.

%t a[1] = 2; a[2] = 3; hs = {a[1], a[2]}; pool = Range[4, 1000];

%t 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]]]

%t Array[a, 90, 1] (* _Shenghui Yang_, Oct 16 2024*)

%o (Python)

%o from math import gcd

%o from itertools import count, islice

%o def agen(): # generator of terms

%o an2, an1, aset, m = 2, 3, {2, 3}, 4

%o yield from [2, 3]

%o while True:

%o t = an2%an1

%o an = next(k for k in count(m) if k not in aset and an1%k > 1 and gcd(k, t) > 1)

%o yield an

%o aset.add(an)

%o while m in aset: m += 1

%o an2, an1 = an1, an

%o print(list(islice(agen(), 90))) # _Michael S. Branicky_, Oct 15 2024

%Y Cf. A064413, A359557, A270139, A027749.

%K nonn

%O 1,1

%A _Scott R. Shannon_, Oct 15 2024