Самый быстрый способ отфильтровать последовательность 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
• 6 x 9= 54
• 6 x 10= 60
• 6 x 11= 66 (две шестерки; это не разные цифры.)

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

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

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

родовое слово

Answer 1

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

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

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

родовое слово

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

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

родовое слово

, который возвращает истину, если все цифры в коде number_str уникальны, иначе - ложь.

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

родовое слово

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

родовое слово

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

родовое слово

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

родовое слово

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

родовое слово

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

родовое слово

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

родовое слово

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

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

родовое слово

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

родовое слово

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

родовое слово

Answer 2

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

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

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

Answer 3

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

1) Перебор последовательности A010784.

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

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

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

родовое слово

Answer 4

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