Calcular números práticos

18

Definição

Um número inteiro positivo né um número prático (sequência OEIS A005153 ) se todos os números inteiros positivos menores puderem ser representados como somas de divisores distintos de n.

Por exemplo, 18é um número prático: seus divisores são 1, 2, 3, 6, 9 e 18, e os outros números inteiros positivos menores que 18 podem ser formados da seguinte forma:

 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

Mas 14não é um número prático: seus divisores são 1, 2, 7 e 14, e não há subconjunto deles que se soma a 4, 5, 6, 11, 12 ou 13.

Desafio

Escreva um programa, função ou verbo que tenha como entrada um número inteiro positivo xe retorne ou imprima o xésimo número prático, indexado de 1 para consistência com o OEIS. Seu código deve ser suficientemente eficiente para lidar com entradas de até 250000 em menos de dois minutos em um computador desktop razoável. (Nota: minha implementação de referência em Java gerencia 250000 em menos de 0,5 segundos, e minha implementação de referência em Python gerencia em 12 segundos).

Casos de teste

Input        Expected output
1            1
8            18
1000         6500
250000       2764000
1000000      12214770
3000000      39258256
Peter Taylor
fonte
(IMHO) isto pode ser mesmo mover interessante se o código mais rápido (por língua?) Ganha
Sarge Borsch
4
@SargeBorsch Então você verá tabelas de entradas de 250
mil
@belisarius bom ponto. mas acho que essa trapaça pode ser facilmente banida. Ou o problema pode exigir respostas corretas para qualquer número, mas então não haveria dificuldades ao fazê-lo em uma linguagem sem grandes números inteiros na biblioteca padrão ...: /
Sarge Borsch
Eu tenho uma otimização algorítmica em mente, mas com as regras atuais tenho preguiça de implementá-la: P
Sarge Borsch
4
@SargeBorsch, se você não quiser jogar seu código, sinta-se à vontade para enviá-lo para algo como gist.github.com e solte um link em um comentário aqui ou no chat. FWIW Prefiro código golf com restrições generosas de desempenho ao código mais rápido por dois motivos: primeiro, o comprimento do código é mais objetivamente mensurável; segundo, introduz um elemento de compensação: quais otimizações de velocidade podem ser deixadas de fora para encurtar o código sem prejudicar o desempenho?
Peter Taylor

Respostas:

5

J (99 caracteres)

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
)

Como a declaração do problema pede um "programa, função ou verbo ", alguém teve que fazer uma apresentação em J. As pessoas notarão que eu realmente não joguei golfe (!) Ou otimizei isso. Como as outras entradas, usei o teorema de Stewart, mencionado no link OEIS, para testar se cada número par é prático ou não.

Não tenho acesso imediato a um "computador desktop razoável" com o J instalado. No meu netbook de seis anos, f 250000calcula-se em 120,6 segundos, o que não leva menos de dois minutos, mas presumivelmente em qualquer computador um pouco mais razoável que isso termine no tempo.

Omar
fonte
6

Mathematica, 126 121 caracteres

Graças a belisarius.

Usando a fórmula na wikipedia.

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

Exemplos:

f[1]

1

f[8]

18

f[250000]

2764000

Demorou 70 anos para calcular f[250000]no meu computador.

alefalpha
fonte
3
Eu acho que você pode obter um desempenho melhor à custa de um caractere, ignorando inteiros ímpares
Dr. belisarius
1
Ao reduzir o código do envio do OEIS, você diminuiu a execução em 10 vezes. Apenas imaginando: "por que você acha que seu código é muito mais lento que o exemplo da OEIS?"
DavidC
@belisarius Sua sugestão diminui o tempo pela metade, conforme o esperado.
DavidC
2
O mesmo em 119 caracteres:(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Dr. belisarius
3

Haskell - 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..])!!)

Exemplos:

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

Aqui está um pequeno conjunto de testes (anexado ao acima):

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]

Resultados do teste após serem compilados com 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]
mniip
fonte
Quando eu tento isso no ghci, ele reclama parse error on input `='. Preciso usar uma bandeira ou outra?
Peter Taylor
1
@ PeterTaylor Você não pode colar definições de funções no ghci assim. Mais simples que você pode fazer é guardá-lo para asdf.hse executar ghci asdf.hs, em seguida, a partir daí você seria capaz de acessof
mniip
@PeterTaylor ghc --make -O3 [filename]. Você também pode carregá-lo no ghci, :l [filename]mas, considerando que as restrições de tempo compiladas provavelmente são as melhores. :)
Jonathan Van Matre 15/03
@JonathanVanMatre como visto no comentário acima, ghcicarrega arquivos especificado em seus argumentos
mniip
Ah ok. Enquanto isso, eu estou rodando com sua estrutura de teste e ghc. Seu computador é mais rápido que o meu, mas ainda está dentro do critério de desempenho do meu computador em 98 segundos.
Peter Taylor
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}

250k em aprox. 6s no meu laptop.

Código não golfe comentado: http://jsfiddle.net/82xb9/3/ agora com melhor teste de sigma e uma condição melhor se (comentários de agradecimento)

Versões de pré-edição: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/

alexander-brett
fonte
A pergunta solicita uma função ou programa (JS não possui verbos); portanto, em vez de não contar a primeira linha, você deve agrupar a segunda linha em uma declaração de função e substituir a final k--;por return k-1. Embora isso aumente levemente a contagem de bytes, você pode economizar alguns com coisas como substituir p[i]>=P+2por p[i]>P+1(e provavelmente removendo a chamada de função interna e usando uma breakalternativa).
Peter Taylor
Eu acho que a parte "testing sigma" pode ser reescrita para tamanho e velocidade: jsfiddle.net/3DTSa . Embora esta solução JS seja muito rápida como é.
user2846289