cp's OEIS Frontend

A381019 a(n) is the smallest positive integer not yet in the sequence such that a(n) is relatively prime to a(n-i) for all 1 <= i <= min(a(n), n-1).

%I A381019 #85 Apr 07 2025 00:47:41
%S A381019 1,2,3,5,7,11,4,13,17,19,23,29,9,31,37,8,41,43,47,53,59,61,6,67,71,73,
%T A381019 79,83,89,25,97,101,103,107,109,12,113,127,131,137,139,149,151,157,
%U A381019 163,167,10,173,179,181,191,193,197,199,49,211,223,227,229,233
%N A381019 a(n) is the smallest positive integer not yet in the sequence such that a(n) is relatively prime to a(n-i) for all 1 <= i <= min(a(n), n-1).
%C A381019 Theorem (_Russ Cox_, Feb 14-16, 2025): Every positive number will eventually appear. For proof see link.
%C A381019 _Jinyuan Wang_ (Feb 16, 2025) has informed us that he also proved that every number appears.
%H A381019 Michael S. Branicky, <a href="/A381019/b381019.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1500 from Michael De Vlieger)
%H A381019 Michael S. Branicky, <a href="/A381019/a381019.py.txt">Python program</a>
%H A381019 Russ Cox, <a href="/A381019/a381019_1.txt">Proof that every number appears</a>
%H A381019 Michael De Vlieger, <a href="/A381019/a381019.png">Annotated log log scatterplot of a(n)</a>, n = 1..20000, showing primes in red, proper prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue and purple, where purple represents powerful numbers that are not prime powers. Composite terms are enlarged for visibility.
%e A381019 After a(2)=2, the next term that shares a common factor with 2 is a(7)=4, which is permitted since the difference 7-2 = 5 is greater than 4.
%p A381019 N:= 1000: # for terms before the first term > N
%p A381019 Cands:= [$2..N]: R:= [1]: x:= 1:
%p A381019 for n from 2 do
%p A381019   found:= false;
%p A381019   for j from 1 to N - n do
%p A381019     if andmap(t -> igcd(t, Cands[j]) = 1, [seq(R[n-i],i=1 .. min(Cands[j],n-1))]) then
%p A381019       found:= true; x:= Cands[j]; R:= [op(R),x]; Cands:= subsop(j=NULL,Cands); break
%p A381019     fi od:
%p A381019   if not found then break fi
%p A381019 od:
%p A381019 R; # _Robert Israel_, Feb 14 2025
%t A381019 nn = 120; c[_] = False; u = v = 2; a[1] = 1;
%t A381019 Do[k = u;
%t A381019   While[Or[c[k],
%t A381019     ! CoprimeQ[k, Product[a[h], {h, n - Min[k, n - 1], n - 1}] ] ],
%t A381019     If[k > n - 1, k = v, k++]];
%t A381019   Set[{a[n], c[k]}, {k, True}];
%t A381019   If[k == u, While[c[u], u++]];
%t A381019   If[k == v, While[Or[c[v], CompositeQ[v]], v++]], {n, 2, nn}];
%t A381019 Array[a, nn] (* _Michael De Vlieger_, Feb 14 2025 *)
%o A381019 (Python) # see link for faster version
%o A381019 from math import gcd
%o A381019 from itertools import count, islice
%o A381019 def agen(): # generator of terms
%o A381019     alst, aset, an, m = [1], {1}, 1, 2
%o A381019     for n in count(2):
%o A381019         yield an
%o A381019         an = next(k for k in count(m) if k not in aset and all(gcd(alst[-j], k) == 1 for j in range(1, min(k, n-1)+1)))
%o A381019         alst.append(an)
%o A381019         aset.add(an)
%o A381019         while m in aset: m += 1
%o A381019 print(list(islice(agen(), 61))) # _Michael S. Branicky_, Feb 13 2025
%Y A381019 Cf. A381115-A381120, A379810.
%Y A381019 A381167 is a different but closely related sequence.
%K A381019 nonn,look
%O A381019 1,2
%A A381019 _Ali Sada_ and _Allan C. Wechsler_, Feb 12 2025
%E A381019 More terms from _Michael S. Branicky_, Feb 13 2025