Istnieje równanie, zakładając ni xsą 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^2I (3x)^2).

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą, iokreśl i zwróć rozwiązanie noraz xnajmniejszą 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]

Brachylog , 35 bajtów

,[N:X]#>>==L(.rMtT;Lr.rMtT),M^:T*?,

Wypróbuj online!

Wyjaśnienie

Tworzymy listę [N, X], w której N >= Xnastę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śli Nzostanie przypisana 3, 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ści N, która przejdzie do 4itp.

,[N:X]     The list [N, X]
#>         Both N and X are strictly positive
>=         N >= X
=L         Assign values to N and X, and L = [N, X]
(          Either...
    .          Output = L
    rM         M is the reverse of the Output
    tT         T is the second element of M
;          ...or...
    Lr.        Output is the reverse of L
    rM         M = L
    tT         T is the last element of M
),
M^         First element of M to the power of the second element of L (T)...
:T*?,      ... times T is equal to the Input

Mathematica, 61 bajtów

Dzięki milom za zaoszczędzenie 2 bajtów plus całą masę bajtów, które policzyłem bez powodu!

Last@Select[{n,(#/n)^(1/n)}~Table~{n,2Log@#},IntegerQ@*Last]&

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ł Lastjest wystarczająco dobry, aby znaleźć optymalną parę.

MATL , 22 bajty

`T@XK:"@K@-@^*G=?3Mb~.

Wyjścia są x, nw tej kolejności.

Dane wejściowe są ograniczone domyślnym doubletypem danych MATL , który może dokładnie reprezentować liczby całkowite do maksymalnie 2^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...whilePętla zewnętrzna przechodzi przez wszystkie możliwe sumy n+xw porządku rosnącym. Pętla zostanie zatrzymana, gdy tylko zostanie znalezione rozwiązanie. Gwarantuje to, że wydamy rozwiązanie z minimalną sumą.
• for eachPętla wewnętrzna testuje wszystko ni xz 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 na falsetaki, aby wyjść również z pętli .

Skomentowany kod:

`         % Do...while
  T       %   Push "true". Will be used as loop condition (possibly negated to exit loop)
  @       %   Push iteration index, say K, which represents n+x
  XK      %   Copy that into clipboard K
  :       %   Range [1 2 ... K]
  "       %   For each
    @     %     Push loop variable (1, 2, ... K), which represents n
    K@-   %     Compute x as K minus n
    @     %     Push n again
    ^*    %     Power, multiply. This gives n*x^n
    G=    %     Does this equal the input?
    ?     %     If so
      3M  %       Push the inputs of the third-last function, that is, x and n
      b   %       Bubble up the "true" that is at the bottom of the stack
      ~   %       Transform it into "false". This will exit the do...while loop
      .   %       Break the for loop
          %     Implicitly end if
          %   Implicitly end for
          % Implicitly end do...while
          % Implicitly display

Galaretka , 23 16 bajtów

×*@¥/=³
ṗ2ÇÐfSÞḢ

Biorą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 = 2048uż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.

×*@¥/=³
ÆDµṚ*İ⁸żḞÇÐfSÞḢ

Biorąc pod uwagę i, oblicza dzielniki, iaby wygenerować pary [n, x]gdzien jest dzielnikiem i x = floor( (i/n)^(1/n) ). Następnie filtruje je pod kątem wartości, gdzie n * x^n == iposortuje pozostałe pary według ich sumy i zwraca pierwszą parę.

Wypróbuj online!lub Zweryfikuj wszystkie przypadki testowe.

Wyjaśnienie

×*@¥/=³  Helper link. Input: list [n, x]
    /    Reduce using
   ¥       A dyadic chain
 *@        Compute x^n
×          Multiply by n
      ³  The initial value i
     =   Test if n * x^n == i

ṗ2ÇÐfSÞḢ  Main link (16 byte version). Input: integer i
ṗ2        Generate all pairs of integers in [1, i]
  ÇÐf     Filter for where the helper link is true
     SÞ   Sort them by their sum
       Ḣ  Return the first result

ÆDµṚ*İ⁸żḞÇÐfSÞḢ  Main link (23 byte version). Input: integer i
ÆD               Compute the divisors of i
  µ              Begin a new monadic chain operating on the divisors
   Ṛ             Reverse the divisors
     İ           Reciprocal of each divisors
    *            Raise each in the reversed divisors to the reciprocal of a divisor
      ⁸          Get the divisors
       ż         Interleave the divisors with the previous powers
        Ḟ        Floor each
         ÇÐf     Filter for where the helper link is true
            SÞ   Sort them by their sum
              Ḣ  Return the first result

PHP, 104 bajtów

for(;1<$x=(($i=$argv[1])/++$n)**(1/$n);)!($x==ceil($x))?:$a[$x+$n]="[$x, $n]";ksort($a);echo$a[key($a)];

Powoduje to wyświetlenie wszystkich możliwych rozwiązań, które nie są w proponowanym formacie 73 bajtów

for(;1<=$x=(($i=$argv[1])/++$n)**(1/$n);)!($x==ceil($x))?:print"$x,$n\n";

Perl, 52 bajty

Obejmuje +2 za -ap

Podaj dane na STDIN

mono.pl <<< 33044255768277

mono.pl:

#!/usr/bin/perl -ap
$_=("@F"/++$.)**(1/$.)while!/\./?$\="$. $_":$_>2}{

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.