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 14
nã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 x
e 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
fonte
Respostas:
J (99 caracteres)
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 250000
calcula-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.fonte
Mathematica,
126121 caracteresGraças a belisarius.
Usando a fórmula na wikipedia.
Exemplos:
Demorou 70 anos para calcular
f[250000]
no meu computador.fonte
(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Haskell - 329
Exemplos:
Aqui está um pequeno conjunto de testes (anexado ao acima):
Resultados do teste após serem compilados com
ghc -O3
:fonte
parse error on input `='
. Preciso usar uma bandeira ou outra?asdf.hs
e executarghci asdf.hs
, em seguida, a partir daí você seria capaz de acessof
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. :)ghci
carrega arquivos especificado em seus argumentosghc
. Seu computador é mais rápido que o meu, mas ainda está dentro do critério de desempenho do meu computador em 98 segundos.Javascript,
306 307282B250k 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/
fonte
k--;
porreturn k-1
. Embora isso aumente levemente a contagem de bytes, você pode economizar alguns com coisas como substituirp[i]>=P+2
porp[i]>P+1
(e provavelmente removendo a chamada de função interna e usando umabreak
alternativa).