12345678910111213141516171819202122232425262728293031323334353637383940 |
- #!/usr/bin/ruby
- # Efficient formula for counting the numbers of perfect powers <= n.
- # Formula:
- # a(n) = n - Sum_{1..floor(log_2(n))} mu(k) * (floor(n^(1/k)) - 1)
- # = 1 - Sum_{2..floor(log_2(n))} mu(k) * (floor(n^(1/k)) - 1)
- # See also:
- # https://oeis.org/A069623
- func perfect_power_count(n) {
- 1 - sum(2..n.ilog(2), {|k|
- mu(k) * (n.iroot(k) - 1)
- })
- }
- for n in (0..15) {
- printf("a(10^%d) = %s\n", n, perfect_power_count(10**n))
- assert_eq(perfect_power_count(10**n), 10**n -> perfect_power_count)
- }
- __END__
- a(10^0) = 1
- a(10^1) = 4
- a(10^2) = 13
- a(10^3) = 41
- a(10^4) = 125
- a(10^5) = 367
- a(10^6) = 1111
- a(10^7) = 3395
- a(10^8) = 10491
- a(10^9) = 32670
- a(10^10) = 102231
- a(10^11) = 320990
- a(10^12) = 1010196
- a(10^13) = 3184138
- a(10^14) = 10046921
- a(10^15) = 31723592
|