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

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.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..1237

Rémy Sigrist, C program

Example

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.

Prog

(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
(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
(C) See Links section.

Crossrefs

Cf. A000005, A005179, A000290, A350150.

Sequence in context: A133057 A155523 A019912 * A081344 A227272 A021405

Adjacent sequences: A354900 A354901 A354902 * A354904 A354905 A354906

Keyword

nonn

Author

David James Sycamore, Jun 11 2022

Extensions

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

Status

approved