This problem is not original. You will get detailed discussion at the book:
How to solve it: Modern Huristics by David B. Fogel and Michalewicz page 274.
So I knew the math soln but did not use it considering it a programming contest

. And Kisman's alternate solution was based on math.