%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