Given a positive integer , find the minimum number of perfect square numbers that sum to . For example, can be written as (three squares) or (four squares). The answer is .
This is a dynamic programming problem, but logarithms appear when computing perfect squares. How many perfect squares are there up to ? About , and .
Before reading the solution, think about this: how would you find all perfect squares up to ? And how does the logarithm relate to the number of bits in ?