Calcular números prácticos

18

Definición

Un entero positivo nes 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, 18es 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 14no 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 xy 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
Peter Taylor
fuente
(En mi humilde opinión), esto puede ser incluso interesante si gana el código más rápido (¿por idioma?)
Nombre para mostrar
44
@SargeBorsch Entonces verás tablas de 250,000 entradas en todas las respuestas
Dr. belisarius
@belisarius buen punto. pero creo que ese engaño se puede prohibir fácilmente. O el problema puede requerir respuestas correctas para cualquier número, pero luego habría dificultades al hacerlo en un idioma sin grandes números enteros en la biblioteca estándar ...: /
Nombre para mostrar
Tengo en mente una optimización algorítmica, pero con las reglas actuales soy demasiado vago para implementarla: P
Nombre para mostrar
44
@SargeBorsch, si no quieres jugar golf, no dudes en subirlo a algo como gist.github.com y dejar un enlace en un comentario aquí o en el chat. FWIW Prefiero el código de golf con generosas restricciones de rendimiento al código más rápido por dos razones: en primer lugar, la longitud del código es más objetivamente medible; En segundo lugar, introduce un elemento de compensación: ¿qué optimizaciones de velocidad se pueden omitir para acortar el código sin arruinar el rendimiento?
Peter Taylor

Respuestas:

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 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 250000calcula 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.

Omar
fuente
6

Mathematica, 126 121 caracteres

Gracias a belisario.

Usando la fórmula en wikipedia.

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

Ejemplos:

f[1]

1

f[8]

18 años

f[250000]

2764000

Tomó 70 años para calcular f[250000]en mi computadora.

alephalpha
fuente
3
Creo que puede obtener un mejor rendimiento a expensas de un
personaje
1
Al reducir el código del envío de OEIS, redujo la ejecución 10 veces. Solo me pregunto, "¿por qué crees que tu código se ejecuta mucho más lento que el ejemplo OEIS?"
DavidC
@belisarius Su sugerencia reduce el tiempo a la mitad, como se esperaba.
DavidC
2
Lo mismo en 119 caracteres:(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Dr. belisario
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..])!!)

Ejemplos:

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

Aquí hay un pequeño conjunto de pruebas (antes de lo anterior):

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 de la prueba después de ser compilado con 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
fuente
Cuando intento esto en ghci, se queja parse error on input `='. ¿Necesito usar alguna bandera u otra?
Peter Taylor
1
@PeterTaylor No puede pegar definiciones de funciones en ghci como ese. Lo más simple que puede hacer es guardarlo asdf.hsy ejecutarlo ghci asdf.hs, luego desde allí podrá accederf
mniip
@PeterTaylor 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. :)
Jonathan Van Matre
@JonathanVanMatre como se ve en el comentario anterior, ghcicarga los archivos especificados en sus argumentos
mniip
Ah ok Mientras tanto, lo tengo funcionando con su marco de prueba y ghc. 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.
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 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/

alexander-brett
fuente
La pregunta pide una función o programa (JS no tiene verbos), por lo que, en lugar de no contar la primera línea, debe ajustar la segunda línea en una declaración de función y reemplazar la final k--;con return k-1. Aunque eso aumenta ligeramente su recuento de bytes, puede ahorrar algunos con cosas como reemplazar p[i]>=P+2con p[i]>P+1(y probablemente eliminando la llamada a la función interna y utilizando un breaklugar).
Peter Taylor
Creo que la parte "prueba sigma" se puede reescribir tanto para el tamaño como para la velocidad: jsfiddle.net/3DTSa . Aunque esta solución JS es muy rápida como es.
user2846289