Нахождение минимального k, что 2 ^ k начинается с n - PullRequest
Новая
       3

Нахождение минимального k, что 2 ^ k начинается с n

0 голосов
/ 16 февраля 2020

Учитывая положительное целое число n ≤ 10 7 , мне нужно найти наименее положительное целое число k , такое, что десятичное представление 2 k начинается с десятичного представления n .

Так, например, если n = 12, то k = 7 (потому что 2 7 = 12 8); если n = 134, то k = 27 (потому что 2 27 = 134 , 217 728); а если n = 82, то k = 209 (потому что 2 209 ≈ 8,2 3 × 10 62 ).

(Если таких k не существует, мне нужно вернуть -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)

Что может быть не так?

1 Ответ

6 голосов
/ 17 февраля 2020

Предположим, вы хотите найти степень 2, которая начинается с 123.

Это эквивалентно нахождению кратного лога 10 (2), у которого мантисса лежит между 0.089905111439398 и 0.093421685162235 (потому что log 10 (123) = 2.089905111439398 и log 10 (124) = 2.093421685162235).

Если вы задаете вопрос таким образом нет необходимости вычислять огромные степени 2. Все, что вам нужно, это немного арифметики с плавающей точкой c.

Следующий код работает довольно хорошо, но занимает несколько секунд, чтобы получить ответы, когда n близко к 10 7 : 

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
...