Number of Co | Python3 program to count the pairs whose sum of digits is co - prime ; Recursive function to return the frequency of numbers having their sum of digits i ; Returns 1 or 0 ; Returns value of the dp if already stored ; Loop from digit 0 to 9 ; To change the tight to 1 ; Calling the recursive function to find the frequency ; Function to find out frequency of numbers from 1 to N having their sum of digits from 1 to 162 and store them in array ; Number to string conversion ; Calling the recursive function and pushing it into array ; Function to find the pairs ; Calling the formArray function of a - 1 numbers ; Calling the formArray function of b numbers ; Subtracting the frequency of higher number array with lower number array and thus finding the range of numbers from a to b having sum from 1 to 162 ; To find out total number of pairs which are co - prime ; Driver code ; Function to count the pairs
import math NEW_LINE def recursive ( idx , sum , tight , st , dp , num ) : NEW_LINE INDENT if ( idx == num ) : NEW_LINE INDENT return sum == 0 NEW_LINE DEDENT if ( dp [ idx ] [ tight ] [ sum ] != - 1 ) : NEW_LINE INDENT return dp [ idx ] [ tight ] [ sum ] NEW_LINE DEDENT ans = 0 NEW_LINE for d in range ( 10 ) : NEW_LINE INDENT newTight = False NEW_LINE if ( tight and ord ( st [ idx ] ) - ord ( '0' ) < d ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( tight and ord ( st [ idx ] ) - ord ( '0' ) == d ) : NEW_LINE INDENT newTight = True NEW_LINE DEDENT if ( sum >= d ) : NEW_LINE INDENT ans += recursive ( idx + 1 , sum - d , newTight , st , dp , num ) NEW_LINE DEDENT DEDENT dp [ idx ] [ tight ] [ sum ] = ans NEW_LINE return dp [ idx ] [ tight ] [ sum ] NEW_LINE DEDENT def formArray ( N ) : NEW_LINE INDENT dp = [ [ [ - 1 for x in range ( 166 ) ] for y in range ( 2 ) ] for z in range ( 20 ) ] NEW_LINE st = str ( N ) NEW_LINE num = len ( st ) NEW_LINE arr = [ ] NEW_LINE for i in range ( 1 , 163 ) : NEW_LINE INDENT arr . append ( recursive ( 0 , i , 1 , st , dp , num ) ) NEW_LINE DEDENT return arr NEW_LINE DEDENT def findPair ( a , b ) : NEW_LINE INDENT arr_smaller = formArray ( a - 1 ) NEW_LINE arr_greater = formArray ( b ) NEW_LINE for i in range ( len ( arr_greater ) ) : NEW_LINE INDENT arr_greater [ i ] -= arr_smaller [ i ] NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( 1 , 163 ) : NEW_LINE INDENT for j in range ( i + 1 , 163 ) : NEW_LINE INDENT if ( math . gcd ( i , j ) == 1 ) : NEW_LINE INDENT ans = ( ans + arr_greater [ i - 1 ] * arr_greater [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = 12 NEW_LINE b = 15 NEW_LINE print ( findPair ( a , b ) ) NEW_LINE DEDENT