Encuentra la función de Landau para un número dado N

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es encontrar la función de Landau del número N.

En teoría de números, la función de Landau encuentra el MCM más grande entre todas las particiones del número dado N.

Por ejemplo: si N = 4, las posibles particiones son:
1. {1, 1, 1, 1}, MCM = 1
2. {1, 1, 2}, MCM = 2
3. {2, 2}, MCM = 2
4. {1, 3}, MCM = 3

Entre las particiones anteriores, las particiones cuyo LCM es máximo es {1, 3} como LCM = 3.

Ejemplos:

Entrada: N = 4
Salida: 4
Explicación: Las
particiones de 4 son [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4] entre las cuales máximo LCM es de la última partición 4 cuyo LCM también es 4.

Entrada: N = 7
Salida: 12
Explicación:
Para N = 7 el MCM máximo es 12.

Enfoque: La idea es usar Recursión para generar todas las particiones posibles para el número N dado y encontrar el valor máximo de LCM entre todas las particiones. Considere cada número entero de 1 a N tal que la suma N se pueda reducir por este número en cada llamada recursiva y si en cualquier llamada recursiva N se reduce a cero , entonces encuentre el MCM del valor almacenado en el vector . A continuación se muestran los pasos para la recursividad:
 

  1. Obtenga el número N cuya suma debe dividirse en dos o más números enteros positivos.
  2. Iterar recursivamente del valor 1 a N como índice i :
    • Caso base: si el valor llamado de forma recursiva es 0 , encuentre el MCM del valor almacenado en el vector actual, ya que esta es la forma de dividir N en dos o más enteros positivos. 
       
if (n == 0)
    findLCM(arr);
  • Llamada recursiva: si no se cumple el caso base, iterar recursivamente desde [i, N – i] . Empuje el elemento j actual en el vector (digamos arr ) e itere recursivamente para el siguiente índice y después de que finalice esta recursión, extraiga el elemento j insertado anteriormente: 
     
for j in range[i, N]:
    arr.push_back(j);
    recursive_function(arr, j + 1, N - j);
    arr.pop_back(j);
  1. Después de toda la llamada recursiva, imprima el máximo de todos los LCM calculados.

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// To store Landau's function of the number
int Landau = INT_MIN;
 
// Function to return gcd of 2 numbers
int gcd(int a, int b)
{
 
    if (a == 0)
 
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return LCM of two numbers
int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}
 
// Function to find max lcm value
// among all representations of n
void findLCM(vector<int>& arr)
{
    int nth_lcm = arr[0];
 
    for (int i = 1; i < arr.size(); i++)
 
        nth_lcm = lcm(nth_lcm, arr[i]);
 
    // Calculate Landau's value
    Landau = max(Landau, nth_lcm);
}
 
// Recursive function to find different
// ways in which n can be written as
// sum of atleast one positive integers
void findWays(vector<int>& arr, int i, int n)
{
    // Check if sum becomes n,
    // consider this representation
    if (n == 0)
        findLCM(arr);
 
    // Start from previous element
    // in the representation till n
    for (int j = i; j <= n; j++) {
 
        // Include current element
        // from representation
        arr.push_back(j);
 
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // Backtrack - remove current
        // element from representation
        arr.pop_back();
    }
}
 
// Function to find the Landau's function
void Landau_function(int n)
{
    vector<int> arr;
 
    // Using recurrence find different
    // ways in which n can be written
    // as a sum of atleast one +ve integers
    findWays(arr, 1, n);
 
    // Print the result
    cout << Landau;
}
 
// Driver Code
int main()
{
    // Given N
    int N = 4;
 
    // Function Call
    Landau_function(N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// To store Landau's function of the number
static int Landau = Integer.MIN_VALUE;
 
// Function to return gcd of 2 numbers
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return LCM of two numbers
static int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}
 
// Function to find max lcm value
// among all representations of n
static void findLCM(Vector<Integer> arr)
{
    int nth_lcm = arr.get(0);
 
    for(int i = 1; i < arr.size(); i++)
        nth_lcm = lcm(nth_lcm, arr.get(i));
 
    // Calculate Landau's value
    Landau = Math.max(Landau, nth_lcm);
}
 
// Recursive function to find different
// ways in which n can be written as
// sum of atleast one positive integers
static void findWays(Vector<Integer> arr,
                     int i, int n)
{
     
    // Check if sum becomes n,
    // consider this representation
    if (n == 0)
        findLCM(arr);
 
    // Start from previous element
    // in the representation till n
    for(int j = i; j <= n; j++)
    {
         
        // Include current element
        // from representation
        arr.add(j);
 
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // Backtrack - remove current
        // element from representation
        arr.remove(arr.size() - 1);
    }
}
 
// Function to find the Landau's function
static void Landau_function(int n)
{
    Vector<Integer> arr = new Vector<>();
 
    // Using recurrence find different
    // ways in which n can be written
    // as a sum of atleast one +ve integers
    findWays(arr, 1, n);
 
    // Print the result
    System.out.print(Landau);
}
 
// Driver Code
public static void main(String[] args)
{
    // Given N
    int N = 4;
 
    // Function call
    Landau_function(N);
}
}
 
// This code is contributed by amal kumar choubey

Python3

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

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// To store Landau's function of the number
static int Landau = int.MinValue;
 
// Function to return gcd of 2 numbers
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return LCM of two numbers
static int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}
 
// Function to find max lcm value
// among all representations of n
static void findLCM(List<int> arr)
{
    int nth_lcm = arr[0];
 
    for(int i = 1; i < arr.Count; i++)
        nth_lcm = lcm(nth_lcm, arr[i]);
 
    // Calculate Landau's value
    Landau = Math.Max(Landau, nth_lcm);
}
 
// Recursive function to find different
// ways in which n can be written as
// sum of atleast one positive integers
static void findWays(List<int> arr,
                     int i, int n)
{
     
    // Check if sum becomes n,
    // consider this representation
    if (n == 0)
        findLCM(arr);
 
    // Start from previous element
    // in the representation till n
    for(int j = i; j <= n; j++)
    {
         
        // Include current element
        // from representation
        arr.Add(j);
 
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // Backtrack - remove current
        // element from representation
        arr.RemoveAt(arr.Count - 1);
    }
}
 
// Function to find the Landau's function
static void Landau_function(int n)
{
    List<int> arr = new List<int>();
 
    // Using recurrence find different
    // ways in which n can be written
    // as a sum of atleast one +ve integers
    findWays(arr, 1, n);
 
    // Print the result
    Console.Write(Landau);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N
    int N = 4;
 
    // Function call
    Landau_function(N);
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
 
// Javascript program for the above approach
 
// To store Landau's function of the number
var Landau = -1000000000;
 
// Function to return gcd of 2 numbers
function gcd(a, b)
{
 
    if (a == 0)
 
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return LCM of two numbers
function lcm(a, b)
{
    return (a * b) / gcd(a, b);
}
 
// Function to find max lcm value
// among all representations of n
function findLCM(arr)
{
    var nth_lcm = arr[0];
 
    for (var i = 1; i < arr.length; i++)
 
        nth_lcm = lcm(nth_lcm, arr[i]);
 
    // Calculate Landau's value
    Landau = Math.max(Landau, nth_lcm);
}
 
// Recursive function to find different
// ways in which n can be written as
// sum of atleast one positive integers
function findWays(arr, i, n)
{
    // Check if sum becomes n,
    // consider this representation
    if (n == 0)
        findLCM(arr);
 
    // Start from previous element
    // in the representation till n
    for (var j = i; j <= n; j++) {
 
        // Include current element
        // from representation
        arr.push(j);
 
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // Backtrack - remove current
        // element from representation
        arr.pop();
    }
}
 
// Function to find the Landau's function
function Landau_function(n)
{
    arr = [];
 
    // Using recurrence find different
    // ways in which n can be written
    // as a sum of atleast one +ve integers
    findWays(arr, 1, n);
 
    // Print the result
    document.write( Landau);
}
 
// Driver Code
// Given N
var N = 4;
 
// Function Call
Landau_function(N);
 
// This code is contributed by rrrtnx.
</script>
Producción: 

4

 

Complejidad de Tiempo: O(2 N ) 
Espacio Auxiliar: O(N 2 ) 
 

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *