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