Some clues:
Code:
* Splitting a 1 out of the number makes things worse unless (unless the number is 1).
E.g. 2 -> 1+1 -> 1*1 = 1 which is less than 2.
* Splitting 4 -> 2+2 -> 2*2 = 4, so splitting out a 4 is the same as splitting out 2 2s.
* Splitting 5 -> 2+3 -> 2*3 = 6 which is larger than 5.
Therefore split the number only into 2s, 3s and 4s (or just into 2s and 3s since 4s can be split into 2 2s).
* Splitting 6 -> 2+2+2 -> 2*2*2 = 8, but 6 -> 3+3 -> 3*3 = 9.
9 is larger than 8, so splitting out 3s is preferable to splitting out 2s (or 4s),
except when that would leave a 1 remaining.
Conclusion:
Code:
* If N > 3 and N ≡ 0 (mod 3) then only split out 3s.
* If N > 3 and N ≡ 1 (mod 3) then split out a single 4 (or 2 2s) and only split out 3s for any remaining part.
* If N > 3 and N ≡ 2 (mod 3) then split out a single 2 and only split out 3s for the remaining part.
* If N < 4 then leave it as is.
For example:
Code:
7 -> 4+3 -> 4*3 = 12 (or 7 -> 2+2+3 -> 2*2*3 = 12)
8 -> 2+3+3 -> 2*3*3 = 18
9 -> 3+3+3 -> 3*3*3 = 27
10 -> 4+3+3 -> 4*3*3 = 36