Secuencia de alícuotas

Dado un número n, la tarea es imprimir su Secuencia de alícuotas. La secuencia alícuota de un número comienza consigo mismo, los términos restantes de la secuencia son la suma de los divisores propios del término inmediatamente anterior. Por ejemplo, la secuencia de alícuotas para 10 es 10, 8, 7, 1, 0. La secuencia puede repetirse. Por ejemplo, para 6, tenemos una secuencia infinita de todos los 6. En tales casos, imprimimos el número que se repite y paramos. Ejemplos:

Input:  n = 10
Output: 10 8 7 1 0
Sum of proper divisors of 10 is  5 + 2 + 1 = 8.
Sum of proper divisors of 8 is 4 + 2 + 1 = 7.
Sum of proper divisors of 7 is 1
Sum of proper divisors of 1 is 0
Note that there is no proper divisor of 1.

Input  : n = 6
Output : 6 
         Repeats with 6

Input : n = 12
Output : 12 16 15 9 4 3 1 0 

Puntos importantes:

  • Los números que tienen secuencias alícuotas repetidas de longitud 1 se llaman números perfectos . Por ejemplo 6, la suma de sus divisores propios es 6.
  • Los números que tienen secuencias alícuotas repetidas de longitud 2 se denominan números amistosos . Por ejemplo, 220 es un número amistoso.
  • Los números que tienen secuencias alícuotas repetidas de longitud 3 se denominan números sociables .
  • Se conjetura que cada secuencia alícuota termina de una de las siguientes maneras
    • con un número primo que a su vez termina en 1 y luego en 0.
    • un numero perfecto
    • un conjunto de números amistosos o sociables.

La solución radica principalmente en el cálculo de la suma de todos los divisores propios del término anterior.

  • Si observamos con atención, los divisores del número n están presentes en pares. Por ejemplo si n = 100, entonces todos los pares de divisores son: (1,100), (2,50), (4,25), (5,20), (10,10)
  • Usando este hecho, calcule eficientemente los divisores. Al comprobar los divisores tendremos que tener cuidado si hay dos divisores iguales como en el caso de (10, 10).
  • En tal caso tomaremos solamente uno de ellos en el cálculo de la suma. Esta suma contendrá la suma de todos los divisores posibles, por lo que debemos restar el número n de la suma de todos los divisores para obtener la suma de los divisores propios.

Podemos generar la secuencia imprimiendo primero el número n y luego calculando los siguientes términos usando la suma de los divisores propios. Cuando calculamos el siguiente término, verificamos si ya hemos visto este término o no. Si el término vuelve a aparecer, tenemos una secuencia repetitiva. Imprimimos lo mismo y rompemos el bucle. 

C++

// C++ implementation of Optimized approach
// to generate Aliquot Sequence
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate sum of all proper divisors
int getSum(int n)
{
    int sum = 0;  // 1 is a proper divisor
 
    // Note that this loop runs till square root
    // of n
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i==0)
        {
            // If divisors are equal, take only one
            // of them
            if (n/i == i)
                sum = sum + i;
 
            else // Otherwise take both
            {
                sum = sum + i;
                sum = sum + (n / i);
            }
        }
    }
 
    // calculate sum of all proper divisors only
    return sum - n;
}
 
// Function to print Aliquot Sequence for an input n.
void printAliquot(int n)
{
    // Print the first term
    printf("%d ", n);
    unordered_set<int>  s;
    s.insert(n);
 
    int next = 0;
    while (n > 0)
    {
        // Calculate next term from previous term
        n = getSum(n);
 
        if (s.find(n) != s.end())
        {
            cout << "\nRepeats with " << n;
            break;
        }
 
        // Print next term
        cout << n << " ";
        s.insert(n);
    }
}
 
/* Driver program to test above function */
int main()
{
    printAliquot(12);
    return 0;
}

Java

// Java implementation of Optimized approach
// to generate Aliquot Sequence
import java.util.*;
 
class GFG
{
 
    // Function to calculate sum
    // of all proper divisors
    static int getSum(int n)
    {
        int sum = 0; // 1 is a proper divisor
 
        // Note that this loop runs till 
        // square root of n
        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
                // If divisors are equal, take only one
                // of them
                if (n / i == i)
                {
                    sum = sum + i;
                }
                else // Otherwise take both
                {
                    sum = sum + i;
                    sum = sum + (n / i);
                }
            }
        }
 
        // calculate sum of all proper divisors only
        return sum - n;
    }
 
    // Function to print Aliquot
    // Sequence for an input n.
    static void printAliquot(int n)
    {
         
        // Print the first term
        System.out.printf("%d ", n);
         
        TreeSet<Integer> s = new TreeSet<>();
        s.add(n);
 
        int next = 0;
        while (n > 0)
        {
            // Calculate next term from previous term
            n = getSum(n);
 
            if (s.contains(n) && n != s.last())
            {
                System.out.print("\nRepeats with " + n);
                break;
            }
 
            // Print next term
            System.out.print(n + " ");
            s.add(n);
        }
    }
 
    /* Driver code */
    public static void main(String[] args)
    {
        printAliquot(12);
    }
}
 
// This code is contributed by Rajput-JI

Python3

# Python implementation of Optimized approach
# to generate Aliquot Sequence
 
from math import sqrt
 
# Function to calculate sum of all proper divisors
def getSum(n):
    summ = 0 # 1 is a proper divisor
 
    # Note that this loop runs till square root
    # of n
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
 
            # If divisors are equal, take only one
            # of them
            if n // i == i:
                summ += i
 
            # Otherwise take both
            else:
                summ += i
                summ += n // i
 
    # calculate sum of all proper divisors only
    return summ - n
 
# Function to print Aliquot Sequence for an input n.
def printAliquot(n):
 
    # Print the first term
    print(n, end=" ")
    s = set()
    s.add(n)
 
    nextt = 0
    while n > 0:
 
        # Calculate next term from previous term
        n = getSum(n)
 
        if n in s:
            print("Repeats with", n)
            break
 
        # Print next term
        print(n, end=" ")
        s.add(n)
 
# Driver Code
if __name__ == "__main__":
    printAliquot(12)
 
# This code is contributed by
# sanjeev2552

C#

// C# implementation of Optimized approach
// to generate Aliquot Sequence
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to calculate sum
    // of all proper divisors
    static int getSum(int n)
    {
        int sum = 0; // 1 is a proper divisor
 
        // Note that this loop runs till
        // square root of n
        for (int i = 1; i <= Math.Sqrt(n); i++)
        {
            if (n % i == 0)
            {
                // If divisors are equal, 
                // take only one of them
                if (n / i == i)
                {
                    sum = sum + i;
                }
                else // Otherwise take both
                {
                    sum = sum + i;
                    sum = sum + (n / i);
                }
            }
        }
 
        // calculate sum of all proper divisors only
        return sum - n;
    }
 
    // Function to print Aliquot
    // Sequence for an input n.
    static void printAliquot(int n)
    {
         
        // Print the first term
        Console.Write(n+" ");
         
        HashSet<int> s = new HashSet<int>();
        s.Add(n);
 
        while (n > 0)
        {
             
            // Calculate next term from previous term
            n = getSum(n);
 
            if (s.Contains(n))
            {
                Console.Write("\nRepeats with " + n);
                break;
            }
 
            // Print next term
            Console.Write(n + " ");
            s.Add(n);
        }
    }
 
    /* Driver code */
    public static void Main(String[] args)
    {
        printAliquot(12);
    }
}
 
/* This code has been contributed
by PrinciRaj1992*/

Javascript

// JavaScript implementation of Optimized approach
// to generate Aliquot Sequence
 
// Function to calculate sum of all proper divisors
function getSum(n){
    let sum = 0;  // 1 is a proper divisor
 
    // Note that this loop runs till square root
    // of n
    for (let i=1; i<= Math.sqrt(n); i++){
        if (n%i==0){
            // If divisors are equal, take only one
            // of them
            if (n/i == i){
                sum = sum + i;
            }
            else{
                // Otherwise take both
                sum = sum + i;
                sum = sum + Math.floor(n / i);
            }
        }
    }
 
    // calculate sum of all proper divisors only
    return sum - n;
}
 
// Function to print Aliquot Sequence for an input n.
function printAliquot(n){
    // Store the answer in temp array.
    const temp = new Array();
    temp.push(n);
  
    // Creating a set.
    const s = new Set();
    s.add(n);
     
    let next = 0;
    while (n > 0){
        // Calculate next term from previous term
        n = getSum(n);
 
        if (s.has(n)){
            console.log("Repeats with ");
            break;
        }
 
        // Print next term
        temp.push(n);
        s.add(n);
    }
    // Convert the given array to string
    // and print it.
    const ans = temp.join(' ');
    console.log(ans);
}
 
/* Driver program to test above function */
{
    printAliquot(12);
    return 0;
}
 
//The code is contributed by Gautam goel (gautamgoel962)

Producción:

12 16 15 9 4 3 1 0 

Referencia: https://en.wikipedia.org/wiki/Aliquot_sequence Este artículo es una contribución de Harsh Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *