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

%I #88 Aug 16 2024 08:37:06

%S 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,

%T 16,16,17,18,18,18,18,18,19,19,19,19,20,20,21,21,21,21,22,22,23,23,23,

%U 23,24,24,24,24,24,24,25,25,26,26,26,27,27,27,28,28,28,28,29,29,30,30

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

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

%C Larger than but analogous to Pi(n).

%C Counts A000961 without 1=prime^0: a(n)=A065515(n)-1. - _Reinhard Zumkeller_, Jul 03 2003

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

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

%H Daniel Forgues, <a href="/A025528/b025528.txt">Table of n, a(n) for n = 1..100000</a>.

%H <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>

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

%F a(n) = Sum_{p prime <= n} floor(log(n)/log(p)). - _Benoit Cloitre_, Apr 30 2002

%F a(n) ~ n/log(n). - _Benoit Cloitre_, May 30 2003

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

%F a(n) = A000720(n) + A000720(floor(n^(1/2))) + A000720(floor(n^(1/3))) + ... - _Max Alekseyev_, May 11 2009

%F Partial sums of A069513. - _Enrique Pérez Herrero_, May 30 2011

%F a(n) = A001222(A003418(n)). - _Luc Rousseau_, Jan 05 2018

%F From _Steven Foster Clark_, Sep 26 2018: (Start)

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

%F 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.

%F (End)

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

%t 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 *)

%t Table[Sum[Boole[1 < Cyclotomic[n, 1]], {n, 1, m}], {m, 1, 75}] (* _Fred Daniel Kline_, Oct 03 2016 *)

%o (PARI) for(n=1,100,print1(sum(k=1,n,logint(n,prime(k))),",")) \\ corrected by _Luc Rousseau_, Jan 04 2018

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

%o (PARI) a(n)=n+=.5;sum(e=1,log(n)\log(2),primepi(n^(1/e))) \\ _Charles R Greathouse IV_, Apr 30 2012

%o (SageMath)

%o def A025528(n) : return sum([1 for k in (0..n) if is_prime_power(k)])

%o print([A025528(n) for n in (1..74)]) # _Peter Luschny_, Nov 18 2019

%o (Python)

%o from sympy import primepi, integer_nthroot

%o 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

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

%Y One less than A065515.

%K nonn

%O 1,3

%A _Clark Kimberling_

%E New description from _Labos Elemer_, Nov 09 2000