Подсчитайте практические цифры

18

Определение

Целое положительное число 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
Питер Тейлор
источник
(ИМХО) это может даже стать интересным, если выиграет самый быстрый код (для каждого языка?)
отображаемое имя
4
@SargeBorsch Итак, вы увидите таблицы из 250 тыс. Записей по всем ответам
д-р belisarius
@belisarius хорошая мысль. но я думаю, что такой обман может быть легко запрещен. Или проблема может потребовать правильных ответов для любого числа, но тогда возникнут трудности при выполнении этого на языке без больших целых чисел в стандартной библиотеке ...: /
Отображаемое имя
Я имею в виду одну алгоритмическую оптимизацию, но с текущими правилами мне лень ее реализовывать: P
отображаемое имя
4
@SargeBorsch, если вы не хотите играть в свой код, не стесняйтесь загрузить его на gist.github.com и оставить ссылку в комментарии здесь или в чате. Я предпочитаю, чтобы код-гольф с большими ограничениями производительности был быстрее кода по двум причинам: во-первых, длина кода более объективно измерима; во-вторых, он вводит элемент компромисса: какие оптимизации скорости можно пропустить, чтобы сократить код без ущерба для производительности?
Питер Тейлор

Ответы:

5

J (99 символов)

f=:3 :0
'n c'=.0 1
while.c<y do.
'p e'=.__ q:n=.n+2
c=.c+*/(}.p)<:}:1+*/\(<:p^e+1)%<:p
end.
n+n=0
)

Поскольку постановка задачи требует «программы, функции или глагола », кто-то должен был сделать J-представление. J люди заметят, что я не играл в гольф (!) И не оптимизировал это. Как и другие записи, я использовал теорему Стюарта, упомянутую в ссылке OEIS, чтобы проверить, является ли каждое четное число практичным или нет.

У меня нет готового доступа к «разумному настольному компьютеру» с установленным J. На моем шестилетнем нетбуке он f 250000вычисляется за 120,6 секунды, что не намного меньше двух минут, но, по-видимому, на любом чуть более разумном компьютере это заканчивается вовремя.

Омар
источник
6

Mathematica, 126 121 символов

Спасибо Велисарию.

Используя формулу в Википедии.

f=(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&

Примеры:

f[1]

1

f[8]

18

f[250000]

2764000

На f[250000]моем компьютере потребовалось 70-е годы .

alephalpha
источник
3
Я думаю, что вы можете получить лучшую производительность за счет одного символа, обходя нечетные целые числа
доктор Белизариус
1
Сокращая код из представления OEIS, вы замедлили выполнение в 10 раз. Просто интересно: «Как вы думаете, почему ваш код работает намного медленнее, чем пример OEIS?»
DavidC
@belisarius Ваше предложение сокращает время вдвое, как и ожидалось.
DavidC
2
То же самое в 119 символах:(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Доктор Велизарий
3

Хаскелл - 329

s 1=[]
s n=p:(s$div n p)where d=dropWhile((/=0).mod n)[2..ceiling$sqrt$fromIntegral n];p=if null d then n else head d
u=foldr(\v l@((n,c):q)->if v==n then(n,c+1):q else(v,1):l)[(0,1)]
i z=(z<2)||(head w==2)&&(and$zipWith(\(n,_)p->n-1<=p)(tail n)$scanl1(*)$map(\(n,c)->(n*n^c-1)`div`(n-1))n)where w=s z;n=u w
f=((filter i[0..])!!)

Примеры:

> f 1
1
> f 13
32
> f 1000
6500

Вот небольшой набор тестов (см. Выше):

import Data.Time.Clock
import System.IO

test x = do
    start <- getCurrentTime
    putStr $ (show x) ++ " -> " ++ (show $ f x)
    finish <- getCurrentTime
    putStrLn $ " [" ++ (show $ diffUTCTime finish start) ++ "]"

main = do
    hSetBuffering stdout NoBuffering
    mapM_ test [1, 8, 1000, 250000, 1000000, 3000000]

Результаты теста после компиляции с ghc -O3:

1 -> 1 [0.000071s]
8 -> 18 [0.000047s]
1000 -> 6500 [0.010045s]
250000 -> 2764000 [29.084049s]
1000000 -> 12214770 [201.374324s]
3000000 -> 39258256 [986.885397s]
МНИИП
источник
Когда я пытаюсь это в ghci, он жалуется parse error on input `='. Нужно ли использовать какой-либо флаг или другой?
Питер Тейлор
1
@PeterTaylor Вы не можете вставлять определения функций в ghci, как это. Самое простое, что вы можете сделать, это сохранить его asdf.hsи запустить ghci asdf.hs, тогда оттуда вы сможете получить доступf
Самое простое, что mniip
@PeterTaylor ghc --make -O3 [filename]. Вы также можете загрузить его в GHCI с:l [filename] но с учетом скомпилированных временных ограничений, вероятно, лучше. :)
Джонатан Ван Матре
@JonathanVanMatre, как видно из приведенного выше комментария, ghciзагружает файлы, указанные в его аргументах
mniip
Ах хорошо. Тем временем я запустил его с вашей тестовой средой и ghc. Ваш компьютер работает быстрее, чем мой, но он все равно находится в пределах критерия производительности на моем компьютере за 98 секунд.
Питер Тейлор
2

Javascript, 306 307 282B

function y(r){for(n=r-1,k=1;n;k++)if(p=[],e=[],c=0,P=s=1,!((x=k)%2|1==x)){while(x>1){for(f=x,j=2;j<=Math.sqrt(f);j++)if(f%j==0){f=j;break}f!=p[c-1]?(p.push(f),e.push(2),c++):e[c-1]++,x/=f}for(i=0;c>i;i++){if(p[i]>P+1){s=0;break}P*=(Math.pow(p[i],e[i])-1)/(p[i]-1)}s&&n--}return k-1}

250к в ок. 6s на моем ноутбуке.

Прокомментированный негольфовый код: http://jsfiddle.net/82xb9/3/ теперь с улучшенным сигма-тестированием и улучшенным условием (спасибо, комментарии)

Предварительно отредактированные версии: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/

александр-Brett
источник
Вопрос действительно требует функции или программы (у JS нет глаголов), поэтому вместо того, чтобы не считать первую строку, вам следует заключить вторую строку в объявлении функции и заменить заключительную k--;на return k-1. Хотя это немного увеличивает количество байтов, вы можете сэкономить несколько таких вещей, как замена p[i]>=P+2на p[i]>P+1(и, вероятно, удалив внутренний вызов функции и используя breakвместо него).
Питер Тейлор
Я думаю, что часть «test sigma» может быть переписана для размера и скорости: jsfiddle.net/3DTSa . Хотя это решение JS очень быстро, как есть.
user2846289