login
A358820
a(n) is the least novel k such that d(k)|n, where d is the divisor counting function A000005.
4
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
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
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(26) and beyond from Michael S. Branicky, Dec 02 2022
a(24) corrected by Michael De Vlieger, Dec 05 2022
STATUS
approved