Pseudofactorial

39

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. 1
  2. 2
  3. 6 6
  4. 24
  5. 120
  6. 720
  7. 5040

Pseudofactorial:

  1. 1
  2. 2
  3. 6 6
  4. 12
  5. 60 60
  6. 60 60
  7. 420
Tony Ruth
fuente
66
No estoy seguro de entender por qué 2y 6fueron eliminados de la lista de múltiplos. ¿Puede por favor aclarar las reglas?
Maltysen
2
@Mattysen, psuedofactorial (N) es el número más pequeño que tiene los números del 1 al N como factores (el mínimo común múltiplo de esos números). Esa es la definición técnica, pero la forma en que la escribí sugirió que es similar a un factorial.
Tony Ruth
44
¡Bienvenido a Programming Puzzles & Code Golf! Este es un buen primer desafío!
Alex A.
1
Su primer desafío llegó a la cima de HNQ. ¡Agradable!
Daniel M.

Respuestas:

19

Dyalog APL , 3 bytes

∧/⍳

APL late jalea

1 aunque argumento

∧/ LCM a través de

Adán
fuente
10
Ese interrobang es muy sexy.
shooqie
1
Oh hombre, venciste a Dennis ...
Mama Fun Roll
1
Impresionante, pero ¿cómo son estos 3 bytes ?
dejó de girar en sentido antihorario el
8

C (con x86), 52 bytes

d(n,k,b,t){for(b=k=1;b;++k)for(t=n,b=0;t;b+=k%t--);}

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:

main()
{
    printf("%d\n", d(7)); // outputs 420
}

No es obvio cómo devuelve un valor (no hay returndeclaración).

La convención de llamada para x86 dice que la función debe devolver su valor en el eaxregistro. Convenientemente, la instrucción de división idivespera su entrada eaxy genera el resultado en eax(cociente) y edx(resto). La última iteración se divide kpor1 , lo eaxque contendrá el valor correcto cuando salga la función.

Esto solo funciona con optimizaciones activadas (en modo de depuración, genera 421).

anatolyg
fuente
¿Cómo logras no declarar el tipo de n, k, b y t?
Tony Ruth
C tiene la regla default-int: todos los tipos omitidos son intpor 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; {...}
anatolyg
si se está aprovechando de una convención de llamadas, esta debería estar marcada "C (cdecl)" en lugar de solo "C"
Steve Cox
@SteveCox Both cdecly stdcallusa el mismo método para el valor de retorno, así que supongo que x86es suficiente
anatolyg
7

Haskell, 20 bytes

f x=foldr1 lcm[1..x]

Ejemplo de uso: map f [1..7] -> [1,2,6,12,60,60,420].

El lcmtruco en Haskell.

nimi
fuente
6

Python + SymPy, 45 bytes

import sympy
lambda n:sympy.lcm(range(1,n+1))

Bastante autoexplicativo.


Python 2, 57 54 bytes

i=r=input();exec't=r\nwhile r%i:r+=t\ni-=1;'*r;print r

Pruébalo en Ideone .

Cómo funciona

La entrada se almacena en las variables i y r .

execejecuta el siguiente código r veces.

t=r
while r%i:r+=t
i-=1

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.

Dennis
fuente
1
Sin usar bibliotecas o exectrucos 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 que lcm(x,y) = x*y/gcd(x,y).
Bakuriu
6

Python, 46 bytes

g=lambda n,c=0:n<1or(c%n<1)*c or g(n,c+g(n-1))

Buscando el múltiplo cde g(n-1)directamente. Pensé antes que este método encontraría erróneamente 0 como un múltiplo de cualquier cosa, pero el orcortocircuito o (c%n<1)*csaltará c==0también porque 0 es Falsey.


50 bytes:

g=lambda n,i=1:n<1or(i*n%g(n-1)<1)*i*n or g(n,i+1)

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ño i*nde nese también es un múltiplo deg(n-1) . Realmente lento.

Gracias a Dennis por 4 bytes mirando múltiplos de en nlugar de g(n-1).

xnor
fuente
5

J, 9 bytes

[:*./1+i.

Enfoque directo. Crea el rango de números [0, ..., n-1], luego agrega uno a cada uno y lo reduce usando el LCM.

Uso

   f =: [:*./1+i.
   f 7
420
millas
fuente
5

MATL , 4 bytes

:&Zm

Pruébalo en línea!

Explicación

:      % Take input N implicitly. Generate range [1 2 ... N]
&Zm    % LCM of the numbers in that array. Display implicitly
Luis Mendo
fuente
4

Mathematica, 13 bytes

LCM@@Range@#&
Monja permeable
fuente
¿No es esto equivalente a solo componer LCMy Rangecon @*?
Maltysen
1
LCMopera por elementos en una lista, que se pasaría Range, 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í como LCM@@Range@#&para 13 bytes funcionaría.
millas
3

Pyth - 8 bytes

Comprueba todos los números hasta encontrar uno que sea divisible por [1..N].

f!s%LTSQ

Test Suite .

Maltysen
fuente
3

Octava, 27 bytes

@(x)lcm(1,num2cell(1:x){:})

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 1y x( 1:x), los convierte en una matriz de celdas con num2cell. Luego, la {:}indexación crea una lista separada por comas que se pasa lcmcomo múltiples argumentos de entrada para calcular el mínimo común múltiplo. Un 1 siempre se pasa como el primer argumento lcmporque lcmsiempre necesita al menos dos argumentos de entrada.

Suever
fuente
1
¡Entonces lcmen Octave acepta más de 2 entradas! Interesante
Luis Mendo
@LuisMendo Yup 2+
Suever
3

MATLAB, 49 bytes

@(x)find(~any(bsxfun(@rem,1:prod(1:x),(1:x)')),1)
Suever
fuente
+1 parabsxfun
flawr
3

Perl 6 , 13 bytes

{[lcm] 1..$_}

Bloque de código anónimo que crea un Rango de 1 a la entrada (inclusive), y luego lo reduce con &infix:<lcm>.

Ejemplo:

#! /usr/bin/env perl6
use v6.c;

my &postfix:<p!> = {[lcm] 1..$_}

say 1p!; # 1
say 2p!; # 2
say 3p!; # 6
say 4p!; # 12
say 5p!; # 60
say 6p!; # 60
say 7p!; # 420

say 10000p!; # 5793339670287642968692270879...
# the result from this is 4349 digits long
Brad Gilbert b2gills
fuente
ideone.com/gR4SK5
Brad Gilbert b2gills
2

JavaScript (ES6), 92 88 80 74 69 bytes:

Gracias @ConorOBrien y @Neil

y=>(g=(a,b)=>b?g(b,a%b):a,[...Array(y)].map((_,i)=>y=y*++i/g(y,i)),y)
Pluma
fuente
b?g(b,a%b):aGuarda un byte.
Neil
y*++i/g(y,i)Guarda algunos bytes más.
Neil
1

05AB1E, 20 bytes

Lpvyi¹LÒN>¢àN>*ˆ}}¯P

Explicación

Lpv                    # for each item in isprime(range(1,N)): N=7 -> [0,1,1,0,1,0,1]
   yi                  # if prime
     ¹LÒN>¢            # count occurrences of the prime 
                         in the prime-factorization of range(1,N):
                         p=2 -> [0,1,0,2,0,1,0]
           àN>*ˆ       # add max occurrence of that prime multiplied by the prime 
                         to global array: N=7 -> [4,3,5,7]
                }}     # end if/loop
                  ¯P   # get product of global array

Pruébalo en línea

Emigna
fuente
1

Minkolang 0.15 , 12 bytes

Tengo dos soluciones de 12 bytes y las he incluido a ambas.

1n[i1+4$M]N.

Pruébalo aquí!

Explicación

1               Push 1
 n              Take number from input
  [             For loop that repeats n times
   i1+          Push loop counter + 1
      4$M       Pop b, a and push lcm(a,b)
         ]      Close for loop
          N.    Output as number and stop.

Tan sencillo como se pone.


11nLd[4$M]N.

Pruébalo aquí!

Explicación

11              Push two 1s
  n             Take number from input
   L            Pop b, a and push range from a to b, inclusive
    d           Duplicate top of stack (n)
     [4$M]      Pop b, a and push lcm(a,b), n times
          N.    Output as number and stop.

De esto se puede derivar una tercera solución: eliminar a 1y agregar a ddespués de la actual d. 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 [).

El'endia Starman
fuente
1

Rubí, 25 bytes.

g=->n{(1..n).reduce :lcm}

Rubí, 25 bytes.

g=->n{n<1?1:a[n-1].lcm n}
Peter Kagey
fuente
1
Hola y bienvenidos a PPCG! Gran primer post! No tiene que nombrar su función, por lo que puede eliminarla g=.
NoOneIsHere
Se permiten funciones anónimas.
Erik the Outgolfer
1

Lenguaje GameMaker, 60 bytes

for(b=k=1;b;++k){b=0for(t=argument0;t;b+=k mod t--)}return k

Basado en la lógica de la respuesta de anatolyg.

Timtech
fuente
1

PHP, 61 52 48 bytes

ahorró 9 bytes gracias a @ user59178, 4 bytes al fusionar los bucles.

La recurrencia en PHP es voluminosa debido a la functionpalabra clave; entonces uso iteración
Y con algunos "pequeños" trucos, ahora incluso vencí a JS de Arnauld .

while(++$k%++$i?$i>$argv[1]?0:$i=1:$k--);echo$k;

toma información del argumento de la línea de comando. Corre con-r .

Descompostura

while(++$k%++$i?    # loop $i up; if it does not divide $k
    $i>$argv[1]?0       # break if $i (smallest non-divisor of $k) is larger than input
    :$i=1               # while not, reset $i and continue loop with incremented $k
    :$k--);         # undo increment while $i divides $k
echo$k;         # print $k

sin golf

Eso es en realidad dos bucles en uno:

while($i<=$argv[1]) # loop while $i (smallest non-divisor of $k) is not larger than input
    for($k++,       # loop $k up from 1
        $i=0;$k%++$i<1;);   # loop $i up from 1 while it divides $k
echo$k;             # print $k

Nota: copiado de mi respuesta en el duplicado

Titus
fuente
1

Japt, 10 bytes

No hay LCM incorporado.

@õ e!vX}a1

Intentalo

Lanudo
fuente
0

Pyke, 3 bytes, sin competencia

S.L

Pruébalo aquí!

S   - range(1, input+1)
 .L - lowest_common_multiple(^)
Azul
fuente
0

Hoon , 67 bytes

|*
*
(roll (gulf 1 +<) |=({a/@ b/_1} (div (mul a b) d:(egcd a b))))

Crea la lista [1..n], dobla la lista con mcm. Desafortunadamente, el Hoon stdlib no tiene uno preconstruido que pueda usar: /

RenderSettings
fuente
0

𝔼𝕊𝕄𝕚𝕟, 7 caracteres / 9 bytes

Мū…⩤⁽1ï

Try it here (ES6 only).

Solo un LCM de rango inclusivo de 1 a entrada.

Mama Fun Roll
fuente
0

AWK, 42 bytes

{for(x=n=1;n<=$1;)if(x%n++){x++;n=1}$0=x}1

Uso de línea de comando:

awk '{for(x=n=2;n<=$1;)if(x%n++){x++;n=2}$0=x}1' <<< NUM

No vi una AWKsolución y ayer se publicó un duplicado de la pregunta, así que pensé en unirlo. Es una solución bastante lenta para 19mi caja o más grande, pero funciona.

Robert Benson
fuente
0

QBIC , 35 32 bytes

Esto me trajo aquí.

:{p=0[a|~q%b|p=1]]~p=0|_Xq\q=q+1

Explicación:

:        Get cmd line param as number 'a'
{        Start an infinite DO loop
p=0      Sets a flag that shows if divisions failed
[a|      FOR (b=1; b<=a; b++)
~q%b     IF 'q' (which starts at 1 in QBIC) is not cleanly divisible by 'b'
|p=1     THEN Set the flag
]]   Close the FOR loop and the IF, leave the DO open
~p=0     IF 'q' didn't get flagged
|_Xq     THEN quit, printing 'q'
\q=q+1   ELSE raise 'q', redo
         [DO Loop implicitly closed by QBIC]

Aquí hay una versión que deja de probar qcuando bno la divide limpiamente. Además, el orden de las pruebas b's en contra qse invierte en el supuesto de que los mayores b' s serán más difíciles de dividir por (toma 2, 3, 4por ejemplo: si %2=0, %4podría ser !0. Viceversa no tanto ...).

:{p=0[a,2,-1|~q%b|p=1┘b=2]]~p=0|_Xq\q=q+1
Steenbergh
fuente
0

8vo , 23 bytes

Código

1 ' lcm rot 2 swap loop

Este código deja pseudofactorial resultante en TOS

Uso y ejemplo

ok> 7 1 ' lcm rot 2 swap loop .
420

O más claramente

ok> : pseudofact 1 ' n:lcm rot 2 swap loop ;

ok> 7 pseudofact .
420
Chaos Manor
fuente