Учитывая число n> 77 , напишите программу или функцию, которая находит набор различных положительных целых чисел, так что сумма набора равна n , а сумма обратных значений набора равна 1.
Пример для 80:
80 = 2 + 4 + 10 + 15 + 21 + 28 ⟶ 1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1
Ваша программа или функция должна (теоретически) работать для любых n <2 32 и не должна быть оправдана за ошибки округления с плавающей запятой. Отметим, что решения существуют для всех n> 77 .
Самый короткий код в байтах побеждает.
Есть бонусный стимул: я назначу награду за самое маленькое решение, которое работает для любого n и запускает log (n) . Для малых n оно должно быть быстрым (определяется на мое усмотрение). Да, это возможно
O(log n)
алгоритм.Ответы:
Mathematica, 54 байта
Примерно так же неэффективно, как это получается, но это решает
n = 78
примерно за 9 секунд.Результат возвращается в виде списка, заключенного в одноэлементный список, например:
источник
Python 3,
73061995 байтЭто решение работает в log (n) сложности (насколько я могу судить).
Вы можете проверить, что
f(2**32 - 1)
работает почти мгновенноЯ использовал эту статью о методе для его вычисления. С помощью этого метода существует огромный массив данных для предварительно определенных значений для n от 78 до 334 без четных чисел после 168. Я хотел превратить эти данные во что-то маленькое, и я не знал хороших алгоритмов сжатия, поэтому я сделал мой собственный.
Я сжал его, имея список правил замены строк. Я создал метод, который нашел правило замены строки, которое сократило бы большинство содержимого во всем, принимая во внимание определение правила. Затем я применял это рекурсивно, пока не смог создать больше правил (я использовал символы gz и AZ). Строка, которую я сделал для замены, представляла собой разделенный запятыми список шестнадцатеричных значений для каждого из чисел. В ретроспективе, преобразование их в их шестнадцатеричные значения, возможно, не было самым разумным выбором, вероятно, было бы короче оставить их в десятичном виде, поскольку наличие шестнадцатеричного числа сохраняло бы только трехзначные числа, но добавляло бы 0 для однозначных чисел.
В строке, где я установил c, вы можете увидеть список правил замены и текст, на котором он выполняется. Правила также должны применяться в обратном порядке, поскольку некоторые правила включают символы, созданные из других правил.
В этом коде также есть множество мест, где я мог бы сократить синтаксис, например, превратить список списков в один список, а затем использовать другой метод для доступа к правилам, чтобы заменить текст на
источник
n=218
выходы[2]
это то, что ожидается ??Haskell, 93 байта
Ужасно медленный 1, но он работает в постоянной памяти. Тривиальное решение: проверьте все подпоследовательности
[2..n]
на сумму и сумму взаимных.Возвращение всех решений вместо одного на 3 байта короче: просто удалите
!!0
(будьте осторожны: время выполнения всегда будет вне графика).1 Время выполнения зависит от того, насколько рано результат появится в списке подпоследовательностей. Лень Хаскелла останавливает поиск, если найдено первое совпадение. После компиляции
p 89
(result[3,4,6,9,18,21,28]
:) запускается на моем (4-летнем) ноутбуке в 35 лет. Другие значения, даже меньшие, могут занять часы.источник
Юлия, 77 байт
Это неэффективная лямбда-функция, которая принимает целое число и возвращает целочисленный массив. Чтобы вызвать его, присвойте его переменной.
Мы получаем разделы целого числа, используя
partitions
. Затем мы отфильтровываем набор разделов только с теми, у которых уникальные элементы имеют взаимные суммы, равные 1. Чтобы гарантировать отсутствие ошибок округления, мы используемRational
тип Джулии для создания обратных ссылок .filter
возвращает итератор, поэтому мы должныcollect
преобразовать его в массив. Это дает нам массив массивов (только с одним элементом), поэтому мы можем получить первое использование[1]
.Теперь, когда я говорю неэффективно, я имею в виду это. Выполнение этого для n = 80 занимает 39.113 секунды на моем компьютере и выделяет 13.759 ГБ памяти.
источник