brilliant_numbers_count.sf

#!/usr/bin/ruby

# Count the number of Brilliant numbers < 10^n.

# Brilliant numbers are semiprimes such that both prime factors have the same number of digits in base 10.

# OEIS sequence:
#   https://oeis.org/A086846 --  Number of brilliant numbers < 10^n.

# See also:
#   https://rosettacode.org/wiki/Brilliant_numbers

func brilliant_numbers_count_fast(n) {

    var count = 0
    var len = n.isqrt.len

    for k in (1 .. len-1) {
        var pi = prime_count(10**(k-1), 10**k - 1)
        count += binomial(pi, 2)+pi
    }

    var min = (10**(len - 1))
    var max = (10**len - 1)

    each_prime(min, max, {|p|
        count += prime_count(p, max `min` idiv(n, p))
    })

    return count
}

func brilliant_numbers_count_faster(n) {

    var count = 0
    var len = n.isqrt.len

    for k in (1 .. len-1) {
        var pi = (prime_count(10**k) - prime_count(10**(k-1)))
        count += binomial(pi, 2)+pi
    }

    var min = (10**(len - 1))
    var max = (10**len - 1)

    var pi_min = prime_count(min)
    var pi_max = prime_count(max)

    var j = -1

    each_prime(min, max, {|p|
        p*p <= n || break
        count += (((n >= max*p) ? pi_max : prime_count(idiv(n, p))) - pi_min - ++j)
    })

    return count
}

func brilliant_numbers_count_slow(n) {

    var count = 0

    for k in (1 .. n.isqrt.len) {
        var P = primes(10**(k-1), 10**k - 1)
        for i in (0..P.end) {
            for j in (i..P.end) {
                P[i]*P[j] > n ? break : ++count
            }
        }
    }

    return count
}

for n in (1..9) {
    printf("Less than 10^%s, there are %s brilliant numbers\n", n, brilliant_numbers_count_faster(10**n - 1))
}


__END__
Less than 10^1, there are 3 brilliant numbers
Less than 10^2, there are 10 brilliant numbers
Less than 10^3, there are 73 brilliant numbers
Less than 10^4, there are 241 brilliant numbers
Less than 10^5, there are 2504 brilliant numbers
Less than 10^6, there are 10537 brilliant numbers
Less than 10^7, there are 124363 brilliant numbers
Less than 10^8, there are 573928 brilliant numbers
Less than 10^9, there are 7407840 brilliant numbers
Less than 10^10, there are 35547994 brilliant numbers
Less than 10^11, there are 491316166 brilliant numbers
Less than 10^12, there are 2409600865 brilliant numbers