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,2

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.

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.

Example

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.

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

Prog

(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

Crossrefs

Cf. A381115-A381120, A379810.

A381167 is a different but closely related sequence.

Sequence in context: A143345 A111679 A349872 * A381167 A087174 A071963

Adjacent sequences: A381016 A381017 A381018 * A381020 A381021 A381022

Keyword

nonn,look

Author

Ali Sada and Allan C. Wechsler, Feb 12 2025

Extensions

More terms from Michael S. Branicky, Feb 13 2025

Status

approved