sidef-scripts/Math/prime_power_counting_function.sf

#!/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