2
$\begingroup$

Find two integers x and y such that $x^y +y^x = 94032$.

I have used

Solve[x^y + y^x == 94032, {x, y}, Integers]
Reduce[x^y + y^x == 94032, {x, y}, Integers]
FindInstance[x^y + y^x == 94032, {x, y}, Integers]

But I can not find the integers that are the solution

I would appreciate any help

$\endgroup$
  • 2
    $\begingroup$ Is it possible there are no integer solutions? ContourPlot[x^y + y^x == 94032, {x, 5.1, 6.2}, {y, 5.8, 6.9}] $\endgroup$ – Moo Jan 6 '17 at 6:02
  • 1
    $\begingroup$ Also, transcendental Diophantine equations are hard. $\endgroup$ – J. M. is away Jan 6 '17 at 6:03
  • 1
    $\begingroup$ $x=1,y=94031$ is solution. $\endgroup$ – Nasser Jan 6 '17 at 6:19
  • $\begingroup$ There are at least two solutions : x^y + y^x /. {x -> 94031, y -> 1} x^y + y^x /. {x -> 1, y -> 94031} gives 94032 $\endgroup$ – cyrille.piatecki Jan 6 '17 at 6:20
  • 2
    $\begingroup$ Frequently, adding bounds to variables helps Mathematica find solutions. In your case, including x>0 and y>0 in Solve does not help, but including 10>x>0 does. The tighter the bound, the quicker the solution, suggesting Mathematica is using a brute-force algorithm. $\endgroup$ – KennyColnago Jan 6 '17 at 16:29
5
$\begingroup$

There is always a trivial solution: $x=n-1,y=1$.

You can use brute force to find non trivial solutions.

Method 1. Calculate $x^y+y^x$ for all pairs $x < \sqrt{n}$ and $y < \sqrt{n}$. Since we are not interested in trivial solutions, we don't need to check $x > \sqrt{n}$. Then check if we have $n$ in the result list.

findNonTrivialPairs[n_]:=Select[{#1, #2, #1^#2 + #2^#1} & @@@ Tuples[#, 2] &@
    Range[Ceiling@Sqrt[n]], #[[3]] == n &];
findNonTrivialPairs[100]
(* {{2, 6, 100}, {6, 2, 100}} *)

AbsoluteTiming@findNonTrivialPairs[94032]    
(* {0.545318, {}}  <- no non-trivial solutions *)

Method 2.

We will look for pairs where $y > x$, so iterations over y start with $x$

f[{x_, y_, z_}] := {x, y + 1, x^(y + 1) + (y + 1)^x};    
g[x_, n_] := NestWhile[f, {x, x, 0}, #[[3]] < n &];     
findPairs[n_] :=Select[Map[g[#, n] &,Range[n/2]], #[[1]]^#[[2]] + #[[2]]^#[[1]] == n &];

findPairs[100]

(* {{1, 99, 100}, {2, 6, 100}} it has non-trivial solutions *)

Let's find non-trivial solutions for $100<n<200$

Rest /@ Select[findPairs /@ Range[100, 1000], Length[#] > 1 &]
(* {{{2, 6, 100}}, {{3, 4, 145}}, {{2, 7, 177}}, {{2, 8, 320}}, {{3, 5, 
   368}}, {{2, 9, 593}}, {{3, 6, 945}}} *)

For your particular $n=94032$ it seems to have no non-trivial solution (and it takes some time to calculate it):

AbsoluteTiming@findPairs[94032]
(* {108.22, {{1, 94031, 94032}}} *)

Update: We don't need to iterate up to n/2 we can iterate up to l, where l^l=n

It will significantly increase performance.

limit[n_] := Ceiling[x /. FindRoot[x^x == n, {x, 1}]];
findPairs2[n_] := 
  Select[Map[g[#, n] &,Range[limit[n]]], #[[1]]^#[[2]] + #[[2]]^#[[1]] == n &];

AbsoluteTiming@findPairs2[94032]
(* {0.401372, {{1, 94031, 94032}}} *)
$\endgroup$
  • $\begingroup$ Great analysis, many ways I did not know, thanks for your time $\endgroup$ – zeros Jan 7 '17 at 1:47
3
$\begingroup$

you can actually very simply show there are only the trivial solutions:

1) note it is sufficient to consider x<=y , so 2 x^x <= 94032 or x<=6.

Then:

 Table[ {x, y /. FindRoot[ x^y + y^x == 94032 , {y, x}]}, {x, 6}]

{{1, 94031.}, {2, 16.5167}, {3, 10.4125}, {4, 8.22445}, {5, 6.99343}, {6, 6.00551}}

$\endgroup$
  • $\begingroup$ thanks, Very effective and concise $\endgroup$ – zeros Jan 7 '17 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.