123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- #!/usr/bin/ruby
- # A nice algorithm in terms of the prime-counting function for counting the number of prime powers <= n, with exponents >= 1.
- # See also:
- # https://oeis.org/A025528
- # https://en.wikipedia.org/wiki/Prime-counting_function
- # https://trizenx.blogspot.com/2018/11/partial-sums-of-arithmetical-functions.html
- func prime_power_count(n) {
- sum(1..n.ilog2, {|k|
- prime_count(n.iroot(k))
- })
- }
- for n in (1..27) {
- say "a(10^#{n}) = #{prime_power_count(10**n)}"
- }
- __END__
- a(10^1) = 7
- a(10^2) = 35
- a(10^3) = 193
- a(10^4) = 1280
- a(10^5) = 9700
- a(10^6) = 78734
- a(10^7) = 665134
- a(10^8) = 5762859
- a(10^9) = 50851223
- a(10^10) = 455062595
- a(10^11) = 4118082969
- a(10^12) = 37607992088
- a(10^13) = 346065767406
- a(10^14) = 3204942420923
- a(10^15) = 29844572385358
- a(10^16) = 279238346816392
- a(10^17) = 2623557174778438
- a(10^18) = 24739954338671299
- a(10^19) = 234057667428388198
- a(10^20) = 2220819603016308079
- a(10^21) = 21127269487386615271
- a(10^22) = 201467286693435354626
- a(10^23) = 1925320391619238700024
- a(10^24) = 18435599767386814628355
- a(10^25) = 176846309399257764978954
- a(10^26) = 1699246750872783231673649
- a(10^27) = 16352460426842732867857607
|