686. Powers of Two.md

686. Powers of Two

Question

is the first power of two whose leading digits are "12". The next power of two whose leading digits are "12" is .

Define p(L, n) to be the nth-smallest value of j such that the base 10 representation of begins with the digits of L. So p(12, 1) = 7 and p(12, 2) = 80.

You are also given that p(123, 45) = 12710. Find p(123, 678910).

Solution

The solution is to find integer k such that

which is equivalent of

Again, pypy reduces running time massively from 1min to 0.3sec.

def p686(n=678910):
    LOG2_123 = log(1.23, 2)
    LOG2_124 = log(1.24, 2)
    LOG2_10 = log(10, 2)

    i, j = 0, 0
    while j < n:
        l = int(LOG2_123 + i * LOG2_10 + 1)
        m = int(LOG2_124 + i * LOG2_10)

        if j + (m - l + 1) >= n:
            return n + l - j - 1
        else:
            j += m - l + 1
        i += 1

Note

Calculating log is expensive. Time needed for 10 million (1e7) calls:

Log	Time
log(1)	2s
log(1, 2)	3s
log(1) / log(2)	4s

Answer

193060223