The "no factorial is a perfect square" is used to justify why square roots are applied before any factorial on a given node of the evaluation tree.
No factorial is applied on a non integer intermediate result indeed, but if the intermediate result "becomes integer again", factorial are tried.
For example, if a candidate is (1/2) * 3 * 4 + 5, then the algorithm won't try to compute any factorial of (1/2) * 3 = 1.5, but it will consider (1/2) * 3 * 4 = 6.0 as integer and try the factorial on 6.
You've missed my point. Why do you not consider sqrt(3!)? It's not integral, but if you multiply by sqrt(6), the result IS integral. I don't think an optimal solution will have non-integral subexpressions, but you need an argument to justify that. Or you need to include them in your brute force search.
That's right, sorry I missed your point. I edited the post accordingly, thanks a lot for your input!
Note however that I did not pretend to have an exhaustive search, just a "brute" one to find a solution. I changed "enumerating all the candidate" to "enumerating the candidate" to remove some confusion.
Comments
The "no factorial is a perfect square" is used to justify why square roots are applied before any factorial on a given node of the evaluation tree.
No factorial is applied on a non integer intermediate result indeed, but if the intermediate result "becomes integer again", factorial are tried.
For example, if a candidate is (1/2) * 3 * 4 + 5, then the algorithm won't try to compute any factorial of (1/2) * 3 = 1.5, but it will consider (1/2) * 3 * 4 = 6.0 as integer and try the factorial on 6.
You've missed my point. Why do you not consider sqrt(3!)? It's not integral, but if you multiply by sqrt(6), the result IS integral. I don't think an optimal solution will have non-integral subexpressions, but you need an argument to justify that. Or you need to include them in your brute force search.
That's right, sorry I missed your point. I edited the post accordingly, thanks a lot for your input!
Note however that I did not pretend to have an exhaustive search, just a "brute" one to find a solution. I changed "enumerating all the candidate" to "enumerating the candidate" to remove some confusion.