Самый быстрый способ отфильтровать последовательность A010784
Последовательность A010784 в OEIS - это последовательность, содержащая только цифры с разными цифрами. Это конечная сумма.
Я пытался найти несколько чисел в этой последовательности с определенными атрибутами.
Например: 6 является отдельным числом величины 10. Это может быть найдено следующим образом:
- 6 х 1 = 6
- 6 х 2 = 12
- 6 х 3 = 18
- 6 х 4 = 24
- 6 х 5 = 30
- 6 х 6 = 36
- 6 х 7 = 42
- 6 х 8 = 48
- 6 х 9 = 54
- 6 х 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
4 ответа
Конечно, есть лучший способ. Вы должны построить числа снизу вверх, то есть, если число a1...ak (это k цифр) не имеет величины N, так что цифра появляется дважды в пределах первых k цифр результата для любого мультипликатора 2..N тогда также нет любого числа b1...bm a1...ak. Это обеспечивает значительно более быструю процедуру рекурсивного перечисления, поскольку оно сокращает экспоненциальный объем пространства поиска. Детали оставлены в качестве упражнения для ОП.
Более длинное объяснение:
Предположим, что есть процедура
magnitude(number_str)
который рассчитывает величину для числа number_str представлены в 10-значном, так что процедура возвращает 0, если number_str содержит хотя бы одно двойное вхождение цифры, 1 если number_str каждая цифра различна, но умножение числа на два приводит к появлению цифры несколько раз и т. д.
Эта процедура может быть реализована в рамках другой
unique_digits(number_str)
который возвращает истину, если все цифры в number_str являются уникальными, в противном случае ложными.
Сейчас, когда 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) <= величина (и) в общем случае не является теоремой, примером которой является
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
У вас есть две проблемы:
1) Итерация по последовательности A010784.
Используйте itertools.permutations для создания последовательных возможных чисел.
2) Расчет величины числа.
Вы можете определить, имеет ли номер только уникальные цифры с помощью этого фрагмента кода:
def unique_num(x):
return len(str(x)) == len(set(str(x))
Разве это не просто проблема перестановок? Для данной величины M ты делаешь 10см.
Например, с величиной 2, сколько способов выбрать 2 цифры из 0..9? (На самом деле это должен быть один из 1..9 и один из 0..9, где вторая цифра не соответствует первой.)
Вам, конечно, не нужно проходить их все и проверять. Просто настройте набор и выберите один, затем выберите другой. А еще лучше, просто создайте их с нуля. Сначала выполните все, что начинается с 1 (10, 12, 13, 14 и т. Д.), Затем все, что начинается с 2 и т. Д.
Вы можете вырезать несколько веток, если вы просто ищете самые большие цифры. От 6 x 11 = 66 Вы также знаете, что величина 11 не больше 5. Как только вы знаете большее число с величиной>= 5, вы можете пропустить 11.