given an integer numperfectsquares will return the minimum amount of perfect squares are required to sum to the specified number lagrange s foursquare theorem gives us that the answer will always be between 1 and 4 https en wikipedia orgwikilagrange27sfoursquaretheorem some examples number perfect squares representation answer 9 32 1 10 32 12 2 12 22 22 22 3 31 52 22 12 12 4 returns the smallest number of perfect squares that sum to the specified number return int between 1 4 if the number is a perfect square then we only need 1 number we check if https en wikipedia orgwikilegendre27sthreesquaretheorem holds and divide the number accordingly ie if the number can be written as a sum of 3 squares where the 02 is allowed which is possible for all numbers except those of the form 4a8b 7 if the number is of the form 4a8b 7 it can t be expressed as a sum of three or less excluding the 02 perfect squares if the number was of that form the previous while loop divided away the 4a so by now it would be of the form 8b 7 so check if this is the case and return 4 since it neccessarily must be a sum of 4 perfect squares in accordance with https en wikipedia orgwikilagrange27sfoursquaretheorem by now we know that the number wasn t of the form 4a8b 7 so it can be expressed as a sum of 3 or less perfect squares try first to express it as a sum of 2 perfect squares and if that fails we know finally that it can be expressed as a sum of 3 perfect squares returns the smallest number of perfect squares that sum to the specified number return int between 1 4 if the number is a perfect square then we only need 1 number we check if https en wikipedia org wiki legendre 27s_three square_theorem holds and divide the number accordingly ie if the number can be written as a sum of 3 squares where the 0 2 is allowed which is possible for all numbers except those of the form 4 a 8b 7 if the number is of the form 4 a 8b 7 it can t be expressed as a sum of three or less excluding the 0 2 perfect squares if the number was of that form the previous while loop divided away the 4 a so by now it would be of the form 8b 7 so check if this is the case and return 4 since it neccessarily must be a sum of 4 perfect squares in accordance with https en wikipedia org wiki lagrange 27s_four square_theorem by now we know that the number wasn t of the form 4 a 8b 7 so it can be expressed as a sum of 3 or less perfect squares try first to express it as a sum of 2 perfect squares and if that fails we know finally that it can be expressed as a sum of 3 perfect squares
import math

def num_perfect_squares(number):
    
    
    if int(math.sqrt(number))**2 == number:
        return 1

    
    
    
    while number > 0 and number % 4 == 0:
        number /= 4

    
    
    
    
    
    if number % 8 == 7:
        return 4

    
    
    
    for i in range(1, int(math.sqrt(number)) + 1):
        if int(math.sqrt(number - i**2))**2 == number - i**2:
            return 2

    return 3