Sum of all perfect square divisors of numbers from 1 to N | Python3 program to find the sum of all perfect square divisors of numbers from 1 to N ; Function for finding inverse of a number iteratively Here we will find the inverse of 6 , since it appears as denominator in the formula of sum of squares from 1 to N ; Store the value of the inverse of 6 once as we don 't need to call the function again and again ; Formula for finding the sum of first n squares ; No perfect square exists which is less than 4 ; Starting from 2 , present value of start is denoted here as curStart ; Finding end of the segment for which the contribution will be same ; Using the above mentioned formula to find ans % MOD ; Now for mthe next iteration start will become end + 1 ; Finally return the answer ; Driver Code ; Here we are adding x because we have not counted 1 as perfect squares so if u want to add it you can just add that number to the ans
from math import * NEW_LINE MOD = 1000000007 NEW_LINE def inv ( a ) : NEW_LINE INDENT o = 1 NEW_LINE p = MOD - 2 NEW_LINE while ( p > 0 ) : NEW_LINE INDENT if ( p % 2 == 1 ) : NEW_LINE INDENT o = ( o * a ) % MOD NEW_LINE DEDENT a = ( a * a ) % MOD NEW_LINE p >>= 1 NEW_LINE DEDENT return o NEW_LINE DEDENT inv6 = inv ( 6 ) NEW_LINE def sumOfSquares ( n ) : NEW_LINE INDENT n %= MOD NEW_LINE return ( ( ( n * ( n + 1 ) ) % MOD * ( 2 * n + 1 ) ) % MOD * inv6 ) % MOD NEW_LINE DEDENT def sums ( n ) : NEW_LINE INDENT if ( n < 4 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT curStart = 2 NEW_LINE ans = 0 NEW_LINE sqrtN = int ( sqrt ( n ) ) NEW_LINE while ( curStart <= n // curStart ) : NEW_LINE INDENT V = n // ( curStart * curStart ) NEW_LINE end = int ( sqrt ( n // V ) ) NEW_LINE ans += ( ( n // ( curStart * curStart ) % MOD * ( sumOfSquares ( end ) + MOD - sumOfSquares ( curStart - 1 ) ) ) % MOD ) NEW_LINE if ( ans >= MOD ) : NEW_LINE INDENT ans -= MOD NEW_LINE DEDENT curStart = end + 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT Input = [ 5 ] NEW_LINE for x in Input : NEW_LINE INDENT print ( " sum ▁ of ▁ all ▁ perfect ▁ " \ " square ▁ " , end = ' ' ) NEW_LINE print ( " divisors ▁ from ▁ 1 ▁ to " , x , " is : ▁ " , end = ' ' ) NEW_LINE print ( x + sums ( x ) ) NEW_LINE DEDENT DEDENT