Hay un número bastante curioso que aparece a veces en problemas matemáticos o enigmas. El pseudofactorial (N) es el mínimo común (es decir, el más bajo) de los números del 1 al N; en otras palabras, es el número más bajo que tiene todos los números del 1 al N como factores.
Por ejemplo pseudofactorial (7) = 3 * 4 * 5 * 7, que es lo mismo que 7! excepto que 2 y 6 se han eliminado porque están contenidos en otros términos.
Escriba un programa para calcular pseudofactorial (N) y, como siempre, gana el código más corto.
Aquí hay una breve lista para su uso. Se pueden encontrar más casos de prueba en el OEIS bajo A003418 .
Factorial:
- 1
- 2
- 6 6
- 24
- 120
- 720
- 5040
Pseudofactorial:
- 1
- 2
- 6 6
- 12
- 60 60
- 60 60
- 420
code-golf
math
number-theory
factorial
Tony Ruth
fuente
fuente
2
y6
fueron eliminados de la lista de múltiplos. ¿Puede por favor aclarar las reglas?Respuestas:
Dyalog APL , 3 bytes
APL late jalea ‽
⍳
1 aunque argumento∧/
LCM a través defuente
Jalea , 4 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
C (con x86), 52 bytes
Comprueba los números del 1 en adelante. Para cada número, lo divide por todos los números desde n hasta 1, y suma el resto. Se detiene cuando la suma es 0.
Uso:
No es obvio cómo devuelve un valor (no hay
return
declaración).La convención de llamada para x86 dice que la función debe devolver su valor en el
eax
registro. Convenientemente, la instrucción de divisiónidiv
espera su entradaeax
y genera el resultado eneax
(cociente) yedx
(resto). La última iteración se dividek
por1
, loeax
que contendrá el valor correcto cuando salga la función.Esto solo funciona con optimizaciones activadas (en modo de depuración, genera
421
).fuente
int
por defecto (incluido el valor de retorno). Funciona para argumentos de función si se declaran utilizando la sintaxis llamada "estilo antiguo". La declaración con tipos explícitamente definidos seríaint d(n,k,b,t) int n,k,b,t; {...}
cdecl
ystdcall
usa el mismo método para el valor de retorno, así que supongo quex86
es suficienteHaskell, 20 bytes
Ejemplo de uso:
map f [1..7]
->[1,2,6,12,60,60,420]
.El
lcm
truco en Haskell.fuente
Python + SymPy, 45 bytes
Bastante autoexplicativo.
Python 2,
5754 bytesPruébalo en Ideone .
Cómo funciona
La entrada se almacena en las variables i y r .
exec
ejecuta el siguiente código r veces.Si bien i varía de r a 1 , agregamos el valor inicial de r (almacenado en t ) tantas veces como sea necesario para r para crear un múltiplo de i . El resultado es, obviamente, un múltiplo de t .
El valor final de r es, por lo tanto, un múltiplo de todos los enteros en el rango [1, ..., n] , donde n es la entrada.
fuente
exec
trucos de terceros, existe una solución de 78 bytes:from fractions import*;lambda n:reduce(lambda x,y:x*y/gcd(x,y),range(1,n+1),1)
utiliza el hecho de quelcm(x,y) = x*y/gcd(x,y)
.Python, 46 bytes
Buscando el múltiplo
c
deg(n-1)
directamente. Pensé antes que este método encontraría erróneamente 0 como un múltiplo de cualquier cosa, pero elor
cortocircuito o(c%n<1)*c
saltarác==0
también porque 0 es Falsey.50 bytes:
Como la solución de Dennis , pero como una función recursiva. Después de calcular
g(n-1)
, busca el múltiplo más pequeñoi*n
den
ese también es un múltiplo deg(n-1)
. Realmente lento.Gracias a Dennis por 4 bytes mirando múltiplos de en
n
lugar deg(n-1)
.fuente
J, 9 bytes
Enfoque directo. Crea el rango de números
[0, ..., n-1]
, luego agrega uno a cada uno y lo reduce usando el LCM.Uso
fuente
MATL , 4 bytes
Pruébalo en línea!
Explicación
fuente
Mathematica, 13 bytes
fuente
LCM
yRange
con@*
?LCM
opera por elementos en una lista, que se pasaríaRange
, lo que significa que esto solo devolvería el mcm ( x ) para x de 1 a n . Además, hay una falta&
que cerraría la función anónima. Algo así comoLCM@@Range@#&
para 13 bytes funcionaría.Julia, 11 bytes
Pruébalo en línea!
fuente
Pyth - 8 bytes
Comprueba todos los números hasta encontrar uno que sea divisible por
[1..N]
.Test Suite .
fuente
Octava, 27 bytes
Crea una función anónima que se puede invocar como
ans(N)
.Demo en línea
Explicación
Esta solución crea una lista de todos los números entre
1
yx
(1:x
), los convierte en una matriz de celdas connum2cell
. Luego, la{:}
indexación crea una lista separada por comas que se pasalcm
como múltiples argumentos de entrada para calcular el mínimo común múltiplo. Un 1 siempre se pasa como el primer argumentolcm
porquelcm
siempre necesita al menos dos argumentos de entrada.fuente
lcm
en Octave acepta más de 2 entradas! InteresanteMATLAB, 49 bytes
fuente
bsxfun
Perl 6 , 13 bytes
Bloque de código anónimo que crea un Rango de 1 a la entrada (inclusive), y luego lo reduce con
&infix:<lcm>
.Ejemplo:
fuente
JavaScript (ES6),
9288807469 bytes:Gracias @ConorOBrien y @Neil
fuente
b?g(b,a%b):a
Guarda un byte.y*++i/g(y,i)
Guarda algunos bytes más.05AB1E, 20 bytes
Explicación
Pruébalo en línea
fuente
Minkolang 0.15 , 12 bytes
Tengo dos soluciones de 12 bytes y las he incluido a ambas.
Pruébalo aquí!
Explicación
Tan sencillo como se pone.
Pruébalo aquí!
Explicación
De esto se puede derivar una tercera solución: eliminar a
1
y agregar ad
después de la actuald
. En ambos casos, el número adicional es necesario porque el bucle for se ejecuta demasiadas veces, y hacer que se ejecute una vez menos requiere dos bytes (1-
justo antes del[
).fuente
Rubí, 25 bytes.
Rubí, 25 bytes.
fuente
g=
.Lenguaje GameMaker, 60 bytes
Basado en la lógica de la respuesta de anatolyg.
fuente
PHP,
615248 bytesahorró 9 bytes gracias a @ user59178, 4 bytes al fusionar los bucles.
La recurrencia en PHP es voluminosa debido a la
function
palabra clave; entonces uso iteraciónY con algunos "pequeños" trucos, ahora incluso vencí a JS de Arnauld .
toma información del argumento de la línea de comando. Corre con
-r
.Descompostura
sin golf
Eso es en realidad dos bucles en uno:
Nota: copiado de mi respuesta en el duplicado
fuente
Japt, 10 bytes
No hay LCM incorporado.
Intentalo
fuente
Pyke, 3 bytes, sin competencia
Pruébalo aquí!
fuente
Hoon , 67 bytes
Crea la lista
[1..n]
, dobla la lista con mcm. Desafortunadamente, el Hoon stdlib no tiene uno preconstruido que pueda usar: /fuente
𝔼𝕊𝕄𝕚𝕟, 7 caracteres / 9 bytes
Try it here (ES6 only).
Solo un LCM de rango inclusivo de 1 a entrada.
fuente
AWK, 42 bytes
Uso de línea de comando:
No vi una
AWK
solución y ayer se publicó un duplicado de la pregunta, así que pensé en unirlo. Es una solución bastante lenta para19
mi caja o más grande, pero funciona.fuente
QBIC ,
3532 bytesEsto me trajo aquí.
Explicación:
Aquí hay una versión que deja de probar
q
cuandob
no la divide limpiamente. Además, el orden de las pruebasb
's en contraq
se invierte en el supuesto de que los mayoresb
' s serán más difíciles de dividir por (toma2
,3
,4
por ejemplo: si%2=0
,%4
podría ser!0
. Viceversa no tanto ...).fuente
Axioma, 35 bytes
código de prueba y resultados
Acabo de hacer la solución de Encontrar el entero positivo más pequeño que tiene todos los enteros de 1 a n como factores porque usted dice que es duplicado, lo publico aquí
fuente
Pari / GP , 14 bytes
Pruébalo en línea!
fuente
8vo , 23 bytes
Código
Este código deja pseudofactorial resultante en TOS
Uso y ejemplo
O más claramente
fuente