A025528 Number of prime powers <= n with exponents > 0 (A246655).

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

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

a(n) is the sum of the exponents in the prime factorization of lcm{1,2,...,n}.

Larger than but analogous to Pi(n).

Counts A000961 without 1=prime^0: a(n)=A065515(n)-1. - Reinhard Zumkeller, Jul 03 2003

Equally, number of finite fields of order <= n. - Neven Juric, Feb 05 2010

Examples

			Below 100 there are 25 primes and 25 + 10 = 35 prime powers.
		

References

• G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, p. 203, Publications de l'Institut Cartan, 1990.

Links

• Daniel Forgues, Table of n, a(n) for n = 1..100000.
• Index entries for sequences related to lcm's

Crossrefs

Cf. A000961, A000040, A000720, A001221, A003418, A141228, A246655, A276781 (ordinal transform).

One less than A065515.

Programs

Mathematica

primePowerPi[n_] := Sum[PrimePi[n^(1/k)], {k, Log[2, n]}]; Table[primePowerPi[n], {n, 75}] (* Geoffrey Critzer, Jan 07 2012 *) (* and modified by Robert G. Wilson v, Jan 07 2012 *)
Table[Sum[Boole[1 < Cyclotomic[n, 1]], {n, 1, m}], {m, 1, 75}] (* Fred Daniel Kline, Oct 03 2016 *)

PARI

for(n=1,100,print1(sum(k=1,n,logint(n,prime(k))),",")) \\ corrected by Luc Rousseau, Jan 04 2018

PARI

a(n)=sum(i=1,n,if(omega(i)-1,0,1))

PARI

a(n)=n+=.5;sum(e=1,log(n)\log(2),primepi(n^(1/e))) \\ Charles R Greathouse IV, Apr 30 2012

Python

from sympy import primepi, integer_nthroot
def A025528(n): return sum(primepi(integer_nthroot(n,k)[0]) for k in range(1,n.bit_length())) # Chai Wah Wu, Aug 15 2024

SageMath

def A025528(n) : return sum([1 for k in (0..n) if is_prime_power(k)])
print([A025528(n)  for n in (1..74)]) # Peter Luschny, Nov 18 2019

Formula

a(n) = Cardinality[{1..n}|A001221(i)=1].

a(n) = Sum_{p prime <= n} floor(log(n)/log(p)). - Benoit Cloitre, Apr 30 2002

a(n) ~ n/log(n). - Benoit Cloitre, May 30 2003

a(n) = A069637(n) + A000720(n). - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Feb 24 2004 [Corrected by Franklin T. Adams-Watters, Jun 08 2008]

a(n) = A000720(n) + A000720(floor(n^(1/2))) + A000720(floor(n^(1/3))) + ... - Max Alekseyev, May 11 2009

Partial sums of A069513. - Enrique Pérez Herrero, May 30 2011

a(n) = A001222(A003418(n)). - Luc Rousseau, Jan 05 2018

From Steven Foster Clark, Sep 26 2018: (Start)

a(n) = Sum_{m=1..n} A001222(m) * A002321(floor(n/m)) where A001222() is the Omega function and A002321() is the Mertens function.

a(n) = Sum_{m=1..floor(log_2(n))} A000010(m)/m * J(floor(n^(1/m))) where A000010() is Euler's totient function and J(n) = Sum_{m=1..floor(log_2(n))} 1/m * A000720(floor(n^(1/m))) is Riemann's prime-power counting function.

(End)

Extensions

New description from Labos Elemer, Nov 09 2000