A203967 The number of positive integers <= n that have a prime number of divisors.

0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 8, 9, 10, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25

Offset: 1

Author

Geoffrey Critzer, Jan 08 2012

Keywords

• nonn

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A009087, A010051, A010055, A100995.

Programs

Haskell

a203967 n = length $ takeWhile (<= n) a009087_list
-- Reinhard Zumkeller, Jun 06 2013

Mathematica

Table[Total[Table[PrimePi[m^(1/n)], {n,Table[Prime[n]-1, {n,1,20}]}]], {m,1,100}]
tot = 0; Table[If[PrimeQ[DivisorSigma[0, n]], tot++]; tot, {n, 100}] (* T. D. Noe, Jan 10 2012 *)

Python

from sympy import primepi, integer_nthroot, primerange
def A203967(n): return int(sum(primepi(integer_nthroot(n,k-1)[0]) for k in primerange(n.bit_length()+1))) # Chai Wah Wu, Feb 22 2025

Formula

a(n) = a(n-1) + A010055(n) * A010051(A100995(n)+1). - Reinhard Zumkeller, Jun 06 2013