# Why doesn't FullSimplify work properly on this?

I wish to simplify the simple expression fac[n_] := Sum[R^i, {i, 0, n}]; as much as possible for various $n$. FullSimplify or Factor work on this, but not always, as good as it should be. For example, in the sixth line of

Table[{fac[j], fac[j] // FullSimplify, fac[j] // Factor}, {j, 1, 8}] // TableForm


it seems that FullSimplify does not work at all!?

$1+R+R^2+R^3+R^4+R^5+R^6$ has not been simplified! It is well-known that $$1+R+R^2+R^3+R^4+R^5+R^6=1+(R+R^4)(1+R+R^2).$$

So, now my question is: Is there any way in Mathematica to obtain the very simplified form of the expression fac[n_] := Sum[R^i, {i, 0, n}];, just like $1+(R+R^4)(1+R+R^2)$ or even simpler for various $n$?

I will be grateful if anyone can give me some tips.

-
Why not just Sum[R^i, {i, 0, n}]? –  belisarius Nov 19 '13 at 19:16
Note that $1+R+R^2+R^3+R^4+R^5+R^6$ requires 5 multiplications to be implemented, while $1+(R+R^4)(1+R+R^2)$ requires only 3! That is why a more factorized form is desirable. –  Fazlollah Soleymani Nov 19 '13 at 20:41
Please execute the command I wrote above –  belisarius Nov 19 '13 at 21:08
"More factorized" and "fewer multiplications" are not the same as "simple". –  bill s Feb 18 at 0:43

You can try to write your own ComplexityFunction for the task. For instance, this function produces different results from default:

FullSimplify[Sum[R^i, {i, 0, 6}],
ComplexityFunction -> (2 Count[#, Plus, Infinity, Heads -> True] +
Total@Cases[#, _^n_ :> n, Infinity] &)]


1 + R (1 + R) (1 - R + R^2) (1 + R + R^2)

It's not what you were looking for, though. You can try to change ComplexityFunction and look at what kind of search space FullSimplify looks through with something like this, which sows all expressions passed to ComplexityFunction:

Reap[FullSimplify[Sum[R^i, {i, 0, 6}],
ComplexityFunction -> ((Sow[#]; LeafCount[#]) &)]] // Last


Results are not particularly promising in this case, though; it would seem FullSimplify doesn't visit a single time those alternatives you wanted to see. I'm not certain of it, but the complexity function in use might also affect the direction simplification tries to pursue. (By the way, transformations in use can be augmented through TransformationFunctions.)

Completely different route for this kinds of optimizations is to look on answers related to Compile. Some effort to exactly the direction you were interested of (minimizing amount of multiplications) has been pursued by others on Mma.SE.

-