Remarque: ce défi a été publié sur le bac à sable .

introduction

Ce défi est inspiré par Putnam B1 2009 , un problème dans un concours de mathématiques de premier cycle. Le problème est le suivant:

Montrer que tout nombre rationnel positif peut être écrit comme un quotient de produits de factorielles de nombres premiers (pas nécessairement distincts). Par exemple,

Défi

Votre défi est de prendre une paire d'entiers positifs relativement premiers, représentant le numérateur et le dénominateur d'un nombre rationnel positif (ou juste le nombre rationnel lui-même) en entrée, et de sortir deux listes (ou tableaux, etc.) de nombres premiers afin que le nombre rationnel entré est égal au rapport du produit des factorielles des nombres premiers dans la première liste au produit des factorielles des nombres premiers dans la deuxième liste.

Remarques

• Il peut ne pas y avoir de nombres premiers contenus à la fois dans la première liste et dans la deuxième liste; cependant, un nombre premier peut apparaître autant de fois que l'on souhaite dans l'une ou l'autre liste.
• Les entrées peuvent être supposées être chacune (sans restriction) entre 1 et 65535; cependant, on ne peut pas supposer que les factorielles des nombres que vous devrez produire seront dans cette plage.

Exemple d'entrée et de sortie

Voici des exemples d'entrées et de sorties légales.

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],[]

Les entrées (2,2), (0,3), (3,0), (3,6) et (1,65536) sont des entrées illégales (c'est-à-dire que votre programme n'a pas besoin de se comporter d'une manière particulière sur elles ). Voici quelques exemples de sorties illégales:

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)

Notation

C'est le code-golf , donc le score le plus bas en octets gagne!

05AB1E , 54 53 48 46 40 35 33 32 28 octets

[D¿÷Z#DÓ€gZD<ØŠQ*DˆR!*]¯øεʒĀ

Essayez-le en ligne! Edit: sauvé 2 octets grâce à @ ASCII uniquement. Sauvé 1 2 3 4 octets grâce à @Emigna. (Je n'ai besoin d'en enregistrer qu'un de plus et je suis à la moitié de mon nombre d'octets d'origine!) Explication:

[       Begin an infinite loop
D¿÷     Reduce to lowest terms
Z#      Exit the loop if the (largest) value is 1
DÓ€g    Find the index of the largest prime factor of each value
Z       Take the maximum
D<ØŠ    Convert index back to prime and save for later
Q       Convert to an pair of which value had the largest prime factor
*       Convert to an pair with that prime factor and zero
Dˆ      Save the pair in the global array for later
R!*     Multiply the other input value by the factorial of the prime
]       End of infinite loop
¯ø      Collect all the saved primes
εʒĀ     Forget all the saved 0s

Mathematica, 175 177 169 154 108 octets

Join@@@Table[x[[1]],{s,{1,-1}},{x,r@#},x[[2]]s]&@*(If[#==1,1,{p,e}=Last@(r=FactorInteger)@#;p^e#0[p!^-e#]]&)

Essayez-le en ligne!

Comment ça fonctionne

C'est la composition de deux fonctions. Le premier, qui dégoûte pour

If[# == 1,
  1,
  {p,e} = Last[FactorInteger[#]];
  p^e * #0[p!^-e * #]
]&

est une fonction récursive pour calculer réellement la factorisation souhaitée. Plus précisément, étant donné une entrée rationnelle x, nous calculons les nombres premiers dont les factorielles devraient être au numérateur et au dénominateur, et nous retournons la fraction avec tous ces nombres premiers multipliés ensemble. (Par exemple, en entrée 10/9 = 2!*5!/(3!*3!*3!), nous revenons 10/27 = 2*5/(3*3*3).)

Nous le faisons en traitant le plus grand facteur premier à chaque étape: si p ^e se produit dans la factorisation de x, nous nous assurons que p! ^e se produit dans la factorisation factorielle, et récurrence sur x divisé par p! ^e .

(Plus tôt, j'avais une stratégie plus intelligente qui évite les grands nombres en regardant le nombre premier précédent avant p, mais Mathematica peut gérer des nombres aussi grands que 65521! Facilement, donc cela ne sert à rien. L'ancienne version que vous pouvez trouver dans l'historique est beaucoup plus rapide: sur mon ordinateur, il a fallu 0,05 seconde sur les entrées que cette version gère en 1,6 seconde.)

La deuxième fonction transforme la sortie de la première fonction en listes de nombres premiers.

Join @@@ 
  Table[x[[1]],
    {s,{1,-1}},
    {x,FactorInteger[#]},
    x[[2]]*s
  ]&

Pour s=1(puissances positives) et s=-1(puissances négatives), et pour chaque terme {prime,exponent}de la factorisation r@#, nous répétons le nombre premier prime exponent*splusieurs fois.

Version sans concurrence avec 109 62 octets

If[#==1,∇1=1,{p,e}=Last@FactorInteger@#;(∇p)^e#0[p!^-e#]]&

Comme ci-dessus, mais au lieu de donner la sortie sous forme de liste, donne la sortie sous forme d'expression, en utilisant l'opérateur ∇ (car il n'a pas de signification intégrée) comme substitut pour les factorielles. Ainsi, une entrée de 10/9donne une sortie de (∇2*∇5)/(∇3)^3à représenter (2!*5!)/(3!)^3.

Ceci est plus court car nous sautons la deuxième partie de la fonction.

+2 octets: l'affectation f=Firstdoit être effectuée au bon endroit pour empêcher Mathematica de se fâcher.

-8 octets: correction d'un bug pour les sorties entières, ce qui raccourcissait le code.

-15 octets: FactorIntegerrenvoie une sortie triée, dont nous pouvons tirer parti.

-46 octets: nous n'avons pas vraiment besoin d'être intelligents.

Python 2, 220 202 195 183 octets

g=lambda a,b:a and g(b%a,a)or b;n,d=input();m=c=()
while n+d>2:
 t=n*d;f=p=2
 while t>p:
	if t%p:p+=1;f*=p
	else:t/=p
 if n%p:c+=p,;n*=f
 else:m+=p,;d*=f
 t=g(n,d);n/=t;d/=t
print m,c

Essayez-le en ligne! Edit: 18 25 octets enregistrés grâce à @ Mr.Xcoder. 12 octets enregistrés grâce à @JonathanFrech.