Определение
Целое положительное число n
является практическим числом (последовательность OEIS A005153 ), если все меньшие положительные целые числа могут быть представлены в виде сумм различных делителей n
.
Например, 18
это практическое число: его делители равны 1, 2, 3, 6, 9 и 18, а остальные натуральные числа меньше 18 можно сформировать следующим образом:
4 = 1 + 3 5 = 2 + 3 7 = 1 + 6
8 = 2 + 6 10 = 1 + 9 11 = 2 + 9
12 = 3 + 9 = 1 + 2 + 9 = 1 + 2 + 3 + 6
13 = 1 + 3 + 9 14 = 2 + 3 + 9 15 = 6 + 9
16 = 1 + 6 + 9 17 = 2 + 6 + 9
Но 14
это не практическое число: его делителями являются 1, 2, 7 и 14, и нет подмножества их, которое добавляет к 4, 5, 6, 11, 12 или 13.
Вызов
Напишите программу, функцию или глагол, которые принимают в качестве входных данных положительное целое число x
и либо возвращают, либо выводят на печать x- е практическое число, индексированное от 1 для соответствия OEIS. Ваш код должен быть достаточно эффективным, чтобы он мог обрабатывать ввод до 250000 менее чем за две минуты на приемлемом настольном компьютере. (Примечание: моя эталонная реализация в Java управляет 250000 менее чем за 0,5 секунды, а моя эталонная реализация в Python управляет ею за 12 секунд).
Контрольные примеры
Input Expected output
1 1
8 18
1000 6500
250000 2764000
1000000 12214770
3000000 39258256
источник
Ответы:
J (99 символов)
Поскольку постановка задачи требует «программы, функции или глагола », кто-то должен был сделать J-представление. J люди заметят, что я не играл в гольф (!) И не оптимизировал это. Как и другие записи, я использовал теорему Стюарта, упомянутую в ссылке OEIS, чтобы проверить, является ли каждое четное число практичным или нет.
У меня нет готового доступа к «разумному настольному компьютеру» с установленным J. На моем шестилетнем нетбуке он
f 250000
вычисляется за 120,6 секунды, что не намного меньше двух минут, но, по-видимому, на любом чуть более разумном компьютере это заканчивается вовремя.источник
Mathematica,
126121 символовСпасибо Велисарию.
Используя формулу в Википедии.
Примеры:
На
f[250000]
моем компьютере потребовалось 70-е годы .источник
(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Хаскелл - 329
Примеры:
Вот небольшой набор тестов (см. Выше):
Результаты теста после компиляции с
ghc -O3
:источник
parse error on input `='
. Нужно ли использовать какой-либо флаг или другой?asdf.hs
и запуститьghci asdf.hs
, тогда оттуда вы сможете получить доступf
ghc --make -O3 [filename]
. Вы также можете загрузить его в GHCI с:l [filename]
но с учетом скомпилированных временных ограничений, вероятно, лучше. :)ghci
загружает файлы, указанные в его аргументахghc
. Ваш компьютер работает быстрее, чем мой, но он все равно находится в пределах критерия производительности на моем компьютере за 98 секунд.Javascript,
306 307282B250к в ок. 6s на моем ноутбуке.
Прокомментированный негольфовый код: http://jsfiddle.net/82xb9/3/ теперь с улучшенным сигма-тестированием и улучшенным условием (спасибо, комментарии)
Предварительно отредактированные версии: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/
источник
k--;
наreturn k-1
. Хотя это немного увеличивает количество байтов, вы можете сэкономить несколько таких вещей, как заменаp[i]>=P+2
наp[i]>P+1
(и, вероятно, удалив внутренний вызов функции и используяbreak
вместо него).