OFFSET
0,3
LINKS
Amiram Eldar, Table of n, a(n) for n = 0..90
FORMULA
a(n) <= A000041(n).
EXAMPLE
For n = 2, the numbers k with Omega(k) = 2 are either of the form p^2 with p prime, or of the form p1*p2 with p1 and p2 being distinct primes. The corresponding numbers of divisors are 3 and 4, respectively. Since there are 2 possible values, a(2) = 2.
For n = 8, there are 22 prime signatures of numbers k with Omega(k) = 8, corresponding to the number of partitions of 8. However, the prime signatures p1^5 * p2 * p3 * p4 and p1^3 * p2^3 * p3^2 both correspond to the same number of divisors, 48. Therefore, there are only 21 distinct possible values of the number of divisors, and a(8) = 21.
MATHEMATICA
a[n_] := Length @ Union[Times @@ (# + 1) & /@ IntegerPartitions[n]]; Array[a, 50, 0]
PROG
(PARI) a(n) = { my (m=Map()); forpart(p=n, mapput(m, prod(k=1, #p, 1+p[k]), 0)); #m } \\ Rémy Sigrist, Jun 17 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Amiram Eldar, Jun 16 2022
STATUS
approved