Sum of kth powers of first n natural numbers | global array to store factorials ; function to calculate the factorials of all the numbers upto k ; function to return the binomial coeff ; nCr = ( n ! * ( n - r ) ! ) / r ! ; function to return the sum of the kth powers of n natural numbers ; when j is 1 ; calculating sum ( n ^ 1 ) of unity powers of n storing sum ( n ^ 1 ) for sum ( n ^ 2 ) ; if k == 1 then temp is the result ; for finding sum ( n ^ k ) removing 1 and n * KCk from ( n + 1 ) ^ k ; Removing all kC2 * sum ( n ^ ( k - 2 ) ) + ... + kCk - 1 * ( sum ( n ^ ( k - ( k - 1 ) ) ; storing the result for next sum of next powers of k ; Driver code
MAX_K = 15 NEW_LINE fac = [ 1 for i in range ( MAX_K ) ] NEW_LINE def factorial ( k ) : NEW_LINE INDENT fac [ 0 ] = 1 NEW_LINE for i in range ( 1 , k + 2 ) : NEW_LINE INDENT fac [ i ] = ( i * fac [ i - 1 ] ) NEW_LINE DEDENT DEDENT def bin ( a , b ) : NEW_LINE INDENT ans = fac [ a ] // ( fac [ a - b ] * fac [ b ] ) NEW_LINE return ans NEW_LINE DEDENT def sumofn ( n , k ) : NEW_LINE INDENT p = 0 NEW_LINE num1 , temp = 1 , 1 NEW_LINE arr = [ 1 for i in range ( 1000 ) ] NEW_LINE for j in range ( 1 , k + 1 ) : NEW_LINE INDENT if j == 1 : NEW_LINE INDENT num1 = ( n * ( n + 1 ) ) // 2 NEW_LINE arr [ p ] = num1 NEW_LINE p += 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp = pow ( n + 1 , j + 1 ) - 1 - n NEW_LINE for s in range ( 1 , j ) : NEW_LINE INDENT temp = temp - ( arr [ j - s - 1 ] * bin ( j + 1 , s + 1 ) ) NEW_LINE DEDENT temp = temp // ( j + 1 ) NEW_LINE arr [ p ] = temp NEW_LINE p += 1 NEW_LINE DEDENT DEDENT temp = arr [ p - 1 ] NEW_LINE return temp NEW_LINE DEDENT n , k = 5 , 2 NEW_LINE factorial ( k ) NEW_LINE print ( sumofn ( n , k ) ) NEW_LINE