Check if a number can be expressed as sum of two Perfect powers | Function that returns true if n can be written as a ^ m + b ^ n ; Taking isSum boolean array for check the sum exist or not ; To store perfect squares ; Initially all sums as false ; If sum exist then push that sum into perfect square vector ; Mark all perfect powers as false ; Traverse each perfectPowers ; Calculating Sum with perfect powers array ; Given Number n ; Function call
def isSumOfPower ( n ) : NEW_LINE INDENT isSum = [ 0 ] * ( n + 1 ) NEW_LINE perfectPowers = [ ] NEW_LINE perfectPowers . append ( 1 ) NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT isSum [ i ] = False NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( isSum [ i ] == True ) : NEW_LINE INDENT perfectPowers . append ( i ) NEW_LINE continue NEW_LINE DEDENT j = i * i NEW_LINE while ( j > 0 and j < ( n + 1 ) ) : NEW_LINE INDENT isSum [ j ] = True NEW_LINE j *= i NEW_LINE DEDENT DEDENT for i in range ( len ( perfectPowers ) ) : NEW_LINE INDENT isSum [ perfectPowers [ i ] ] = False NEW_LINE DEDENT for i in range ( len ( perfectPowers ) ) : NEW_LINE INDENT for j in range ( len ( perfectPowers ) ) : NEW_LINE INDENT sum = ( perfectPowers [ i ] + perfectPowers [ j ] ) NEW_LINE if ( sum < ( n + 1 ) ) : NEW_LINE INDENT isSum [ sum ] = True NEW_LINE DEDENT DEDENT DEDENT return isSum [ n ] NEW_LINE DEDENT n = 9 NEW_LINE if ( isSumOfPower ( n ) ) : NEW_LINE INDENT print ( " true " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " false " ) NEW_LINE DEDENT