# Why Doesn't Mathematica Simplify Combinations of Quotients? (Integer Division)

I stumbled across this as part of a more complicated formula but it can be shown very simply:

In[1]:= f[x_] := Quotient[Quotient[x, 5], 7]; FullSimplify[f[x]]

Out[1]= Quotient[Quotient[x, 5], 7]

In[2]:= FullSimplify[f[x], Element[x, Integers] && x >= -1000 && x <= 1000]

Out[2]= Quotient[Quotient[x, 5], 7]

In[3]:= f[x] == Quotient[x, 35] /. x -> Range[-1000, 1000]

Out[3]= True


Why doesn't Mathematica make the simplification shown to be true in step 3?

EDIT 2: The following works for me, using the identity pointed out by RiemannZeta:

In[1]:= f[x_] := Quotient[Quotient[x, 5], 7]
FullSimplify[f[x]]
FullSimplify[FunctionExpand[f[x]]]

Out[2]= Quotient[Quotient[x, 5], 7]

Out[3]= Floor[1/7 Floor[x/5]]

In[4]:= Unprotect[Floor];
Floor[Floor[x_ Rational[1, m_]] Rational[1, n_]] :=
Floor[x/(n m)] /; Element[{m, n}, Integers] && m > 0 && n > 0
FunctionExpand[f[x]]
FunctionExpand[f[x] == Quotient[x, 35]]

Out[6]= Floor[x/35]

Out[7]= True

-

You could also use TransformationFunctions:

f[x_] := Quotient[Quotient[x, 5], 7];
quotsimp[Quotient[Quotient[x_, n_], m_]] /; Refine[Element[x, Integers]] := Quotient[x, n m]

Assuming[Element[x, Integers],
FullSimplify[f[x], TransformationFunctions -> {quotsimp, Automatic}]
]

(* Quotient[x, 35] *)

-
Interesting! I notice you include the assumption that x is an integer as part of this; is the simplification not valid if x is real or complex? I wonder if that's why Mathematica doesn't do it... – Craig Heath Jun 2 '14 at 17:27
Brief experimentation seems to show that if x is real or complex it is still valid, but if either of the divisors is real then it isn't. – Craig Heath Jun 2 '14 at 17:34
I'm not sure, I added that restriction because I saw you had the line FullSimplify[f[x], Element[x, Integers] && x >= -1000 && x <= 1000]. – Chip Hurst Jun 3 '14 at 1:56
The identity appears to hold for all x. First note Quotient[x, n] == Floor[x/n]. Next, see the second identity in the quotients section: en.wikipedia.org/wiki/Floor_and_ceiling_functions#Quotients. (in fact the identity there is more general!) – Chip Hurst Jun 3 '14 at 2:03
Very interesting! To see if I could get Mathematica to "understand" that identity (in the simple case where m==0), Floor[Floor[x/y]/z] /. Floor[Floor[a_/b_]/c_] -> Floor[a/(b c)] works, but when you make y or z a literal value, e.g. Floor[Floor[x/y]/7] the pattern doesn't match. It seems Mathematica is choosing to represent division by an integer as multiplication by its inverse; as this is no longer obviously an integer, and the identity doesn't hold if n is non-integer, I wonder if this is why the simplification isn't made? Thanks for the clue! – Craig Heath Jun 3 '14 at 17:54

You can make this happen without much trouble by defining your own version of Quotient:

q[x_, n_] := Quotient[x, n];
q[q[x_, n_], m_] := q[x, n m];


Here I've used q for shorthand. It is the same as quotient, but it also "knows" a rule for simplifying double Quotients. Hence

q[q[x,5],7]


gives the desired Quotient[x, 35].

-
Nice! I've added this workaround to the question. Wondering if applying this to the built-in Quotient function would break anything? – Craig Heath Jun 2 '14 at 17:04
There's always lots of ways to break things. It would make me nervous redefining the built-in function. At least with your own definition, you know right where the problem is. – bill s Jun 2 '14 at 17:07