2
$\begingroup$

I try to solve with Mathematica 13.3.1 on Windows 10 the problem $$x^2+2^{x^2+1990}-y^2=2^{y^2+y}+y-1990\land x+y>1990,\, x\in \mathbb{Z},\,y\in \mathbb{Z}$$ which originates from Bauman Moscow State Technical University .

Unfortunately,

FindInstance[2^(x^2 + 1990) + x^2 - y^2 == 2^(y^2 + y) + y - 1990 && 
x + y > 1990, {x, y}, Integers]

FindInstance::nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.

and

NMinimize[{(2^(x^2 + 1990) + x^2 - y^2 - 2^(y^2 + y) - y + 1990)^2, 
x + y > 1990 && {x, y} \[Element] Integers}, {x, y}]

NMinimize::nsol: There are no points that satisfy the constraints {x+y>1990,(x|y)[Element][DoubleStruckCapitalZ]}. {\[Infinity], {x -> Indeterminate, y -> Indeterminate}}

fail. Is it still possible to solve this problem with Mathematica?

$\endgroup$
14
  • $\begingroup$ See here for the reference. $\endgroup$
    – user64494
    Commented Oct 2, 2023 at 18:10
  • 3
    $\begingroup$ "Isn't it art for art's sake?" $\endgroup$
    – Domen
    Commented Oct 2, 2023 at 18:45
  • 1
    $\begingroup$ I might think about introducing auxiliary variables, e.g. u=x^2+1990 and v=y^2+y. If you could find all the solutions of the equality, you could check which satisfied the inequality. $\endgroup$
    – mikado
    Commented Oct 2, 2023 at 18:46
  • $\begingroup$ @Domen: I find Bauman Moscow State Technical University a solid organization. Also the bug in NMinimize should be noticed. $\endgroup$
    – user64494
    Commented Oct 2, 2023 at 18:56
  • $\begingroup$ @mikado: Can you kindly present your suggestion as an answer? $\endgroup$
    – user64494
    Commented Oct 2, 2023 at 19:20

3 Answers 3

2
$\begingroup$

When all the unknowns are integers, here's an approach that can give specific (non-general) solutions to problems that are otherwise unsolvable in Mathematica:

If you can guess upper and lower bounds for all the unknowns, that gives you a finite number of combinations to test. You can then ask Mathematica to do a brute-force search, in which it tests all of them. This works if the number of tests is not too large to be practical.

This is implemented using the following, which works with FindInstance, Reduce, and Resolve:

SetSystemOptions["ReduceOptions" -> "ExhaustiveSearchMaxPoints" -> {a, b}]; 

According to the documentation (note this applies only when all variables are integers):

For systems containing explicit lower and upper bounds on all variables, the Wolfram Language uses exhaustive search to find solutions. The bounds of the search are specified by the value of the system option ExhaustiveSearchMaxPoints. The option value should be a pair of integers (the default is {1000,10000}). If the number of integer points within the bounds does not exceed the first integer, the exhaustive search is used instead of any solution methods other than univariate polynomial solving. Otherwise, if the number of integer points within the bounds does not exceed the second integer, the exhaustive search is performed after all other methods fail.

While your problem is clearly designed to be solved by inspection, we can still use it to test this approach. Let's suppose you guessed both x and y are between 0 and 5,000, inclusive. This gives a maximum of 5,001^2 = 25,010,001 solutions to test. [It would actually be less because of the additional constraint that x + y > 1900, but that's not important here.] For b, We just need to be pick a number larger than the number of possible solutions, so I choose 26,000,000. I also chose 26,000,000 for a to ensure that "exhaustive search is used instead of any solution methods other than univariate polynomial solving", to speed up the process.

If you just want one solution, FindInstance is quicker, because it stops the exhaustive search after a solution is found. This takes 1.4 hours on a 2019 i9 iMac running MMA 13.3.1:

SetSystemOptions[
"ReduceOptions" -> "ExhaustiveSearchMaxPoints" -> {26000000, 26000000}];
FindInstance[
2^(x^2 + 1990) + x^2 - y^2 == 2^(y^2 + y) + y - 1990 
&& x + y > 1900 && 0 <= x <= 5000 && 0 <= y <= 5000, {x, y}, Integers]

{{x -> 1990, y -> 1990}}

If you want all solutions, and don't know how many there are, you'll need to run Reduce (or FindInstance with a sufficiently large value for the maximum number of instances). Here's Reduce without the x + y > 1900 constraint. It took 5.8 hours (I just left it to run overnight):

SetSystemOptions[
"ReduceOptions" -> "ExhaustiveSearchMaxPoints" -> {26000000, 26000000}];
Reduce[
2^(x^2 + 1990) + x^2 - y^2 == 2^(y^2 + y) + y - 1990 
&& 0 <= x <= 5000 && 0 <= y <= 5000, {x, y}, Integers]

(x == 100 && y == 109) || (x == 1990 && y == 1990)

Screenshots of code & results, as requested:


FindInstance



Reduce


$\endgroup$
4
  • $\begingroup$ Cannot reproduce it on my comp because "This takes 1.4 hours on a 2019 i9 iMac running MMA 13.3.1". $\endgroup$
    – user64494
    Commented Oct 5, 2023 at 3:42
  • $\begingroup$ Can you kindly present a screen of your executed code in the forum? In any case +1. $\endgroup$
    – user64494
    Commented Oct 5, 2023 at 3:51
  • $\begingroup$ You wrote "your problem is clearly designed to be solved by inspection". It is not true: see my comment to the question "Reduce[a + 2^a == b + 2^b, {a, b}, Reals] results in (a == 0 && b == 0) || b == 2^a + a - ProductLog[2^(2^a + a) Log[2]]/Log[2], not in a==b. This is a problem". $\endgroup$
    – user64494
    Commented Oct 5, 2023 at 4:21
  • $\begingroup$ (1) Done! BTW, if the runtime is an issue, you could try my same FindInstance code, but substitute 0<=x<2000 && 0<=y=2000 for 0<=x<5000 && 0<=y=5000. Everything else can be left as-is. Then it will check ≈2000^2 combinations instead of ≈5000^2. That reduces my run time substantially, from 1.4 hrs. to 5 mins. (2) Sorry, I'm not following your response to my observation that it's designed to be solvable "by inspection". When I wrote that, I meant it was designed for the students to find the solution "by eye" (without using a CAS like MMA). The hint (1990) is given in the problem. $\endgroup$
    – theorist
    Commented Oct 5, 2023 at 4:54
0
$\begingroup$

Trivally, by regrouping

 2^(x^2 + 1990) + x^2 + 1990 == 2^(y^2 + y) + y^2 + y

has the trival solution only.

Consider the mathematical focus of a technical university.

$\endgroup$
1
  • $\begingroup$ Nothing to comment, $\endgroup$
    – user64494
    Commented Oct 3, 2023 at 8:51
0
$\begingroup$

$$x^2+2^{x^2+1990}-y^2=2^{y^2+y}+y-1990$$

We can cancel the power of two parts if we suppose the solution looks like $x^2 + 1990$ = $y^2 + y$: $$x^2+2^{x^2+1990}-y^2=2^{x^2+1990}+y-1990\\ x^2-y^2=y-1990 \\ = x^2 + 1990 = y^2 + y$$

Which is true due to our assumption $x^2 + 1990 = y^2 + y$

Therefore a solution to $$x^2 + 1990 = y^2 + y$$ is a solution to $$x^2+2^{x^2+1990}-y^2=2^{y^2+y}+y-1990$$

Another way to see this is by taking the log of both sides, and ignoring small terms (screenshot because I didn't want to rewrite this and don't know how to get deleted edits from post history):

enter image description here

So we just need to solve x^2 + 1990 == y^2 + y.

eq = 2^(1990 + x^2) + x^2 - y^2 == -1990 + 2^(y + y^2) + y;
(*simpler equation with same solutions*)
simp = 1990 + x^2 == y + y^2;

(*get integer solutions*)
solns = Solve[simp, {x, y}, Integers]
(*
{{x -> -1990, y -> -1991}, {x -> -1990, y -> 1990}, {x -> -100, 
  y -> -110}, {x -> -100, y -> 109}, {x -> 100, y -> -110}, {x -> 100,
   y -> 109}, {x -> 1990, y -> -1991}, {x -> 1990, y -> 1990}}
*)

And veryfying they all satisfy eq:

(*they all also satisfy eq.*)
eq /. solns
(*{True, True, True, True, True, True, True, True}*)

And the question just wants the one with x+y>1990 (only one solution):

(*select ones where x+y>1990*)
Select[solns, Total@Values@# > 1990 &]
(*{{x -> 1990, y -> 1990}}*)

(*Or alternatively, Reduce with condition on x+y*)
Reduce[simp && x + y > 1990, {x, y}, Integers]
(*x == 1990 && y == 1990*)

Add-on I don't know if these are the only solutions to the original equation. I don't think I have knowledge of the right mathematical tools to prove or disprove that. But I do know these all are solutions.


Second Add-on We can prove that all solutions of eq with a real value y are solutions of simp.

Since we already know from above all solutions of simp are solutions of eq, proving all solutions (with real y) of eq are solutions of simp proves that all possible solutions of eq (with real y) are exactly the solutions of simp with real y. And thus {{x -> 1990, y -> 1990}} is the only valid solution on the integers when we add in the constraint x+y>1990.

First solve for x in eq without the condition x+y > 1990:

red = Simplify[
  Reduce[2^(1990 + x^2) + x^2 == k, x] /. 
   k -> ( -1990 + 2^(y + y^2) + y + y^2)]

(*
(C[1] \[Element] 
    Integers && (x == -((
       I Sqrt[-((-1990 + 2^(y + y^2) + y + y^2) Log[2]) + 
         ProductLog[C[1], 2^(2^(y + y^2) + y + y^2) Log[2]]])/Sqrt[
       Log[2]]) || 
     x == (I Sqrt[-((-1990 + 2^(y + y^2) + y + y^2) Log[2]) + 
        ProductLog[C[1], 2^(2^(y + y^2) + y + y^2) Log[2]]])/Sqrt[
      Log[2]])) || (2^(y (1 + y)) + y + y^2 == 
    2^1990 + 1990 && x == 0)
*)

We can immediately eliminate the last solution (2^(y (1 + y)) + y + y^2 == 2^1990 + 1990 && x == 0 on the integers by showing there's no integer y to satisfy the equation:

(*makes sense because 1990 cannot be written as y (1+y) for integer y*)


Reduce[2^(y (1 + y)) + y + y^2 == 2^1990 + 1990, g, Integers]
(*False*)

So we drop the last solution of red. We also assume real y, and that C[1] the branch number of the product log is an integer:

(*remove last part of red because it is False on integers*)
red = Simplify[Most@red, y \[Element] Reals && C[1] \[Element] Integers]
(*x == -((I Sqrt[-((-1990 + 2^(y + y^2) + y + y^2) Log[2]) + 
     ProductLog[C[1], 2^(2^(y + y^2) + y + y^2) Log[2]]])/Sqrt[
   Log[2]]) || 
 x == (I Sqrt[-((-1990 + 2^(y + y^2) + y + y^2) Log[2]) + 
    ProductLog[C[1], 2^(2^(y + y^2) + y + y^2) Log[2]]])/Sqrt[Log[2]]*)

The two solutions only differ by sign, and we just need to show they also satisfy simp. Since simp is just x^2 in x, we can ignore the sign and take just one of the solutions:

(*notice the two solutions just differ by sign*)
red[[1, 2]] == -red[[2, 2]];
(*just take positive one, because we are going to sub this into simp \
for x, which only has x^2 power*)
red = red[[2, 2]]
(* (I Sqrt[-((-1990 + 2^(y + y^2) + y + y^2) Log[2]) + 
  ProductLog[C[1], 2^(2^(y + y^2) + y + y^2) Log[2]]])/Sqrt[Log[2]] *)

also notice the argument of ProductLog 2^(2^(y + y^2) + y + y^2) Log[2] is always a positive real for real y, so we can just take the principal branch C[1]->0:

red = red /. C[1] -> 0;
(*change red to a rule for replacement later*)
redRule = x -> red

(*x -> (I Sqrt[-((-1990 + 2^(y + y^2) + y + y^2) Log[2]) + 
   ProductLog[2^(2^(y + y^2) + y + y^2) Log[2]]])/Sqrt[Log[2]]*)

Now apply redRule to simp, and divide both sides by Log[2]:

sub = Simplify[ simp /. redRule];
(*divide both sides by log2*)
sub = ApplySides[#/Log[2] &, sub]

(*2^(y + y^2) == ProductLog[2^(2^(y + y^2) + y + y^2) Log[2]]/Log[2]*)

Notice the rhs of sub is the solution to w 2^w = 2^( 2^(y (1 + y)) + y + y^2):

rhs = sub[[2]];
Simplify[rhs*2^rhs == 2^(2^(y (1 + y)) + y + y^2)]

(*True*)

So apply # 2^# & to both sides and simplify:

applied = ApplySides[# 2^# &, sub];
applied // Simplify

(*True*)

Therefore, any solution with real y to eq is a solution to simp. Since we already know any solution to simp is a solution to eq, this means all solutions with real y to eq are the same as all solutions to simp with real y. Since integers are a subset of the reals, we can thus say the same thing about integer y solutions. Therefore {{x -> 1990, y -> 1990}} is the only solution.

Just checking with a few small values of y:


yTab = Table[{y -> i, Flatten[redRule /. y -> i]} // Thread, {i, -5, 
    5}];
Simplify[eq /. yTab]
Simplify[simp /. yTab]

(*{True, True, True, True, True, True, True, True, True, True, True}*)

(*{True, True, True, True, True, True, True, True, True, True, True}*)

$\endgroup$
7
  • $\begingroup$ All that is built on "our assumption $x^2 + 1990 = y^2 + y$". $\endgroup$
    – user64494
    Commented Oct 5, 2023 at 3:40
  • $\begingroup$ In particular ""the small terms I ignored" should be grounded. This follows from the monotonicity of $z+2^z$. As noticed in the comments to the question, MMA 13.3.1 has problems with it. $\endgroup$
    – user64494
    Commented Oct 5, 2023 at 4:03
  • $\begingroup$ @user64494 added proof that all integer solutions are of the form $x^2 + 1990 = y + y^2$ $\endgroup$
    – ydd
    Commented Oct 5, 2023 at 18:07
  • $\begingroup$ "also notice the argument of ProductLog 2^(2^(y + y^2) + y + y^2) Log[2] is always a positive real for real y, so we can just take the principal branch C[1]->0" is one of the steps done by hand. Can you simplify the result of Reduce[a+2^a==b+2^b,{a,b},Reals ] to a==b programatically? $\endgroup$
    – user64494
    Commented Oct 5, 2023 at 18:18
  • $\begingroup$ @user64494 I will try but I am not sure. I have a feeling I am less skilled than you. $\endgroup$
    – ydd
    Commented Oct 5, 2023 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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