cp's OEIS Frontend

A362965 Number of primes <= the n-th prime power.

%I A362965 #34 Nov 02 2024 09:11:26
%S A362965 1,2,2,3,4,4,4,5,6,6,7,8,9,9,9,10,11,11,12,13,14,15,15,16,17,18,18,19,
%T A362965 20,21,22,22,23,24,25,26,27,28,29,30,30,30,31,31,32,33,34,35,36,37,38,
%U A362965 39,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,53,54,54,55,56,57,58,59,60
%N A362965 Number of primes <= the n-th prime power.
%C A362965 Also, number of distinct primes among the first n prime powers (cf. A246655).
%H A362965 Paolo Xausa, <a href="/A362965/b362965.txt">Table of n, a(n) for n = 1..10000</a>
%F A362965 a(n) = A000720(A246655(n)).
%e A362965 The 4th prime, 7, is followed by prime powers 8 and 9 before the next prime (11), accounting for three consecutive 4s in the sequence (at indices n = 5..7). Similarly, the three 9s (at n = 13..15) show that the 9th prime (23) is followed by two prime powers (25, 27) before the next prime (29). This occurs again at n = 40..42 (a(n) = 30), 358..360 (a(n) = 327) and 3588..3590 (a(n) = 3512). - _M. F. Hasler_, Oct 31 2024
%t A362965 A362965list[upto_]:=PrimePi[Select[Range[upto],PrimePowerQ]];A362965list[500] (* _Paolo Xausa_, Jun 29 2023 *)
%o A362965 (PARI) apply(primepi, [p| p <- [1..300], isprimepower(p)]) \\ _Michel Marcus_, Jun 04 2023
%o A362965 (Python)
%o A362965 from sympy import primepi, integer_nthroot
%o A362965 def A362965(n):
%o A362965     def bisection(f,kmin=0,kmax=1):
%o A362965         while f(kmax) > kmax: kmax <<= 1
%o A362965         while kmax-kmin > 1:
%o A362965             kmid = kmax+kmin>>1
%o A362965             if f(kmid) <= kmid:
%o A362965                 kmax = kmid
%o A362965             else:
%o A362965                 kmin = kmid
%o A362965         return kmax
%o A362965     def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
%o A362965     return int(primepi(bisection(f,n,n))) # _Chai Wah Wu_, Oct 28 2024
%Y A362965 Cf. A000961, A000720, A246655, A366833 (run lengths).
%K A362965 nonn
%O A362965 1,2
%A A362965 _Max Alekseyev_, Jun 03 2023