Uwaga: to wyzwanie zostało opublikowane w piaskownicy .
Wprowadzenie
Wyzwanie to jest inspirowane przez 2009 Putnam B1 , problem w konkursie matematyki na studiach licencjackich. Problem jest następujący:
Pokaż, że każdą dodatnią liczbę wymierną można zapisać jako iloraz iloczynów silni (niekoniecznie odrębnych) liczb pierwszych. Na przykład,
Wyzwanie
Wyzwanie polega na przyjęciu pary względnie pierwszych liczb całkowitych dodatnich reprezentujących licznik i mianownik dodatniej liczby wymiernej (lub po prostu samej liczby wymiernej) jako danych wejściowych i wyprowadzenie dwóch list (lub tablic itp.) Liczb pierwszych, tak aby wprowadzona liczba wymierna jest równa stosunkowi iloczynu silni liczb pierwszych z pierwszej listy do iloczynu silni liczb pierwszych z drugiej listy.
Notatki
- Może nie być żadnych liczb pierwszych, które zawierałyby zarówno na pierwszej liście, jak i na drugiej liście; liczba pierwsza może jednak pojawiać się tyle razy, ile zechce się na każdej liście.
- Można przyjąć, że dane wejściowe wynoszą (bez ograniczeń) między 1 a 65535; nie można jednak założyć, że silnia liczb, które trzeba wyprowadzić, będzie w tym zakresie.
Przykład wejścia i wyjścia
Oto przykłady legalnych danych wejściowych i wyjściowych.
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],[]
Dane wejściowe (2,2), (0,3), (3,0), (3,6) i (1 65536) są nielegalnymi danymi wejściowymi (tzn. Twój program nie musi zachowywać się w żaden szczególny sposób na nich ). Oto kilka przykładów nielegalnych wyników:
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)
Punktacja
To jest golf golfowy , więc wygrywa najniższy wynik w bajtach!
źródło
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
a nie parę liczb10
i9
?Odpowiedzi:
05AB1E ,
545348464035333228 bajtówWypróbuj online! Edycja: Zapisano 2 bajty dzięki tylko @ ASCII. Zaoszczędź
1234 bajty dzięki @Emigna. (Muszę uratować jeszcze tylko jeden i jestem o połowę mniejszy od oryginalnej liczby bajtów!) Objaśnienie:źródło
¦D
Mathematica,
175177169154108 bajtówWypróbuj online!
Jak to działa
Jest to kompozycja dwóch funkcji. Pierwszy, który nie lubi
jest funkcją rekurencyjną do faktycznego obliczania pożądanej faktoryzacji. Konkretnie, biorąc pod uwagę racjonalne dane wejściowe
x
, obliczamy liczby pierwsze, których silnia powinna znajdować się w liczniku i mianowniku, i zwracamy ułamek wraz ze wszystkimi tymi liczbami pierwotnymi pomnożonymi razem. (Na przykład10/9 = 2!*5!/(3!*3!*3!)
wracamy10/27 = 2*5/(3*3*3)
).Robimy to, radząc sobie z największym czynnikiem pierwszym na każdym etapie: jeśli p e występuje w rozkładzie x, upewniamy się, że p! e występuje w rozkładzie na czynniki i powtarza się na x podzielone przez p! e .
(Wcześniej miałem bardziej sprytną strategię, która pozwala uniknąć dużych liczb, patrząc na poprzednią liczbę pierwszą przed p, ale Mathematica może łatwo obsługiwać liczby tak duże jak 65521 !, więc nie ma sensu. Stara wersja, którą można znaleźć w historii, to znacznie szybciej: na moim komputerze zajęło to 0,05 sekundy na wejściach obsługiwanych przez tę wersję w 1,6 sekundy.)
Druga funkcja zamienia wynik pierwszej funkcji w listy liczb pierwszych.
Dla
s=1
(mocy dodatnich) is=-1
(mocy ujemnych) oraz dla każdego terminu{prime,exponent}
w rozkładzie na czynnikir@#
powtarzamy liczbę pierwsząprime
exponent*s
wiele razy.Wersja niekonkurencyjna z
10962 bajtamiTo samo co powyżej, ale zamiast dać wynik jako listę, daje wynik jako wyrażenie, używając operatora ∇ (ponieważ nie ma wbudowanego znaczenia) jako stand-in dla silni. Tak więc wejście
10/9
daje wyjście(∇2*∇5)/(∇3)^3
do reprezentowania(2!*5!)/(3!)^3
.Jest to krótsze, ponieważ pomijamy drugą część funkcji.
+2 bajty: zadanie
f=First
należy wykonać w odpowiednim miejscu, aby Mathematica nie zdenerwował się.-8 bajtów: naprawiono błąd dla liczb całkowitych, który faktycznie skrócił kod.
-15 bajtów:
FactorInteger
zwraca posortowane dane wyjściowe, z których możemy skorzystać.-46 bajtów: tak naprawdę nie musimy być sprytni.
źródło
Python 2,
220202195183 bajtówWypróbuj online! Edycja: Zapisano
1825 bajtów dzięki @ Mr.Xcoder. Zaoszczędź 12 bajtów dzięki @JonathanFrech.źródło