Repository: sympy/sympy

Issue:
RecursionError _solve _tsolve _vsolve in expression involving Mod and floor
This expression was extracted from some PyTorch model shape expressions involving SymPy. We have discovered the expression in question is zero, and we would like to know if s2 is now statically known. We don't mind if solving says not implemented, or if there are no solutions (there are probably no solutions). However, the equation instead stack overflows.

```
import sympy
from sympy import Mod, floor

s2 = sympy.Symbol('s2', integer=True, positive=True)

sympy.solve((Mod(floor(s2/2 - 1/2)**2/(floor(s2/2 - 1/2) + 1) + 2*floor(s2/2 - 1/2)/(floor(s2/2 - 1/2) + 1) + 1/(floor(s2/2 - 1/2) + 1), 1))*floor(s2/2 - 1/2) + Mod(floor(s2/2 - 1/2)**2/(floor(s2/2 - 1/2) + 1) + 2*floor(s2/2 - 1/2)/(floor(s2/2 - 1/2) + 1) + 1/(floor(s2/2 - 1/2) + 1), 1) - 0, s2)
```

Fragment of the backtrace:

```
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1630, in _solve
    inv = _vsolve(u - t, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1682, in _solve
    soln = _tsolve(f_num, symbol, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2752, in _tsolve
    return _vsolve(rewrite - rhs, sym, **flags)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2584, in _vsolve
    return [i[s] for i in _solve(e, s, **flags)]
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 1425, in _solve
    f_num, sol = solve_linear(f, symbols=symbols)
  File "/Users/ezyang/Dev/sympy/sympy/solvers/solvers.py", line 2132, in solve_linear
    dnewn_dxi = newn.diff(xi)
  File "/Users/ezyang/Dev/sympy/sympy/core/expr.py", line 3577, in diff
    return _derivative_dispatch(self, *symbols, **assumptions)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 1913, in _derivative_dispatch
    return Derivative(expr, *variables, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 1441, in __new__
    obj = cls._dispatch_eval_derivative_n_times(expr, v, count)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 1902, in _dispatch_eval_derivative_n_times
    return expr._eval_derivative_n_times(v, count)
  File "/Users/ezyang/Dev/sympy/sympy/core/basic.py", line 1835, in _eval_derivative_n_times
    obj2 = obj._eval_derivative(s)
  File "/Users/ezyang/Dev/sympy/sympy/core/cache.py", line 72, in wrapper
    retval = cfunc(*args, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/core/add.py", line 508, in _eval_derivative
    return self.func(*[a.diff(s) for a in self.args])
  File "/Users/ezyang/Dev/sympy/sympy/core/add.py", line 508, in <listcomp>
    return self.func(*[a.diff(s) for a in self.args])
  File "/Users/ezyang/Dev/sympy/sympy/core/expr.py", line 3577, in diff
    return _derivative_dispatch(self, *symbols, **assumptions)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 1913, in _derivative_dispatch
    return Derivative(expr, *variables, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 1441, in __new__
    obj = cls._dispatch_eval_derivative_n_times(expr, v, count)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 1902, in _dispatch_eval_derivative_n_times
    return expr._eval_derivative_n_times(v, count)
  File "/Users/ezyang/Dev/sympy/sympy/core/basic.py", line 1835, in _eval_derivative_n_times
    obj2 = obj._eval_derivative(s)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 608, in _eval_derivative
    df = self.fdiff(i)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 791, in fdiff
    return Subs(Derivative(self.func(*args), D), D, A)
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 2205, in __new__
    s_pts = {p: Symbol(pre + mystr(p)) for p in pts}
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 2205, in <dictcomp>
    s_pts = {p: Symbol(pre + mystr(p)) for p in pts}
  File "/Users/ezyang/Dev/sympy/sympy/core/function.py", line 2203, in mystr
    return p.doprint(expr)
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 293, in doprint
    return self._str(self._print(expr))
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 332, in _print
    return printmethod(expr, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 57, in _print_Add
    t = self._print(term)
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 332, in _print
    return printmethod(expr, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 161, in _print_Function
    return expr.func.__name__ + "(%s)" % self.stringify(expr.args, ", ")
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 41, in stringify
    return sep.join([self.parenthesize(item, level) for item in args])
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 41, in <listcomp>
    return sep.join([self.parenthesize(item, level) for item in args])
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 38, in parenthesize
    return self._print(item)
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 332, in _print
    return printmethod(expr, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 364, in _print_Mul
    a_str = [self.parenthesize(x, prec, strict=False) for x in a]
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 364, in <listcomp>
    a_str = [self.parenthesize(x, prec, strict=False) for x in a]
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 38, in parenthesize
    return self._print(item)
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 332, in _print
    return printmethod(expr, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 161, in _print_Function
    return expr.func.__name__ + "(%s)" % self.stringify(expr.args, ", ")
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 41, in stringify
    return sep.join([self.parenthesize(item, level) for item in args])
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 41, in <listcomp>
    return sep.join([self.parenthesize(item, level) for item in args])
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 38, in parenthesize
    return self._print(item)
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 332, in _print
    return printmethod(expr, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/printing/str.py", line 52, in _print_Add
    terms = self._as_ordered_terms(expr, order=order)
  File "/Users/ezyang/Dev/sympy/sympy/printing/printer.py", line 350, in _as_ordered_terms
    return expr.as_ordered_terms(order=order)
  File "/Users/ezyang/Dev/sympy/sympy/core/expr.py", line 1146, in as_ordered_terms
    terms, gens = self.as_terms()
  File "/Users/ezyang/Dev/sympy/sympy/core/expr.py", line 1176, in as_terms
    coeff = complex(coeff)
  File "/Users/ezyang/Dev/sympy/sympy/core/expr.py", line 355, in __complex__
    re, im = result.as_real_imag()
  File "/Users/ezyang/Dev/sympy/sympy/core/expr.py", line 1931, in as_real_imag
    return (re(self), im(self))
  File "/Users/ezyang/Dev/sympy/sympy/core/cache.py", line 72, in wrapper
    retval = cfunc(*args, **kwargs)
  File "/Users/ezyang/Dev/sympy/sympy/core/numbers.py", line 1375, in __eq__
    other = _sympify(other)
  File "/Users/ezyang/Dev/sympy/sympy/core/sympify.py", line 528, in _sympify
    return sympify(a, strict=True)
  File "/Users/ezyang/Dev/sympy/sympy/core/sympify.py", line 361, in sympify
    is_sympy = getattr(a, '__sympy__', None)
RecursionError: maximum recursion depth exceeded while calling a Python object
```

Reproduces on 1fbd995ead126e9b20210e1d3377210c27c71b7b (master at time of writing)

Discussion:

Patch:
diff --git a/sympy/solvers/solvers.py b/sympy/solvers/solvers.py
index fcc7e13c31..3a86454b24 100644
--- a/sympy/solvers/solvers.py
+++ b/sympy/solvers/solvers.py
@@ -42,6 +42,7 @@
     separatevars)
 from sympy.simplify.sqrtdenest import sqrt_depth
 from sympy.simplify.fu import TR1, TR2i
+from sympy.strategies.rl import rebuild
 from sympy.matrices.common import NonInvertibleMatrixError
 from sympy.matrices import Matrix, zeros
 from sympy.polys import roots, cancel, factor, Poly
@@ -2770,6 +2771,7 @@ def equal(expr1, expr2):
                 return _vsolve(lhs.args[0] - rhs*exp(rhs), sym, **flags)
 
         rewrite = lhs.rewrite(exp)
+        rewrite = rebuild(rewrite) # avoid rewrites involving evaluate=False
         if rewrite != lhs:
             return _vsolve(rewrite - rhs, sym, **flags)
     except NotImplementedError:


Test patch:
diff --git a/sympy/solvers/tests/test_solvers.py b/sympy/solvers/tests/test_solvers.py
index c13aa051c9..1c4b2fca8f 100644
--- a/sympy/solvers/tests/test_solvers.py
+++ b/sympy/solvers/tests/test_solvers.py
@@ -2,6 +2,7 @@
 from sympy.core.add import Add
 from sympy.core.containers import Tuple
 from sympy.core.function import (Derivative, Function, diff)
+from sympy.core.mod import Mod
 from sympy.core.mul import Mul
 from sympy.core import (GoldenRatio, TribonacciConstant)
 from sympy.core.numbers import (E, Float, I, Rational, oo, pi)
@@ -13,6 +14,7 @@
 from sympy.functions.elementary.complexes import (Abs, arg, conjugate, im, re)
 from sympy.functions.elementary.exponential import (LambertW, exp, log)
 from sympy.functions.elementary.hyperbolic import (atanh, cosh, sinh, tanh)
+from sympy.functions.elementary.integers import floor
 from sympy.functions.elementary.miscellaneous import (cbrt, root, sqrt)
 from sympy.functions.elementary.piecewise import Piecewise
 from sympy.functions.elementary.trigonometric import (acos, asin, atan, atan2, cos, sec, sin, tan)
@@ -2646,3 +2648,11 @@ def test_solve_undetermined_coeffs_issue_23927():
         phi: 2*atan((A + sqrt(A**2 + B**2))/B),
         r: (A**2 + A*sqrt(A**2 + B**2) + B**2)/(A + sqrt(A**2 + B**2))/-1
         }]
+
+def test_issue_24368():
+    # Ideally these would produce a solution, but for now just check that they
+    # don't fail with a RuntimeError
+    raises(NotImplementedError, lambda: solve(Mod(x**2, 49), x))
+    s2 = Symbol('s2', integer=True, positive=True)
+    f = floor(s2/2 - S(1)/2)
+    raises(NotImplementedError, lambda: solve((Mod(f**2/(f + 1) + 2*f/(f + 1) + 1/(f + 1), 1))*f + Mod(f**2/(f + 1) + 2*f/(f + 1) + 1/(f + 1), 1), s2))