Самый быстрый способ фильтрации последовательности A010784

Question

Последовательность A010784 в OEIS - это последовательность, содержащая только цифры с разными цифрами.Это конечное количество.

Я пытался найти несколько чисел в этой последовательности с определенными атрибутами.
Например: 6 - это отдельное число величиной 10. Это можно найти какследует:

• 6 x 1 = 6
• 6 x 2 = 12
• 6 x 3 = 18
• 6 x 4 = 24
• 6 x 5 = 30
• 6 x 6 = 36
• 6 x 7 = 42
• 6 x 8 = 48
• 6x 9 = 54
• 6 x 10 = 60
• 6 x 11 = 66 (две шестерки; это не разные цифры.)

Теперь япытаюсь набрать наибольшее число, доступное для нескольких величин порядка.
Скажем, все заказы от 1 до 20.

То, что я сейчас делаю, это цикл из максимально возможного отличного числа, которое составляет 9 876 543 210и наибольшее уникальное число величины 1, вплоть до очень низкого числа.
Этот метод считает крайне неэффективным.По крайней мере, для меня это так.

Я почти уверен, что мне не хватает некоторых вещей о факторинге, которые могли бы сделать вещи намного быстрее.

def unique_num(num):
    # Check whether number is unique.
    return Boolean

def unique_num_magnitude(num):
    # Check of which magnitude the unique number is
    return Integer

# Dictionary with the current highest values
# for each magnitude.
values = {1: 987654321...}

# Set limits
upper_limit = 9876543210
lower_limit = 1

for numbers in range(upper_limit, lower_limit, -1):
    unique = unique_num(num) # Boolean
    if (unique):
        magnitude = unique_num_magnitude(num)
        if (values[magnitude] < num):
            values[magnitude] = num

Answer 1

Конечно, есть лучший способ.Вы должны построить числа снизу вверх, т. Е. Если число a1 ... ak (это k цифр) не имеет величины N, так что цифра появляется дважды в первых k цифрах результата для любого мультипликатора 2..N тогдатакже нет любого числа b1 ... bm a1 ... ak.Это обеспечивает значительно более быструю процедуру рекурсивного перечисления, поскольку сокращает экспоненциальный объем пространства поиска.Детали оставлены в качестве упражнения для OP.

Более подробное объяснение:

Предположим, существует процедура

 magnitude(number_str)

, которая вычисляет величину для числа number_str, представленного в 10-base, так что процедура возвращает 0, если number_str содержит хотя бы одно двойное вхождение цифры, 1, если number_str имеет каждую отдельную цифру, но умножение числа на два приводит к появлению цифры несколько раз и т. д.

Эта процедура может быть реализована в терминах другой

 unique_digits(number_str)

, которая возвращает true, если все цифры в number_str уникальны, в противном случае - false.

Теперь тогда magnitudeможет быть реализовано как

 magnitude(number_str):
   n = str_to_int(number_str)
   k = n
   i = 0
   while (unique_digits(int_to_str(k))):
     k = k + n
     i = i + 1
   return i

Теперь эту процедуру magnitude можно изменить на nocarry_magnitude, который слегка изменяет проверку:

 nocarry_magnitude(number_str, limit):
   l = length(number_str)
   assert (l > 0)
   n = str_to_int(number_str)
   k = n
   i = 0
   while (unique_digits(right_substring(int_to_str(k), l))):
     k = k + n
     i = i + 1
     if (i == limit):
       break
   return i

Эта процедура проверяет наличие нескольких разцифры только в количестве самых правых цифр (младших разрядов) продукта в цикле, сколько было цифр в исходном вводе.Параметр limit необходим, чтобы убедиться, что процедура завершается, поскольку в противном случае процедура может выполняться в бесконечном цикле.Очевидно, что для любой строки s она гласит, что

 magnitude(s) <= nocarry_magnitude(s, M) for large M

Например, возьмите номер 19:

 19 * 1 = 19
 19 * 2 = 38
 19 * 3 = 57
 19 * 4 = 76
 19 * 5 = 95
 19 * 6 = 114 // magnitude("19") = 5
 19 * 7 = 133 // nocarry_magnitude("19", 100) = 6

То, что я написал выше в кратком описании, это то, что если

 nocarry_magnitude(s, x) == k     for x > k

затем для любой строки, полученной с помощью постфикса s (обозначим это x + s ниже), оно гласит, что

 x : string of digits
 magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
 when m >= magnitude(x + s)

Первое неравенство вытекает из приведенного выше утверждения, а второе -очевидно из определения nocarry_magnitude.Обратите внимание, что величина (x + s) <= величина (и) в общем случае не является теоремой, примером которой является </p>

 magnitude( "56")  = 1  // 56 * 2 = 112
 magnitude("256")  = 12 // the first duplicate occurs at 3328

, вызванная переносом.nocarry_magnitude игнорирует перенос, поэтому суффикс строки всегда имеет большую nocarry-звездную величину, чем любое его расширение (влево, то есть цифры более высокого порядка).

Теперь вы можете написать значительноболее быстрая рекурсивная процедура, такая как поиск чисел с величиной не менее M:

 search(str):
   if (str != ""):
     int n = nocarry_magnitude(str, M)
     if (n < M):
       return      # the optimization
     int k = magnitude(str)
     if (k >= M):
       store_answer(str)
   for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
             '10', '20', '30', '40', '50', '60', '70', '80', '90']:
     search(d + str)

 search("")

Вот полная реализация Python (поиск величины 36):

def unique_digits(s):
    r = (len(list(s)) == len(set(s)))
    return r

def magnitude(s):
    n = int(s)
    k = n
    assert n > 0
    i = 0
    while (unique_digits(str(k))):
        k = k + n
        i = i + 1
    return i

def nocarry_magnitude(s, limit):
    l = len(s)
    assert l > 0
    n = int(s)
    assert n > 0
    k = n
    i = 0
    while (unique_digits(str(k)[-l:])):
        k = k + n
        i = i + 1
        if (i >= limit):
            break
    return i

M = 36

def search(s):
    if (not(s == "")):
        n = nocarry_magnitude(s, M)
        if (n < M):
            return
        k = magnitude(s)
        if (k >= M):
            print "Answer: %s |" % s,
            i = int(s)
            k = i
            n = 1
            while (n <= M):
                print k,
                k = k + i
                n = n + 1
            print
    for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
              '10', '20', '30', '40', '50', '60', '70', '80', '90']:
        search(d + s)

search("")

И вот такой прогонзанимает менее одной секунды;это находит ответ «27», который представляется уникальным числом, обеспечивающим рекордную величину 36:

Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
             432 459 486 513 540 567 594 621 648 675 702 729 756 783
             810 837 864 891 918 945 972

Answer 2

У вас есть две проблемы:

1) Итерация по последовательности A010784.

Используйте itertools.permutations для генерации возможных последовательных чисел.

2) Расчет величины числа.

Вы можете определить, имеет ли номер только уникальные цифры, с помощью этого фрагмента кода:

def unique_num(x):
    return len(str(x)) == len(set(str(x))

Answer 3

Разве это не просто проблема перестановки?Для данной величины M вы делаете 10 см.

Например, для величины 2, сколько способов выбрать 2 цифры из 0..9?(На самом деле, это должен быть один из 1..9 и один из 0..9, где вторая цифра не совпадает с первой.)

Вам, конечно, не нужно проходить их все и проверятьих.Просто настройте набор и выберите один, затем выберите другой.А еще лучше, просто создайте их с нуля.Сначала выполните все, что начинается с 1 (10, 12, 13, 14 и т. Д.), Затем все, что начинается с 2 и т. Д.

Answer 4

Вы можете сократить некоторые ветви, если вы просто ищете самые большие числа.Из 6 x 11 = 66 вы также знаете, что величина 11 не больше 5. Как только вы узнаете большее число с величиной> = 5, вы можете пропустить значение 11.