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

%I #23 Jun 24 2022 17:32:04

%S 1,2,4,9,3,5,6,16,25,7,8,36,64,49,10,100,121,11,12,81,13,14,144,625,

%T 15,17,18,729,19,20,169,21,22,196,225,23,24,1024,256,289,26,324,1296,

%U 2401,27,29,28,361,30,4096,400,441,31,32,484,529,33,34,576,5184

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

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

%C 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.

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

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

%H Rémy Sigrist, <a href="/A354903/b354903.txt">Table of n, a(n) for n = 1..1237</a>

%H Rémy Sigrist, <a href="/A354903/a354903.txt">C program</a>

%e 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.

%o (Python)

%o from math import gcd

%o from sympy import divisor_count

%o from itertools import count, islice

%o def agen(): # generator of terms

%o aset, k, mink = {1}, 1, 2; yield 1

%o for n in count(2):

%o an, k = k, mink

%o while k in aset or not gcd(an, divisor_count(k)) == 1: k += 1

%o aset.add(k); yield k

%o while mink in aset: mink += 1

%o print(list(islice(agen(), 60))) # _Michael S. Branicky_, Jun 11 2022

%o (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

%o (C) See Links section.

%Y Cf. A000005, A005179, A000290, A350150.

%K nonn

%O 1,2

%A _David James Sycamore_, Jun 11 2022

%E a(15) and beyond from _Michael S. Branicky_, Jun 11 2022