A354903 Lexicographically earliest infinite sequence of distinct positive integers such that the number of divisors of a(n+1) is prime to a(n).

1, 2, 4, 9, 3, 5, 6, 16, 25, 7, 8, 36, 64, 49, 10, 100, 121, 11, 12, 81, 13, 14, 144, 625, 15, 17, 18, 729, 19, 20, 169, 21, 22, 196, 225, 23, 24, 1024, 256, 289, 26, 324, 1296, 2401, 27, 29, 28, 361, 30, 4096, 400, 441, 31, 32, 484, 529, 33, 34, 576, 5184

Offset: 1

Author

David James Sycamore, Jun 11 2022

Keywords

• nonn

Comments

1,2 are the earliest consecutive pair of numbers satisfying the definition, therefore the sequence begins with a(1)=1, a(2)=2.

The sequence is infinite since there is always a number k prime to a(n), and the smallest number not yet used which has k divisors could be a(n+1), unless there is a smaller number with the same property.

All record terms are squares, though not in ascending order (64 occurs before 49, 100 before 81, etc.).

Conjectured to be a permutation of the positive integers in which primes appear in natural order.

Examples

			a(7)=6 and 16 is the smallest number which has not already occurred whose number of divisors (5) is prime to 6, therefore a(8)=16.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..16384 first 1237 terms from Rémy Sigrist.
• Michael De Vlieger, Mathematica code.
• Rémy Sigrist, C program

Crossrefs

Cf. A000005, A005179, A000290, A350150, A355269.

Programs

C

// See Links section.

PARI

lista(nn) = my(va = vector(nn)); va[1] = 1; for (n=2, nn, my(k=1); while ((gcd(va[n-1], numdiv(k)) != 1) || #select(x->(x==k), va), k++); va[n] = k;); va; \\ Michel Marcus, Jun 11 2022

Python

from math import gcd
from sympy import divisor_count
from itertools import count, islice
def agen(): # generator of terms
    aset, k, mink = {1}, 1, 2; yield 1
    for n in count(2):
        an, k = k, mink
        while k in aset or not gcd(an, divisor_count(k)) == 1: k += 1
        aset.add(k); yield k
        while mink in aset: mink += 1
print(list(islice(agen(), 60))) # Michael S. Branicky, Jun 11 2022

Extensions

a(15) and beyond from Michael S. Branicky, Jun 11 2022