Repository: sympy/sympy
Pull request: fixed is_integer of Mul by not using fraction but collecting numerators and denominators directly
#### References to other Issues or PRs
Fixes #20161

#### Brief description of what is fixed or changed
In Mul._eval_is_integer instead of using the function fraction the args are scanned for contributions to the numerator and denominator.

#### Other comments


#### Release Notes

<!-- BEGIN RELEASE NOTES -->
* core
  * Fixed a few broken cases of expr.is_integer
<!-- END RELEASE NOTES -->

Problem statement:
Inconsistent behavior for sympify/simplify with ceiling
In sympy v1.5.1:
```python
In [16]: sympy.sympify('4*ceiling(x/4 - 3/4)', evaluate=False).simplify()
Out[16]: 4*ceiling(x/4 - 3/4)

In [17]: sympy.sympify('4*ceiling(x/4 - 3/4)', evaluate=True).simplify()
Out[17]: 4*ceiling(x/4 - 3/4)
```

In sympy v.1.6.2:
```python
In [16]: sympy.sympify('4*ceiling(x/4 - 3/4)', evaluate=False).simplify()
Out[16]: 4*ceiling(x/4) - 3

In [17]: sympy.sympify('4*ceiling(x/4 - 3/4)', evaluate=True).simplify()
Out [17]: 4*ceiling(x/4 - 3/4)
```

Is there a way to ensure that the behavior is consistent, even though evaluate is equal to `False` when parsing?

Hints from issue discussion:
`4*ceiling(x/4) - 3` is simply wrong:
```python
>>> x = Symbol('x')
>>> (4*ceiling(x/4 - 3/4)).subs({x:0})
0
>>> (4*ceiling(x/4) - 3).subs({x:0})
-3
```
Boiling the problem further down we find that already a simpler expression is evaluated/transformed incorrectly:
```python
>>> sympy.sympify('ceiling(x-1/2)', evaluate=False)
ceiling(x) + (-1)*1*1/2
```
The `-1/2` is (under `evaluate=False`) constructed as `Mul(-1, Mul(1, Pow(2, -1)))`, for which the attribute `is_integer` is set incorrectly:
```python
>>> Mul(-1,Mul(1,Pow(2,-1,evaluate=False),evaluate=False),evaluate=False).is_integer
True
```
Since `ceiling` takes out all integer summands from its argument, it also takes out `(-1)*1*1/2`. Maybe somebody else can look into the problem, why `is_integer` is set wrongly for this expression.
The reason `is_integer` is incorrect for the expression is because it returns here:
https://github.com/sympy/sympy/blob/1b4529a95ef641c2fc15889091b281644069d20e/sympy/core/mul.py#L1274-L1277
That is due to
```julia
In [1]: e = Mul(-1,Mul(1,Pow(2,-1,evaluate=False),evaluate=False),evaluate=False)                                                              

In [2]: fraction(e)                                                                                                                            
Out[2]: (-1/2, 1)
```
It seems that the `1/2` is carried into the numerator by fraction giving a denominator of one.

You can see the fraction function here:
https://github.com/sympy/sympy/blob/1b4529a95ef641c2fc15889091b281644069d20e/sympy/simplify/radsimp.py#L1071-L1098

The check `term.is_Rational` will not match an unevaluated `Mul(1, Rational(1, 2), evaluate=False)` so that gets carried into the numerator.

Perhaps the root of the problem is the fact that we have unflattened args and `Mul.make_args` hasn't extracted them:
```julia
In [3]: Mul.make_args(e)                                                                                                                       
Out[3]: 
⎛      1⎞
⎜-1, 1⋅─⎟
⎝      2⎠
```
The `make_args` function does not recurse into the args:
https://github.com/sympy/sympy/blob/1b4529a95ef641c2fc15889091b281644069d20e/sympy/core/operations.py#L425-L428

I'm not sure if `make_args` should recurse. An easier fix would be to recurse into any nested Muls in `fraction`.
What about not setting `is_integer` if `evaluate=False` is set on an expression or one of its sub-expressions? Actually I think one cannot expect `is_integer` to be set correctly without evaluating.
That sounds like a good solution. As a safeguard, another one is to not remove the integer summands from `ceiling` if `evaluate=False`; it could be considered as an evaluation of ceiling w.r.t. its arguments.
There is no way to tell if `evaluate=False` was used in general when creating the `Mul`. It's also not possible in general to know if evaluating the Muls would lead to a different result without evaluating them. We should *not* evaluate the Muls as part of an assumptions query. If they are unevaluated then the user did that deliberately and it is not up to `_eval_is_integer` to evaluate them.

This was discussed when changing this to `fraction(..., exact=True)`: https://github.com/sympy/sympy/pull/19182#issuecomment-619398889

I think that using `fraction` at all is probably too much but we should certainly not replace that with something that evaluates the object.
Hm, does one really need to know whether `evaluate=False` was used? It looks like all we need is the expression tree to decide if `is_integer` is set to `True`. What about setting `is_integer=True` in a conservative way, i.e. only for these expression nodes:

- atoms: type `Integer`, constants `Zero` and `One` and symbols with appropriate assumptions
- `Add` and `Mul` if all args have `is_integer==True`
- `Pow` if base and exponent have `is_integer==True` and exponent is non-negative

I probably missed some cases, but you get the general idea. Would that work? The current implementation would only change in a few places, I guess - to a simpler form. Then also for `ceiling` we do not need to check for `evaluate=False`; its implementation could remain unchanged.
What you describe is more or less the way that it already works. You can find more detail in the (unmerged) #20090  

The code implementing this is in the `Mul._eval_is_integer` function I linked to above.
@oscarbenjamin @coproc Sorry for bugging, but are there any plans about this? We cannot use sympy with Python 3.8 anymore in our package because of this...
I explained a possible solution above:

> An easier fix would be to recurse into any nested Muls in `fraction`.

I think this just needs someone to make a PR for that. If the PR comes *very* quickly it can be included in the 1.7 release (I'm going to put out the RC just as soon as #20307 is fixed).

Commit message: convention: make symbol name equal to variable name

Patch to review:
diff --git a/sympy/core/mul.py b/sympy/core/mul.py
index 46f310b122a3..94a0ba8a0aca 100644
--- a/sympy/core/mul.py
+++ b/sympy/core/mul.py
@@ -1262,7 +1262,11 @@ def _eval_is_zero(self):
                     zero = None
         return zero
 
+    #_eval_is_integer = lambda self: _fuzzy_group(
+    #    (a.is_integer for a in self.args), quick_exit=True)
     def _eval_is_integer(self):
+        #return _fuzzy_group(
+        #    (a.is_integer for a in self.args), quick_exit=True)
         from sympy import fraction
         from sympy.core.numbers import Float
 
@@ -1270,19 +1274,35 @@ def _eval_is_integer(self):
         if is_rational is False:
             return False
 
-        # use exact=True to avoid recomputing num or den
-        n, d = fraction(self, exact=True)
-        if is_rational:
-            if d is S.One:
-                return True
-        if d.is_even:
-            if d.is_prime:  # literal or symbolic 2
-                return n.is_even
-            if n.is_odd:
-                return False  # true even if d = 0
-        if n == d:
-            return fuzzy_and([not bool(self.atoms(Float)),
-            fuzzy_not(d.is_zero)])
+        numerators = []
+        denominators = []
+        for a in self.args:
+            if a.is_integer:
+                numerators.append(a)
+            elif a.is_Rational:
+                n, d = a.as_numer_denom()
+                numerators.append(n)
+                denominators.append(d)
+            elif a.is_Pow:
+                b, e = a.as_base_exp()
+                if not b.is_integer or not e.is_integer: return
+                if e.is_negative:
+                    denominators.append(b)
+                elif e.is_positive:
+                    denominators.append(b)
+            else:
+                return
+
+        if not denominators:
+            return True
+
+        odd = lambda ints: all(i.is_odd for i in ints)
+        even = lambda ints: any(i.is_even for i in ints)
+
+        if odd(numerators) and even(denominators):
+            return False
+        elif even(numerators) and denominators == [2]:
+            return True
 
     def _eval_is_polar(self):
         has_polar = any(arg.is_polar for arg in self.args)
diff --git a/sympy/core/tests/test_arit.py b/sympy/core/tests/test_arit.py
index e05cdf6ac190..c4554ce1d6d4 100644
--- a/sympy/core/tests/test_arit.py
+++ b/sympy/core/tests/test_arit.py
@@ -374,7 +374,6 @@ def test_Mul_doesnt_expand_exp():
     assert (x**(-log(5)/log(3))*x)/(x*x**( - log(5)/log(3))) == sympify(1)
 
 def test_Mul_is_integer():
-
     k = Symbol('k', integer=True)
     n = Symbol('n', integer=True)
     nr = Symbol('nr', rational=False)
@@ -388,18 +387,27 @@ def test_Mul_is_integer():
     assert (nz/3).is_integer is None
     assert (nr/3).is_integer is False
     assert (x*k*n).is_integer is None
+    assert (e/2).is_integer is True
+    assert (e**2/2).is_integer is True
+    assert ((-1)**k*n).is_integer is True
+    assert (3*k*e/2).is_integer is True
+    assert (2*k*e/3).is_integer is None
     assert (e/o).is_integer is None
     assert (o/e).is_integer is False
     assert (o/i2).is_integer is False
-    assert Mul(o, 1/o, evaluate=False).is_integer is True
     assert Mul(k, 1/k, evaluate=False).is_integer is None
-    assert Mul(nze, 1/nze, evaluate=False).is_integer is True
-    assert Mul(2., S.Half, evaluate=False).is_integer is False
+    assert Mul(2., S.Half, evaluate=False).is_integer is None
 
     s = 2**2**2**Pow(2, 1000, evaluate=False)
     m = Mul(s, s, evaluate=False)
     assert m.is_integer
 
+    # broken in 1.6 and before, see #20161
+    xq = Symbol('xq', rational=True)
+    yq = Symbol('yq', rational=True)
+    assert (xq*yq).is_integer is None
+    e_20161 = Mul(-1,Mul(1,Pow(2,-1,evaluate=False),evaluate=False),evaluate=False)
+    assert e_20161.is_integer is not True # expand(e_20161) -> -1/2, but no need to see that in the assumption without evaluation
 
 def test_Add_Mul_is_integer():
     x = Symbol('x')


Code review comments:
diff_hunk: @@ -1262,27 +1262,47 @@ def _eval_is_zero(self):
                     zero = None
         return zero
 
+    #_eval_is_integer = lambda self: _fuzzy_group(
+    #    (a.is_integer for a in self.args), quick_exit=True)
     def _eval_is_integer(self):
+        #return _fuzzy_group(
+        #    (a.is_integer for a in self.args), quick_exit=True)
         from sympy import fraction
         from sympy.core.numbers import Float
 
         is_rational = self._eval_is_rational()
         if is_rational is False:
             return False
 
-        # use exact=True to avoid recomputing num or den
-        n, d = fraction(self, exact=True)
-        if is_rational:
-            if d is S.One:
-                return True
-        if d.is_even:
-            if d.is_prime:  # literal or symbolic 2
-                return n.is_even
-            if n.is_odd:
-                return False  # true even if d = 0
-        if n == d:
-            return fuzzy_and([not bool(self.atoms(Float)),
-            fuzzy_not(d.is_zero)])
+        numerators = []
+        denominators = []
+        for a in self.args:
+            if a.is_integer:
+                numerators.append(a)
+            elif a.is_Rational:
+                n, d = a.as_numer_denom()
+                numerators.append(n)
+                denominators.append(d)
+            elif a.is_Pow:
+                b, e = a.as_base_exp()
+                if not b.is_integer or not e.is_integer: return
+                if e.is_negative:
+                    denominators.append(b)
+                elif e.is_positive:
+                    denominators.append(b)
path: sympy/core/mul.py
text: @user1:
I think this needs an `else: return`. If we don't know whether e is positive or negative then we don't know if b is in the numerator or denominator so the subsequent logic is not valid.

@author:
You are right. I was implicitely assuming e.is_zero. Also the case e.is_positive is not needed - a.is_integer would already be triggered. (and the command inside was wrong: 'numerators.append(b)` would be needed)