Hinweis: Diese Herausforderung wurde in der Sandbox veröffentlicht .

Einführung

Diese Herausforderung ist inspiriert von Putnam B1 aus dem Jahr 2009 , einem Problem in einem Mathematikwettbewerb für Studenten. Das Problem ist wie folgt:

Zeigen Sie, dass jede positive rationale Zahl als Quotient von Produkten von Fakultäten von (nicht notwendigerweise unterschiedlichen) Primzahlen geschrieben werden kann. Beispielsweise,

Herausforderung

Ihre Herausforderung besteht darin, zwei relativ positive Primzahlen zu verwenden, die den Zähler und den Nenner einer positiven rationalen Zahl (oder nur der rationalen Zahl selbst) als Eingabe darstellen, und zwei Listen (oder Arrays usw.) von Primzahlen auszugeben, damit Die eingegebene rationale Zahl ist gleich dem Verhältnis des Produkts der Fakultäten der Primzahlen in der ersten Liste zum Produkt der Fakultäten der Primzahlen in der zweiten Liste.

Anmerkungen

• Möglicherweise gibt es keine Primzahlen, die sowohl in der ersten als auch in der zweiten Liste enthalten sind. Ein Prime kann jedoch in jeder Liste so oft vorkommen, wie man möchte.
• Es kann davon ausgegangen werden, dass die Eingaben (uneingeschränkt) zwischen 1 und 65535 liegen. Es kann jedoch nicht davon ausgegangen werden, dass die Fakultäten der auszugebenden Zahlen in diesem Bereich liegen.

Beispiel für Ein- und Ausgabe

Hier sind Beispiele für legale Ein- und Ausgänge.

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

Bei den Eingaben (2,2), (0,3), (3,0), (3,6) und (1,65536) handelt es sich um unzulässige Eingaben (dh Ihr Programm muss sich auf diese nicht besonders verhalten ). Hier einige Beispiele für illegale Ausgaben:

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)

Wertung

Das ist Code-Golf , also gewinnt die niedrigste Punktzahl in Bytes!

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

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

Probieren Sie es online! Bearbeiten: 2 Bytes dank nur @ ASCII gespeichert. Gespeichert 1 2 3 4 dank @Emigna Bytes. (Ich muss nur noch eine speichern und bin auf die Hälfte meiner ursprünglichen Byteanzahl reduziert!) Erläuterung:

[       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 Bytes

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#]]&)

Probieren Sie es online!

Wie es funktioniert

Dies ist die Zusammensetzung zweier Funktionen. Der erste, der ungolfs zu

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

ist eine rekursive Funktion zur tatsächlichen Berechnung der gewünschten Faktorisierung. Speziell bei einer rationalen Eingabe xberechnen wir die Primzahlen, deren Fakultäten sich im Zähler und Nenner befinden sollen, und geben den Bruch mit allen diesen Primzahlen multipliziert zurück. (Zum Beispiel 10/9 = 2!*5!/(3!*3!*3!)kehren wir bei der Eingabe zurück 10/27 = 2*5/(3*3*3).)

Wir tun dies , indem bei jedem Schritt mit dem größten Primfaktor zu tun: wenn p ^e in der Faktorisierung von x auftritt, wir sicher , p zu machen! ^e tritt in der Fakultätsfaktorisierung auf und rekursiert auf x geteilt durch p! ^e .

(Früher hatte ich eine klügere Strategie, bei der große Zahlen vermieden werden, indem die vorherige Primzahl vor p betrachtet wird. Mathematica kann jedoch problemlos Zahlen bis 65521 verarbeiten, sodass es keinen Sinn macht. Die alte Version, die Sie im Verlauf finden können, ist viel schneller: auf meinem Computer dauerte es 0,05 Sekunden für Eingaben, die diese Version in 1,6 Sekunden verarbeitet.)

Die zweite Funktion wandelt die Ausgabe der ersten Funktion in Listen von Primzahlen um.

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

Für s=1(positive Potenzen) und s=-1(negative Potenzen) und für jeden Term {prime,exponent}in der Faktorisierung r@#wiederholen wir die Primzahl prime exponent*sviele Male.

Nicht konkurrierende Version mit 109 62 Bytes

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

Wie oben, aber anstatt die Ausgabe als Liste zu geben, wird die Ausgabe als Ausdruck ausgegeben, wobei der Operator ∇ (da er keine eingebaute Bedeutung hat) als Ersatz für Fakultäten verwendet wird. Somit gibt eine Eingabe von 10/9eine Ausgabe von (∇2*∇5)/(∇3)^3darzustellen (2!*5!)/(3!)^3.

Dies ist kürzer, da wir den zweiten Teil der Funktion überspringen.

+2 Bytes: Die Zuweisung f=Firstmuss an der richtigen Stelle erfolgen, damit Mathematica nicht verärgert wird.

-8 Bytes: Ein Fehler für Integer-Ausgaben wurde behoben, der den Code kürzer machte.

-15 Bytes: FactorIntegerGibt eine sortierte Ausgabe zurück, die wir nutzen können.

-46 Bytes: Wir müssen eigentlich nicht schlau sein.

Python 2, 220 202 195 183 Bytes

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

Probieren Sie es online! Bearbeiten: 18 25 Bytes dank @ Mr.Xcoder gespeichert. 12 Bytes dank @JonathanFrech eingespart.