First power of 2 that has leading decimal digits of 12

func farey_approximations(r, callback) {

    var (a1 = r.int, b1 = 1)
    var (a2 = a1+1,  b2 = 1)

    loop {
        var a3 = a1+a2
        var b3 = b1+b2

        if (a3 < r*b3) {
            (a1, b1) = (a3, b3)
        }
        else {
            (a2, b2) = (a3, b3)
        }

        callback(a3 / b3)
    }
}

func p(L, nth) {

    define ln2  = log(2)
    define ln5  = log(5)
    define ln10 = log(10)

    var t = L.len-1

    func isok(n) {
        floor(exp(ln2*(n - floor((n*ln2)/ln10) + t) + ln5*(t - floor((n*ln2)/ln10)))) == L
    }

    var deltas = gather {
        farey_approximations(ln2/ln10, {|r|
            take(r.de) if (r.de.len == L.len)
            break      if (r.de.len >  L.len)
        })
    }.sort.uniq

    var c = 0
    var k = (1..Inf -> first(isok))

    loop {
        return k if (++c == nth)
        k += (deltas.first {|d| isok(k+d) } \\ die "error: #{k}")
    }
}

var tests = [
    [12, 1],
    [12, 2],
    [123, 45],
    [123, 12345],
    [123, 678910],

    # extra
    [1234, 10000],
    [12345, 10000],
]

for a,b in (tests) {
    say "p(#{a}, #{b}) = #{p(a,b)}"
}

Output:

p(12, 1) = 7
p(12, 2) = 80
p(123, 45) = 12710
p(123, 12345) = 3510491
p(123, 678910) = 193060223
p(1234, 10000) = 28417587
p(12345, 10000) = 284166722

Last updated