Istnieje równanie, zakładając n
i x
są dodatnie,
który wyraża związek między dwoma monomialami, z których jeden jest powszechnym wprowadzaniem w błąd drugiego. Wiele osób popełnia prosty błąd zrównując je (tj. 3x^2
I (3x)^2
).
Wyzwanie
Biorąc pod uwagę dodatnią liczbę całkowitą, i
określ i zwróć rozwiązanie n
oraz x
najmniejszą sumę jako tablicę [n, x]
. W przypadku remisu dowolny zestaw rozwiązań jest dopuszczalny.
Przypadki testowe
62658722541234765
[15, 11]
202500
[4, 15]
524288
[8, 4]
33044255768277
[13, 9]
code-golf
number-theory
Zach Gates
źródło
źródło
[x, n]
zamiast[n, x]
?n
ix
liczby całkowite, prawda?[n, x]
i nie ma ograniczeń czasowych @Fatalizen
ix
są liczbami całkowitymi @LuisMendoOdpowiedzi:
Brachylog , 35 bajtów
Wypróbuj online!
Wyjaśnienie
Tworzymy listę
[N, X]
, w którejN >= X
następnie, po przypisaniu jej wartości, wypróbowujemy oba[N, X]
i[X, N]
jak to możliwe dane wyjściowe. Na przykład, jeśliN
zostanie przypisana3
, będziemy testować przez backtracking[3, 1]
,[1, 3]
,[3, 2]
,[2, 3]
,[3, 3]
i[3, 3]
. Następnie nastąpi kolejny krok cofania wartościN
, która przejdzie do4
itp.źródło
Mathematica, 61 bajtów
Dzięki milom za zaoszczędzenie 2 bajtów plus całą masę bajtów, które policzyłem bez powodu!
Oblicza tabelę par {n, x}, gdzie x = (i / n) ^ (1 / n), przy użyciu wszystkich możliwych wartości n; zachowuje tylko te, dla których odpowiadające x jest liczbą całkowitą; następnie zwraca parę o największej wartości n.
Tutaj „wszystkie możliwe wartości n” mieszczą się w zakresie od 1 do 2 * ln (i). To ignoruje rozwiązanie {n, x} = {i, 1}, ale jest w porządku, ponieważ rozwiązanie {n, x} = {1, i} wystarczy, jeśli jest to najlepszy wybór. Zatem x nigdy nie musi być mniejszy niż 2, co oznacza, że n * 2 ^ n ≤ i, a wszystkie takie n są mniejsze niż 2 * ln (i).
Można wykazać za pomocą rachunku różniczkowego, że para {n, x}, która minimalizuje ich sumę w tym kontekście, jest taka sama jak para {n, x} z największym n (nie licząc {i, 1}). Dlatego inicjał
Last
jest wystarczająco dobry, aby znaleźć optymalną parę.źródło
IntegerQ@*Last
aby zapisać 2 bajty, ale liczę również 63, a nie 86 bajtów w bieżącej wersji.MATL , 22 bajty
Wyjścia są
x
,n
w tej kolejności.Dane wejściowe są ograniczone domyślnym
double
typem danych MATL , który może dokładnie reprezentować liczby całkowite do maksymalnie2^53
. Wyklucza to pierwszy test (nadal daje poprawny wynik, ale nie można tego ogólnie zagwarantować w przypadku tak dużych nakładów).Wypróbuj online!
Wyjaśnienie
Kod wykorzystuje dwie zagnieżdżone pętle:
do...while
Pętla zewnętrzna przechodzi przez wszystkie możliwe sumyn+x
w porządku rosnącym. Pętla zostanie zatrzymana, gdy tylko zostanie znalezione rozwiązanie. Gwarantuje to, że wydamy rozwiązanie z minimalną sumą.for each
Pętla wewnętrzna testuje wszystkon
ix
z tą sumą. Kiedy suma zbiega się z wejściem, pętla wewnętrzna jest opuszczana, a stan pętli zewnętrznej pętli jest ustawiany nafalse
taki, aby wyjść również z pętli .Skomentowany kod:
źródło
Galaretka ,
2316 bajtówBiorąc pod uwagę
i
, generuje to wszystkie pary liczb całkowitych z zamianą w[1, i]
. Następnie wykonuje to samo filtrowanie i sortowanie, jak w poprzednim rozwiązaniu pokazanym poniżej. Ponieważ nie ma ograniczeń czasowych, brutalna siła zadziała, mając wystarczająco dużo czasu.Wypróbuj online! , ale nie wypróbuj dużych wartości online.
Na moim komputerze obliczenie wyniku
i = 2048
użycia nieefektywnej wersji zajmuje około 6 minut .Wydajna wersja
Jest to poprzednie rozwiązanie dla 23 bajtów, które jest w stanie szybko rozwiązać duże wartości.
Biorąc pod uwagę
i
, oblicza dzielniki,i
aby wygenerować pary[n, x]
gdzien
jest dzielnikiem ix = floor( (i/n)^(1/n) )
. Następnie filtruje je pod kątem wartości, gdzien * x^n == i
posortuje pozostałe pary według ich sumy i zwraca pierwszą parę.Wypróbuj online!lub Zweryfikuj wszystkie przypadki testowe.
Wyjaśnienie
źródło
PHP, 104 bajtów
Powoduje to wyświetlenie wszystkich możliwych rozwiązań, które nie są w proponowanym formacie 73 bajtów
źródło
Perl, 52 bajty
Obejmuje +2 za
-ap
Podaj dane na STDIN
mono.pl
:Podjęłam trochę wysiłku, aby również działał
1
. Nie mam pojęcia, czy błędy zmiennoprzecinkowe mogą powodować, że zwracają one błędną odpowiedź dla niektórych danych wejściowych.źródło