找到 2^k 以 n 开头的最小 k

Question

给定一个正整数n≤10⁷，我需要找到最小的正整数k 使得 2^k 的十进制表示以 n 的十进制表示开头。

因此，例如，如果 n = 12，则 k = 7（因为 2⁷ = 128);如果 n = 134，则 k = 27（因为 2²⁷ = 134 ,217,728);如果 n = 82，则 k = 209（因为 2²⁰⁹ ≈ 8.23×10⁶²).

（如果不存在这样的k，我需要return −1。）

我什至没有尝试用公式来解决它（我不知道如何解决），而是决定通过计算 2 的所有幂到 1000，将它们放在一个列表中，然后找到索引来解决以 n 开头的数字。该代码有效，但是......它甚至没有通过系统中的第一个测试。我不知道为什么，因为它适用于上述示例。无论如何，这是代码。

def find_all():
    arr = []
    n = 1
    for i in range(1000):
        arr.append(str(n))
        n = n << 1
    return arr


n = str(n)
NOT_FOUND = True
#n = input()
arr = find_all()
for i in arr:
    if i.startswith(n):
        print(arr.index(i), n)
        NOT_FOUND = False
        break
if NOT_FOUND:
    print(-1, n)

有什么问题吗？

Answer 1

假设您想求以 123 开头的 2 的幂。

这相当于找到 log₁₀(2) 的倍数，其 mantissa 位于 0.089905111439398 和 0.093421685162235 之间（因为 log₁₀(123) = 2.089905111439398 和 log₁₀(124) = 2.093421685162235).

如果你这样设计问题，就不需要计算 2 的巨大次方。你只需要一点浮点运算。

以下代码运行良好，但当 n 接近 10⁷:

时需要几秒钟才能得出答案

def power_of_2_with_prefix(n):
    # Find the minimum integer k such that the digits of 2^k
    # start with the digits of n
    from math import log10
    #
    # First deal with trivial cases
    assert type(n) is int
    if n == 1:
        return 0
    if n < 1:
        return -1
    #
    # Calculate mantissa range
    logmin = log10(n)
    logmax = log10(n+1)
    logmin -= int(logmin)
    logmax -= int(logmax)
    if logmax < logmin:
        logmax += 1
    #
    # Now find a power of 2 whose log10 mantissa lies in this range
    log2 = log10(2)
    # Make sure k is large enough to include all trailing zeros of n
    mink = log10(n) / log10(2)
    x = 1
    k = 0
    while not (logmin <= x < logmax and k >= mink):
        x += log2
        if x >= 1:
            x -= 1
        k += 1
    return k

assert power_of_2_with_prefix(0) == -1
assert power_of_2_with_prefix(1) == 0
assert power_of_2_with_prefix(2) == 1
assert power_of_2_with_prefix(4) == 2
assert power_of_2_with_prefix(40) == 12
assert power_of_2_with_prefix(28584) == 74715
assert power_of_2_with_prefix(28723) == 110057
assert power_of_2_with_prefix(9999999) == 38267831

找到 2^k 以 n 开头的最小 k

Finding the minimal k that 2^k begins with n

python

algorithm

decimal