A390375 a(n) is the number of positive integers with n divisors and no prime divisor greater than n.

1, 1, 2, 3, 3, 9, 4, 20, 10, 16, 5, 75, 6, 36, 36, 126, 7, 196, 8, 288, 64, 64, 9, 1485, 45, 81, 165, 405, 10, 1000, 11, 3003, 121, 121, 121, 4356, 12, 144, 144, 4368, 13, 2197, 14, 1470, 1470, 196, 15, 45900, 120, 1800, 225, 1800, 16, 13056, 256, 13056, 256, 256

Offset

1,3

Comments

a(n) is the number of positive integers k with A000005(k) = n and A006530(k) <= n.

By the divisor function and the fundamental theorem of arithmetic, the triangle T(n,k) in A251683 gives the number of positive integers with n divisors and k given prime factors; since these k primes can be chosen from those <= n, in the formula section T(n,k) is weighted by binomial(pi(n), k).

This sequence extends the prime counting function to all integers. On a prime p, a(p) matches pi(p) (the number of primes up to p). For prime-indexed primes (A006450), the values are themselves prime; in fact a(p)=k when p is the k-th prime. Proofs see formula section.

Links

Felix Huber, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Divisor Function

Eric Weisstein's World of Mathematics, Fundamental Theorem of Arithmetic

Formula

a(n) = Sum_{k=1..A086436(n)} T(n,k)*binomial(A000720(n), k), where T(n,k) is the triangle in A251683.

a(p) = A000720(p) for primes p. Proof: A086436(p) = 1 and T(p,1) = 1 for primes p, so a(n) = 1*binomial(A000720(p), 1) = A000720(p). Equivalently, A390375(A000040(k)) = k for positive integers k.

a(p) is prime iff a prime p is in A006450. Proof: By the definition of A006450, a prime p belongs to A006450 iff pi(p) is prime. Therefore a(p) is prime <=> pi(p) is prime <=> p is in A006450.

Example

a(6) = 9 because 12, 18, 20, 32, 45, 50, 75, 243 and 3125 are the only 9 positive integers with 6 divisors and no prime divisor greater than 6.
a(13) = 6 because 13 is the sixth prime number.

Maple

# b and t by Alois P. Heinz (A251683)
with(numtheory):
b:=proc(n) option remember;
    expand(x*(1+add(b(n/d), d=divisors(n) minus {1, n})))
end:
t:=n->(p->[seq(coeff(p, x, i), i=1..degree(p))])(b(n)):
A390375:=proc(n)
    T:=t(n);
    return max(1, add(T[k]*binomial(pi(n), k), k=1..nops(T)));
end proc:
seq(A390375(n), n=1..58);

Mathematica

b[n_]:=x(1+Sum[b[n/d], {d, Divisors[n]~Complement~{1, n}}]); T[n_]:=CoefficientList[b[n]/x, x];
a[n_]:=If[n>1, Sum[T[n][[k]]*Binomial[PrimePi[n], k], {k, 1, PrimeOmega[n]}], 1]; Array[a, 58] (* James C. McMahon, Nov 08 2025 *)

Prog

(Python)
from sympy.functions.combinatorial.numbers import primepi
def A390375(n: int) -> int:
    ordfact = A251683_row(n)
    return max(1, sum(f * binomial(primepi(n), k + 1) for k, f in enumerate(ordfact)))
print([A390375(n) for n in range(1, 59)])  # Peter Luschny, Nov 06 2025

Crossrefs

Cf. A000005, A000720, A005179, A006450, A006530, A007318, A027750, A074206, A086436, A251683, A377505, A377537.

Sequence in context: A059083 A207626 A232324 * A124931 A210226 A209163

Adjacent sequences: A390372 A390373 A390374 * A390376 A390377 A390378

Keyword

nonn,easy

Author

Felix Huber, Nov 05 2025

Status

approved