login
Number of prime powers <= n.
23

%I #65 Jul 23 2024 09:00:31

%S 1,2,3,4,5,5,6,7,8,8,9,9,10,10,10,11,12,12,13,13,13,13,14,14,15,15,16,

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

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

%N Number of prime powers <= n.

%C a(n) > pi(n) = A000720(n).

%C From _Chayim Lowen_, Aug 05 2015: (Start)

%C a(n) <= pi(n) + A069623(n).

%C Conjecture: a(n) >= pi(A069623(n)) + pi(n) + 1.

%C Each term m is repeated A057820(m) times. (End)

%D F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, Chapter 4.

%H Reinhard Zumkeller, <a href="/A065515/b065515.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimePower.html">Prime Power</a>

%F Partial sums of A010055. - _Reinhard Zumkeller_, Nov 22 2009

%F a(n) = 1 + Sum_{k=1..log_2(n)} pi(floor(n^(1/k))). - _Chayim Lowen_, Aug 05 2015

%F a(n) = 1 + Sum_{k=2..n} floor(2*A001222(k)/(tau(k^2)-1)) where tau is A000005(n). - _Anthony Browne_, May 17 2016

%e There are 9 prime powers <= 12: 1=2^0, 2, 3, 4=2^2, 5, 7, 8=2^3, 9=3^2 and 11, so a(12) = 9.

%p N:= 100: # to get a(1) to a(N)

%p L:= Vector(N):

%p L[1]:= 1:

%p p:= 1:

%p while p < N do

%p p:= nextprime(p);

%p for k from 1 to floor(log[p](N)) do

%p L[p^k] := 1;

%p od

%p od:

%p ListTools:-PartialSums(convert(L,list)); # _Robert Israel_, May 03 2015

%t a[n_] := 1 + Count[ Range[2, n], p_ /; Length[ FactorInteger[p]] == 1]; Table[a[n], {n, 1, 73}] (* _Jean-François Alcover_, Oct 12 2011 *)

%t Accumulate[Table[If[Length[FactorInteger[n]]==1,1,0],{n,80}]] (* _Harvey P. Dale_, Aug 06 2016 *)

%t Accumulate[Table[If[PrimePowerQ[n],1,0],{n,120}]]+1 (* _Harvey P. Dale_, Sep 29 2016 *)

%o (Haskell)

%o a065515 n = length $ takeWhile (<= n) a000961_list

%o -- _Reinhard Zumkeller_, Apr 25 2011

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

%o (Python)

%o from sympy import primepi

%o from sympy.ntheory.primetest import integer_nthroot

%o def A065515(n): return 1+sum(primepi(integer_nthroot(n,k)[0]) for k in range(1,n.bit_length())) # _Chai Wah Wu_, Jul 23 2024

%Y Cf. A000040, A000961, A000720, A276781 (ordinal transform).

%Y A025528(n) = a(n) - 1.

%Y Cf. A139555. - _Reinhard Zumkeller_, Oct 27 2010

%K nice,nonn

%O 1,2

%A _Reinhard Zumkeller_, Nov 27 2001