#!/usr/bin/ruby

var n = 10**19

assert_eq(n.bsearch_le { |k|
    ((k*(log(k)-1) + log(Num.tau*k)/2)) / log(10) <=> n
}, 577134533044522749)  # see also: https://oeis.org/A119906

assert_eq(n.bsearch_ge { |k|
    ((k*(log(k)-1) + log(Num.tau*k)/2)) / log(10) <=> n
}, 577134533044522750)


assert_eq(bsearch_le(100, 200, {|n| exp(n) <=> 10**65 }), 149)   # i.e.: exp(149) <= 10^65
assert_eq(bsearch_ge(100, 200, {|n| exp(n) <=> 10**65 }),150)    # i.e.: exp(150) >= 10^65

assert_eq(100.bsearch {|n| n! <=> 120 }, 5)           # 5! = 120
assert_eq(bsearch(50, 80, {|n| n**2 <=> 4225 }), 65)  # 65^2 = 4225

define Ï„ = Num.tau

func number_of_required_terms(n) {
    n.bsearch_le { |k|
        ((k*(log(k)-1) + log(Ï„*k)/2)) / log(10) <=> n
    }
}

assert_eq(number_of_required_terms(100), 69)
assert_eq(number_of_required_terms(500), 253)
assert_eq(number_of_required_terms(1e20), 5463531774867094396)
assert_eq(number_of_required_terms(1e21), 51865645374019695121)

assert_eq(20..100 -> bsearch { |n| n! <=> 30! }, 30)
assert_eq(42..100 -> bsearch_le { |n| exp(n) <=> 10**28 }, 64)   # i.e.: exp(64) <= 10^28
assert_eq(42..100 -> bsearch_ge { |n| exp(n) <=> 10**28 }, 65)   # i.e.: exp(65) >= 10^28

for k in (1..100) {
    var t = bsearch_min(1, irand(1e4,1e5), {|p|
        pi(p) <=> k
    })

    assert_eq(pi(t), k)
    assert(pi(t-1) < k)

    var u = bsearch_max(1, irand(1e4,1e5), {|p|
        pi(p) <=> k
    })

    assert_eq(pi(u), k)
    assert(pi(u+1) > k)
}

for k in (1..100) {

    var q = prime(k)
    var t = bsearch_min(1, irand(1e4,1e5), {|p|
        prime(p) <=> q
    })

    assert_eq(prime(t), q)

    var u = bsearch_max(1, irand(1e4,1e5), {|p|
        prime(p) <=> q
    })

    assert_eq(prime(u), q)
}

for k in (2..100) {
    var t = bsearch_min(1, irand(1e4,1e5), {|p|
        prime(p) <=> k
    })

    assert(prime(t) >= k, "prime(#{t}) >= #{k}")
    assert(prime(t+1) > k, "prime(#{t}+1) > #{k}")
    assert(prime(t-1) < k, "prime(#{t}-1) < #{k}")

    var u = bsearch_max(1, irand(1e4,1e5), {|p|
        prime(p) <=> k
    })

    assert(prime(u) <= k, "prime(#{t}) <= #{k}")
    assert(prime(u+1) > k, "prime(#{t}) > #{k}")
    assert(prime(u-1) < k, "prime(#{t}) < #{k}")
}

say "** Test passed!"