Nota: este desafío ha sido publicado en el sandbox .
Introducción
Este desafío está inspirado en el Putnam B1 2009 , un problema en una competencia de pregrado en matemáticas. El problema es el siguiente:
Demuestre que cada número racional positivo puede escribirse como un cociente de productos de factoriales de primos (no necesariamente distintos). Por ejemplo,
Desafío
Su desafío es tomar un par de enteros positivos relativamente primos, que representan el numerador y el denominador de un número racional positivo (o solo el número racional en sí) como entrada, y generar dos listas (o matrices, etc.) de números primos para que el número racional ingresado es igual a la razón del producto de los factoriales de los primos en la primera lista al producto de los factoriales de los primos en la segunda lista.
Notas
- Puede que no haya primos que contengan tanto en la primera lista como en la segunda lista; sin embargo, una prima puede aparecer tantas veces como se desee en cualquiera de las listas.
- Se puede suponer que las entradas son (no estrictamente) entre 1 y 65535; sin embargo, no se puede suponer que los factores de los números que necesitará generar estarán en este rango.
Ejemplo de entrada y salida
Aquí hay ejemplos de entradas y salidas legales.
input=>output
10,9 => [2,5],[3,3,3]
2,1 => [2],[]
3,1 => [3],[2]
1,5 => [2,3,2],[5] (elements of a list may be in any order)
3,2 => [3],[2,2]
6,1 => [3],[]
Las entradas (2,2), (0,3), (3,0), (3,6) y (1,65536) son entradas ilegales (es decir, su programa no necesita comportarse de manera particular en ellas ) Aquí hay algunos ejemplos de resultados ilegales:
1,2 => [2],[2,2] (2 is in both returned lists)
5,2 => [5],[2,4] (4 is not prime)
2,1 => [2],[1] (1 is not prime either)
3,2 => [3],[2] (3!/2! = 3, not 3/2)
Puntuación
Este es el código de golf , por lo que gana la puntuación más baja en bytes.
fuente
10/9
=[2*5]/[3*3]
=[(2!/1!) * (5!/4!)] / [(3!/2!) * (3!/2!)]
=[2! * 5! * 2! * 2!] / [3! * 3! * 1! * 4!]
=(2! * 2! * 2! *5!) / (3! * 3! * 4!)
.10/9
lugar de un par de números10
y9
?Respuestas:
05AB1E ,
545348464035333228 bytesPruébalo en línea! Editar: Guardado 2 bytes gracias a @ ASCII-only. Guardado
1234 bytes gracias a @Emigna. (¡Solo necesito guardar uno más y tengo la mitad de mi recuento de bytes original!) Explicación:fuente
¦D
Mathematica,
175177169154108 bytesPruébalo en línea!
Cómo funciona
Esta es la composición de dos funciones. El primero, que se deshace de
es una función recursiva para calcular realmente la factorización deseada. Específicamente, dada una entrada racional
x
, calculamos los primos cuyos factoriales deben estar en el numerador y el denominador, y devolvemos la fracción con todos esos primos multiplicados juntos. (Por ejemplo, en la entrada10/9 = 2!*5!/(3!*3!*3!)
, volvemos10/27 = 2*5/(3*3*3)
).Hacemos esto al tratar con el factor primo más grande en cada paso: si p e ocurre en la factorización de x, ¡nos aseguramos de que p! e ocurre en la factorización factorial, y recurse en x dividido por p! e .
(Anteriormente, tenía una estrategia más inteligente que evita los números grandes mirando el número primo anterior antes de p, ¡pero Mathematica puede manejar números tan grandes como 65521! Fácilmente, por lo que no tiene sentido. La versión anterior que puedes encontrar en la historia es mucho más rápido: en mi computadora, tardé 0.05 segundos en las entradas que esta versión maneja en 1.6 segundos).
La segunda función convierte la salida de la primera función en listas de primos.
Para
s=1
(potencias positivas) ys=-1
(potencias negativas), y para cada término{prime,exponent}
en la factorizaciónr@#
, repetimos el número primoprime
exponent*s
muchas veces.Versión sin competencia con
10962 bytesIgual que el anterior, pero en lugar de dar salida como una lista, da salida como una expresión, utilizando el operador ∇ (porque no tiene un significado incorporado) como sustituto de los factoriales. Por lo tanto, una entrada de
10/9
da una salida de(∇2*∇5)/(∇3)^3
representar(2!*5!)/(3!)^3
.Esto es más corto porque omitimos la segunda parte de la función.
+2 bytes: la tarea
f=First
debe hacerse en el lugar correcto para evitar que Mathematica se enoje.-8 bytes: se corrigió un error para las salidas enteras, lo que en realidad acortaba el código.
-15 bytes:
FactorInteger
devuelve una salida ordenada, que podemos aprovechar.-46 bytes: en realidad no necesitamos ser inteligentes.
fuente
Python 2,
220202195183 bytesPruébalo en línea! Editar: Guardado
1825 bytes gracias a @ Mr.Xcoder. Guardado 12 bytes gracias a @JonathanFrech.fuente