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

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, 79, 83, 89, 25, 97, 101, 103, 107, 109, 12, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 10, 173, 179, 181, 191, 193, 197, 199, 49, 211, 223, 227, 229, 233

Offset: 1

Author

Ali Sada and Allan C. Wechsler, Feb 12 2025

Keywords

• nonn
• look

Comments

Theorem (Russ Cox, Feb 14-16, 2025): Every positive number will eventually appear. For proof see link.

Jinyuan Wang (Feb 16, 2025) has informed us that he also proved that every number appears.

Examples

			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.
		

Links

• Michael S. Branicky, Table of n, a(n) for n = 1..10000 (terms 1..1500 from Michael De Vlieger)
• Michael S. Branicky, Python program
• Russ Cox, Proof that every number appears
• Michael De Vlieger, Annotated log log scatterplot of a(n), 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.

Crossrefs

Cf. A381115-A381120, A379810.

A381167 is a different but closely related sequence.

Programs

Maple

N:= 1000: # for terms before the first term > N
Cands:= [$2..N]: R:= [1]: x:= 1:
for n from 2 do
  found:= false;
  for j from 1 to N - n do
    if andmap(t -> igcd(t, Cands[j]) = 1, [seq(R[n-i],i=1 .. min(Cands[j],n-1))]) then
      found:= true; x:= Cands[j]; R:= [op(R),x]; Cands:= subsop(j=NULL,Cands); break
    fi od:
  if not found then break fi
od:
R; # Robert Israel, Feb 14 2025

Mathematica

nn = 120; c[_] = False; u = v = 2; a[1] = 1;
Do[k = u;
  While[Or[c[k],
    ! CoprimeQ[k, Product[a[h], {h, n - Min[k, n - 1], n - 1}] ] ],
    If[k > n - 1, k = v, k++]];
  Set[{a[n], c[k]}, {k, True}];
  If[k == u, While[c[u], u++]];
  If[k == v, While[Or[c[v], CompositeQ[v]], v++]], {n, 2, nn}];
Array[a, nn] (* Michael De Vlieger, Feb 14 2025 *)

Python

# see link for faster version
from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    alst, aset, an, m = [1], {1}, 1, 2
    for n in count(2):
        yield an
        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)))
        alst.append(an)
        aset.add(an)
        while m in aset: m += 1
print(list(islice(agen(), 61))) # Michael S. Branicky, Feb 13 2025

Extensions

More terms from Michael S. Branicky, Feb 13 2025