Find Landau 's function for a given number N | Python3 program for the above approach ; To store Landau 's function of the number ; Function to return gcd of 2 numbers ; Function to return LCM of two numbers ; Function to find max lcm value among all representations of n ; Calculate Landau 's value ; Recursive function to find different ways in which n can be written as sum of atleast one positive integers ; Check if sum becomes n , consider this representation ; Start from previous element in the representation till n ; Include current element from representation ; Call function again with reduced sum ; Backtrack - remove current element from representation ; Function to find the Landau 's function ; Using recurrence find different ways in which n can be written as a sum of atleast one + ve integers ; Print the result ; Given N ; Function call
import sys NEW_LINE Landau = - sys . maxsize - 1 NEW_LINE def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b % a , a ) NEW_LINE DEDENT def lcm ( a , b ) : NEW_LINE INDENT return ( a * b ) // gcd ( a , b ) NEW_LINE DEDENT def findLCM ( arr ) : NEW_LINE INDENT global Landau NEW_LINE nth_lcm = arr [ 0 ] NEW_LINE for i in range ( 1 , len ( arr ) ) : NEW_LINE INDENT nth_lcm = lcm ( nth_lcm , arr [ i ] ) NEW_LINE DEDENT Landau = max ( Landau , nth_lcm ) NEW_LINE DEDENT def findWays ( arr , i , n ) : NEW_LINE INDENT if ( n == 0 ) : NEW_LINE INDENT findLCM ( arr ) NEW_LINE DEDENT for j in range ( i , n + 1 ) : NEW_LINE INDENT arr . append ( j ) NEW_LINE findWays ( arr , j , n - j ) NEW_LINE arr . pop ( ) NEW_LINE DEDENT DEDENT def Landau_function ( n ) : NEW_LINE INDENT arr = [ ] NEW_LINE findWays ( arr , 1 , n ) NEW_LINE print ( Landau ) NEW_LINE DEDENT N = 4 NEW_LINE Landau_function ( N ) NEW_LINE