Nota: este desafio foi publicado na sandbox .
Introdução
Esse desafio é inspirado em 2009 Putnam B1 , um problema em um concurso de graduação em matemática. O problema é o seguinte:
Mostre que todo número racional positivo pode ser escrito como um quociente de produtos de fatoriais de primos (não necessariamente distintos). Por exemplo,
Desafio
Seu desafio é pegar um par de números inteiros positivos relativamente primos, representando o numerador e o denominador de um número racional positivo (ou apenas o próprio número racional) como entrada, e gerar duas listas (ou matrizes, etc.) de números primos para que o número racional inserido é igual à razão entre o produto dos fatoriais dos primos na primeira lista e o produto dos fatoriais dos primos na segunda lista.
Notas
- Pode não haver números primos contidos na primeira e na segunda lista; no entanto, um primo pode aparecer quantas vezes se desejar em qualquer lista.
- As entradas podem ser assumidas para cada uma estar (sem estrita) entre 1 e 65535; no entanto, não se pode presumir que os fatoriais dos números que você precisará fornecer estarão nesse intervalo.
Exemplo de entrada e saída
Aqui estão exemplos de entradas e saídas legais.
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],[]
As entradas (2,2), (0,3), (3,0), (3,6) e (1.65536) são entradas ilegais (ou seja, seu programa não precisa se comportar de nenhuma maneira específica nelas ) Aqui estão alguns exemplos de saídas ilegais:
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)
Pontuação
Isso é código-golfe , então a pontuação mais baixa em bytes vence!
fonte
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
e não como um par de números10
e9
?Respostas:
05AB1E ,
545348464035333228 bytesExperimente online! Editar: salvou 2 bytes graças a @ ASCII-only. Guardado
1234 bytes graças a @Emigna. (Só preciso salvar mais uma e reduzi para metade a minha contagem de bytes original!) Explicação:fonte
¦D
Mathematica,
175177169 169154108 bytesExperimente online!
Como funciona
Esta é a composição de duas funções. O primeiro, que os incrédulos
é uma função recursiva para realmente calcular a fatoração desejada. Especificamente, dada uma entrada racional
x
, calculamos os primos cujos fatoriais devem estar no numerador e denominador e retornamos a fração com todos esses primos multiplicados juntos. (Por exemplo, na entrada10/9 = 2!*5!/(3!*3!*3!)
, retornamos10/27 = 2*5/(3*3*3)
.)Fazemos isso lidando com o maior fator primo em cada etapa: se p e ocorre na fatoração de x, garantimos que p! e ocorre na fatoração fatorial e recursiva em x dividido por p! e .
(Antes, eu tinha uma estratégia mais inteligente que evita grandes números olhando o número primo anterior antes de p, mas o Mathematica pode lidar com números tão grandes quanto 65521! Facilmente, então não faz sentido. A versão antiga que você pode encontrar na história é muito mais rápido: no meu computador, foram necessários 0,05 segundos nas entradas que esta versão manipula em 1,6 segundos.)
A segunda função transforma a saída da primeira função em listas de números primos.
Para
s=1
(potências positivas) es=-1
(potências negativas), e para cada termo{prime,exponent}
na fatoraçãor@#
, repetimos o número primoprime
exponent*s
muitas vezes.Versão não competidora com
10962 bytesO mesmo que acima, mas em vez de fornecer a saída como uma lista, fornece a saída como uma expressão, usando o operador ((porque não possui significado interno) como substituto de fatoriais. Assim, uma entrada de
10/9
fornece uma saída de(∇2*∇5)/(∇3)^3
para representar(2!*5!)/(3!)^3
.Isso é mais curto porque pulamos a segunda parte da função.
+2 bytes: a atribuição
f=First
deve ser feita no lugar certo para evitar que o Mathematica fique chateado.-8 bytes: corrigido um bug para saídas inteiras, o que na verdade tornava o código mais curto.
-15 bytes:
FactorInteger
retorna a saída classificada, da qual podemos tirar proveito.-46 bytes: na verdade, não precisamos ser espertos.
fonte
Python 2,
220202195183 bytesExperimente online! Edit: Salvo
1825 bytes graças a @ Mr.Xcoder. Economizou 12 bytes graças a @JonathanFrech.fonte