A358820 a(n) is the least novel k such that d(k)|n, where d is the divisor counting function A000005.

1, 2, 4, 3, 16, 5, 64, 6, 9, 7, 1024, 8, 4096, 11, 25, 10, 65536, 12, 262144, 13, 49, 17, 4194304, 14, 81, 19, 36, 15, 268435456, 18, 1073741824, 21, 121, 23, 625, 20, 68719476736, 29, 169, 22, 1099511627776, 28, 4398046511104, 26, 100, 31, 70368744177664, 24

Offset

1,2

Comments

In other words, a(n) = Min{k_j; 1 <= j <= d(n), such that d(k_j) = m_j}, where m_j|n, and k_j has not appeared earlier.

a(n) is composite iff n is odd, and prime p (the least that has not occurred earlier) iff 2|n, and if for any other m|n, and k such that d(k) = m; k > p.

The primes appear in natural order, and records > 1 are 2^(prime(k)-1); k = 1,2,...

Conjectured to be a permutation of the positive integers.

For each n, there is some k <= n such that a(k*d(n)) = n, so (1) a((log 2 + o(1))*n log n/log log n) > n by Wigert's theorem and (2) this sequence is a permutation of the positive integers. - Charles R Greathouse IV, Dec 03 2022

Links

Michael De Vlieger, Table of n, a(n) for n = 1..1024

Michael De Vlieger, Log log scatterplot of Log_10(a(n)), n = 1..256.

Index entries for sequences that are permutations of the natural numbers

Formula

a(prime(k)) = 2^(prime(k) - 1) (see A061286).

n log log n/log n << a(n) <= 2^(n-1), see comments. - Charles R Greathouse IV, Dec 03 2022

Example

a(1)=1 since d(1)=1 and 1 has no other divisors.
a(2)=2 since 2 is the smallest number having just 2 divisors.
a(5)=16 since 5 is prime and 16 is the smallest number having 5 divisors.
a(15)=25 since 15 has divisors 25 is the least novel number having 3 divisors, 81 is the least having 5 divisors and 144 is the least having 15 divisors.

Mathematica

kk = 2^32; nn = 60; c[_] = False; s = Union[Flatten@ Monitor[Table[a^2*b^3, {b, kk^(1/3)}, {a, Sqrt[kk/b^3]}], b]]^2; u = 1; v = 1; w = 1; Do[Which[PrimeQ[n], k = 2^(n - 1), CoprimeQ[n, 6], k = w; While[Nand[! c[#], Divisible[n, DivisorSigma[0, #]]] &[s[[k]]], k++]; If[k == w, While[c[s[[k]]], w++]]; k = s[[k]], OddQ[n], k = v; While[Nand[! c[#], Divisible[n, DivisorSigma[0, #]]] &[k^2], k++]; If[k == v, While[c[v^2], v++]]; k *= k, True, k = u; While[Nand[! c[k], Divisible[n, DivisorSigma[0, k]]], k++]]; Set[{a[n], c[k]}, {k, True}]; If[k == u, While[c[u], u++]], {n, nn}]; Array[a, nn] (* Michael De Vlieger, Dec 03 2022 *)

Prog

(Python)
from functools import lru_cache
from itertools import count, islice
from sympy import divisor_count, isprime
@lru_cache(maxsize=None)
def d(n): return divisor_count(n)
def agen():
    mink, seen = 1, set()
    for n in count(1):
        k = mink if not isprime(n) else 2**(n-1)
        dk = d(k)
        while k in seen or n%dk != 0: k += 1; dk = d(k)
        while mink in seen: mink += 1
        yield k
        seen.add(k)
print(list(islice(agen(), 22))) # Michael S. Branicky, Dec 02 2022

Crossrefs

Cf. A000005, A005179, A061286, A128555 (inverse).

Sequence in context: A271363 A115399 A109429 * A366027 A114894 A183169

Adjacent sequences: A358817 A358818 A358819 * A358821 A358822 A358823

Keyword

nonn

Author

David James Sycamore, Dec 02 2022

Extensions

a(26) and beyond from Michael S. Branicky, Dec 02 2022

a(24) corrected by Michael De Vlieger, Dec 05 2022

Status

approved