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

Question

所以我发现这个数学问题归结为找到最小k，其中2 ^ k以n开头。输入包含n <= 10 ^ 7，并且输出应为k（或-1，如果不存在此类k）我什至没有尝试用公式来解决（我不知道怎么做），而是决定通过计算2的所有幂（直到1000），将它们放在列表中，然后找到开始的数字的索引来解决。与n。该代码有效，但是...它甚至没有通过系统中的第一个测试。我不知道为什么，因为提供的示例（12-7、134-27、82-209）可以无缝运行。无论如何，这是代码。

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

这里是一种没有限制的优化算法。到目前为止，我已经运行了一段时间，最差的n为28,584，最大k为74,715。如果n没有k解决方案并且到目前为止还没有，它将挂起。

import functools

# caches solutions of i so never calculated more than once for any i.
@functools.lru_cache(maxsize=None)
def power(i):
    return str(2**i)

# hangs if k doesn't exist, except for 0.
def f(n):
    if n < 1: return -1
    x = str(n)
    i = 0
    while True:
        if power(i).startswith(x):
            return i
        i += 1

for n in range(10000000):
    print(f'{n:4} ',end='',flush=True)
    if (i := f(n)) >= 0:
        print(f'{i:5} {str(2**i)[:10]}')
    else:
        print(f'-1')