binary_search.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 10 July 2019
# https://github.com/trizen

# Positive integers k at which k/log_2(k) is at a record closeness to an integer, without actually being an integer.
# OEIS: https://oeis.org/A307099

# Known terms:
#    3, 10, 51, 189, 227, 356, 578, 677, 996, 3389, 38997, 69096, 149462, 2208495, 3459604, 4952236, 6710605, 48098656, 81762222, 419495413

# Similar sequence for k/log(k):
#   2, 5, 9, 13, 17, 163, 53453, 110673, 715533
#   https://oeis.org/A178805

#~ func log2(n) {
    #~ n.log
#~ }

func find_k(x) {

    var k = bsearch_le(1e10, {|k|
       k/log2(k) <=> x
    })

    var t1 = k/log2(k)
    var t2 = (k+1)/log2(k+1)

    if (abs(x - t2) < abs(x - t1)) {
        return (t2, k+1)
    }

    return (t1, k)
}

#~ say find_k(222676)
#~ say find_k(14645100)

func diff(x) { abs(x - round(x)) }

var mindiff = Inf

for x in (2..1e9) {

    var (t, k) = find_k(x)

    if (k&(k-1) == 0) {
        next
    }

    var dx = diff(t)

    if (dx < mindiff) {
        mindiff = dx
        print(k, ", ")
    }
}

__END__

var x = 14645100.0000000023234523143424662940405952123775

say bsearch_le(1e9, {|k|
    k/log2(k) <=> x
})

__END__
func diff(x) { abs(x - round(x)) }

    var mindiff = Inf

    for k in (3..1e9) {

        if (k&(k-1) == 0) {
            next
        }

        var x = k/log2(k)
        var dx = diff(x)

        if (dx < mindiff) {
            mindiff = dx
            print(k, ", ")
        }
    }