cp's OEIS Frontend

A065515 Number of prime powers <= n.

%I A065515 #66 Feb 16 2025 08:32:45
%S A065515 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 A065515 16,17,17,18,19,19,19,19,19,20,20,20,20,21,21,22,22,22,22,23,23,24,24,
%U A065515 24,24,25,25,25,25,25,25,26,26,27,27,27,28,28,28,29,29,29,29,30,30,31
%N A065515 Number of prime powers <= n.
%C A065515 a(n) > pi(n) = A000720(n).
%C A065515 From _Chayim Lowen_, Aug 05 2015: (Start)
%C A065515 a(n) <= pi(n) + A069623(n).
%C A065515 Conjecture: a(n) >= pi(A069623(n)) + pi(n) + 1.
%C A065515 Each term m is repeated A057820(m) times. (End)
%D A065515 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier-North Holland, 1978, Chapter 4.
%H A065515 Reinhard Zumkeller, <a href="/A065515/b065515.txt">Table of n, a(n) for n = 1..10000</a>
%H A065515 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrimePower.html">Prime Power</a>
%F A065515 Partial sums of A010055. - _Reinhard Zumkeller_, Nov 22 2009
%F A065515 a(n) = 1 + Sum_{k=1..log_2(n)} pi(floor(n^(1/k))). - _Chayim Lowen_, Aug 05 2015
%F A065515 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 A065515 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 A065515 N:= 100: # to get a(1) to a(N)
%p A065515 L:= Vector(N):
%p A065515 L[1]:= 1:
%p A065515 p:= 1:
%p A065515 while p < N do
%p A065515   p:= nextprime(p);
%p A065515   for k from 1 to floor(log[p](N)) do
%p A065515     L[p^k] := 1;
%p A065515   od
%p A065515 od:
%p A065515 ListTools:-PartialSums(convert(L,list)); # _Robert Israel_, May 03 2015
%t A065515 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 A065515 Accumulate[Table[If[Length[FactorInteger[n]]==1,1,0],{n,80}]] (* _Harvey P. Dale_, Aug 06 2016 *)
%t A065515 Accumulate[Table[If[PrimePowerQ[n],1,0],{n,120}]]+1 (* _Harvey P. Dale_, Sep 29 2016 *)
%o A065515 (Haskell)
%o A065515 a065515 n = length $ takeWhile (<= n) a000961_list
%o A065515 -- _Reinhard Zumkeller_, Apr 25 2011
%o A065515 (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 A065515 (Python)
%o A065515 from sympy import primepi
%o A065515 from sympy.ntheory.primetest import integer_nthroot
%o A065515 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 A065515 Cf. A000040, A000961, A000720, A276781 (ordinal transform).
%Y A065515 A025528(n) = a(n) - 1.
%Y A065515 Cf. A139555. - _Reinhard Zumkeller_, Oct 27 2010
%K A065515 nice,nonn
%O A065515 1,2
%A A065515 _Reinhard Zumkeller_, Nov 27 2001