Definición
Un entero positivo n
es un número práctico (secuencia OEIS A005153 ) si todos los enteros positivos más pequeños se pueden representar como sumas de divisores distintos de n
.
Por ejemplo, 18
es un número práctico: sus divisores son 1, 2, 3, 6, 9 y 18, y los otros enteros positivos menores de 18 se pueden formar de la siguiente manera:
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
Pero 14
no es un número práctico: sus divisores son 1, 2, 7 y 14, y no hay un subconjunto de estos que se sume a 4, 5, 6, 11, 12 o 13.
Desafío
Escriba un programa, función o verbo que tome como entrada un número entero positivo x
y devuelva o imprima el número práctico número x , indexado desde 1 para mantener la coherencia con OEIS. Su código debe ser lo suficientemente eficiente como para manejar entradas de hasta 250000 en menos de dos minutos en una computadora de escritorio razonable. (Nota: mi implementación de referencia en Java maneja 250000 en menos de 0.5 segundos, y mi implementación de referencia en Python lo maneja en 12 segundos).
Casos de prueba
Input Expected output
1 1
8 18
1000 6500
250000 2764000
1000000 12214770
3000000 39258256
fuente
Respuestas:
J (99 caracteres)
Como el enunciado del problema solicita un "programa, función o verbo ", alguien tuvo que hacer una presentación J. J la gente notará que realmente no jugué golf (!) U optimicé esto. Al igual que las otras entradas, utilicé el teorema de Stewart, mencionado en el enlace OEIS, para probar si cada número par es práctico o no.
No tengo acceso a una "computadora de escritorio razonable" con J instalado. En mi netbook de seis años,
f 250000
calcula en 120.6 segundos, que no es menos de dos minutos, pero presumiblemente en cualquier computadora un poco más razonable, esto termina a tiempo.fuente
Mathematica,
126121 caracteresGracias a belisario.
Usando la fórmula en wikipedia.
Ejemplos:
Tomó 70 años para calcular
f[250000]
en mi computadora.fuente
(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Haskell - 329
Ejemplos:
Aquí hay un pequeño conjunto de pruebas (antes de lo anterior):
Resultados de la prueba después de ser compilado con
ghc -O3
:fuente
parse error on input `='
. ¿Necesito usar alguna bandera u otra?asdf.hs
y ejecutarloghci asdf.hs
, luego desde allí podrá accederf
ghc --make -O3 [filename]
. También podría cargarlo en ghci con,:l [filename]
pero dadas las limitaciones de tiempo compiladas, probablemente sea lo mejor. :)ghci
carga los archivos especificados en sus argumentosghc
. Su computadora es más rápida que la mía, pero todavía está dentro del criterio de rendimiento en mi computadora a los 98 segundos.Javascript,
306 307282B250k en aprox. 6s en mi laptop.
Código no comentado comentado: http://jsfiddle.net/82xb9/3/ ahora con mejores pruebas sigma y una mejor condición si (comentarios de agradecimiento)
Versiones de edición previa: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/
fuente
k--;
conreturn k-1
. Aunque eso aumenta ligeramente su recuento de bytes, puede ahorrar algunos con cosas como reemplazarp[i]>=P+2
conp[i]>P+1
(y probablemente eliminando la llamada a la función interna y utilizando unbreak
lugar).