123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 |
- #!/usr/bin/ruby
- # The number of n-almost primes less than or equal to 10^n, starting with a(0)=1.
- # https://oeis.org/A116430
- # Known terms:
- # 1, 4, 34, 247, 1712, 11185, 68963, 409849, 2367507, 13377156, 74342563, 407818620, 2214357712, 11926066887, 63809981451, 339576381990, 1799025041767
- # New terms:
- # a(17) = 9494920297227
- # a(18) = 49950199374227
- # a(19) = 262036734664892
- #`{
- # PARI/GP program:
- almost_prime_count(N, k) = if(k==1, return(primepi(N))); (f(m, p, k, j=0) = my(c=0, s=sqrtnint(N\m, k)); if(k==2, forprime(q=p, s, c += primepi(N\(m*q))-j; j += 1), forprime(q=p, s, c += f(m*q, q, k-1, j); j += 1)); c); f(1, 2, k);
- a(n) = if(n == 0, 1, almost_prime_count(10^n, n)); \\ ~~~~
- }
- #for n in (0..100) {
- for n in (0..100) {
- say [n, n.almost_prime_count(10**n)]
- }
- __END__
- [0, 1]
- [1, 4]
- [2, 34]
- [3, 247]
- [4, 1712]
- [5, 11185]
- [6, 68963]
- [7, 409849]
- [8, 2367507]
- [9, 13377156]
- [10, 74342563]
- [11, 407818620]
- [12, 2214357712]
- [13, 11926066887]
- [14, 63809981451]
- [15, 339576381990]
- [16, 1799025041767]
- [17, 9494920297227]
- [18, 49950199374227]
- [19, 262036734664892]
|