# Factor Recursively

I'm looking for a way to factor a polynomial recursively. Consider the following example:

expr = Expand[(a + (b + c)^2)^2];
Factor@expr
Simplify@expr


While the last Simplify statement gives back the original form (a + (b + c)^2)^2, Factor only factors the outer level and gives (a + b^2 + 2 b c + c^2)^2. Is there a way to factor recursively such as to produce the same output as after Simplify?

EDIT The previous statement of the question might not be completely right, and as Daniel pointed out in his comment, I'm looking for a way to factorise polynomials for which only parts factorise.

I just wrote a very crude function in Mathematica that does the job only for the simplest examples (the third example below is already not working), but it's in fact even slower than Simplify:

myFactor[s_Plus] := With[{l = List @@ s},
attempts = (Factor@*Plus @@ # +
Factor@*Plus @@ Complement[l, #] &) /@
Subsets[l, Floor[Length[l]/2]];
DeleteDuplicates@MinimalBy[ByteCount]@attempts
]

expr1 = a + (b + c)^2 // Expand
expr2 = a + (b + c) (d + e) // Expand
expr3 = (a + b)^2 + (c + d)^3 + e + f + 2 d + 3 a // Expand
(* gives *)
(* a + b^2 + 2 b c + c^2 *)
(* a + b d + c d + b e + c e *)
(* 3 a + a^2 + 2 a b + b^2 + c^3 + 2 d + 3 c^2 d + 3 c d^2 + d^3 + e + f *)

myFactor /@ {expr1, expr2, expr3} // ColumnForm
(* gives *)
(* {a + (b + c)^2} *)
(* {a + (b + c) (d + e)} *)
(* {3 a + a^2 + 2 a b + b^2 + 2 d + (c + d)^3 + e + f} *)


This is a very simple approach where I just split the sum into two parts, try to factorise those, and then sum again. For the last example to work one would probably need something recursive, but given that the performance doesn't seem great, I'm wondering if this approach is worth exploring at all. The only reason I want to avoid Simplify is for performance reasons, as I assume it's going to try a lot of different simplification strategies, which I know I don't want to apply.

• (a + (b + c)^2) is not a factored exporession. I mention this to indicate that the problem you are trying to solve is probably much harder than the problem you state (since e.g. Map can be used to effect factorization at multiple levels). – Daniel Lichtblau Jul 14 '17 at 23:55
• Hi Daniel, you're totally right, I didn't see the full problem here. So I guess my question should be as follows: given a polynomial in some variables which doesn't factorise, but parts of which do, is there a way to find these factorisations without using the command Simplify. – Stan Jul 17 '17 at 23:50

As noted in the question,

Factor[expr]
(* (a + b^2 + 2 b c + c^2)^2 *)


The question, then, is how to transform a + b^2 + 2 b c + c^2 into a + (b + c)^2. Because the former has no common factors, Factor alone cannot do the job. It needs the assistance of some other function. Here are two possibilities.

(Factor[# - a] + a) & /@ Factor[expr]
(* (a + (b + c)^2)^2 *)

Collect[#, a, Factor] & /@ Factor[expr]
(* (a + (b + c)^2)^2 *)


Whether either of these constitutes factoring recursively is in the eye of the beholder.

• Hi bbgodfrey, thanks for the reply. It works for this particular example, but I'm looking for something that would work for general expressions. I think when I asked the question, I didn't properly understand why Factor wouldn't give the desired result. See comments under my question. – Stan Jul 17 '17 at 23:50
• @Stan I made the same remark in my answer, "Because the former has no common factors, Factor alone cannot do the job." If factoring is possible at every level, then as Daniel Lichtblau commented, Factor with Map will work. – bbgodfrey Jul 18 '17 at 1:02
• sorry bbgodfrey, you're totally right! :) – Stan Jul 18 '17 at 7:34