Рубрики

Аликвотная последовательность

Учитывая число n, задача состоит в том, чтобы напечатать его последовательность аликвот. Аликвота Последовательность числа начинается с самого себя, остальные члены последовательности являются суммой собственных делителей предыдущего предыдущего члена. Например, Аликвотная последовательность для 10 равна 10, 8, 7, 1, 0. Последовательность может повторяться. Например, для 6 у нас есть бесконечная последовательность всех 6s. В таких случаях мы печатаем повторяющийся номер и останавливаемся.

Примеры:

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 

Важные моменты:

  • Числа, имеющие повторяющуюся последовательность Аликвота длины 1, называются совершенными числами . Например, 6 сумма его собственных делителей равна 6.
  • Числа, которые имеют повторяющуюся последовательность Аликвота длины 2, называются дружественными числами . Например, 220 — это Дружественный номер.
  • Числа, имеющие повторяющуюся последовательность Аликвоты длины 3, называются общительными числами.
  • Предполагается, что каждая аликвотная последовательность заканчивается одним из следующих способов
    • с простым числом, которое, в свою очередь, заканчивается 1, а затем 0.
    • идеальный номер
    • набор дружных или общительных номеров.

Решение в основном заключается в вычислении суммы всех собственных делителей предыдущего члена.

  • Если мы внимательно наблюдаем, делители числа n присутствуют в парах. Например, если n = 100, то все пары делителей: (1 100), (2,50), (4,25), (5,20), (10,10)
  • Используя этот факт, эффективно вычислить делители. При проверке делителей мы должны быть осторожны, если есть два равных делителя, как в случае (10, 10).
  • В таком случае мы возьмем только один из них при расчете суммы. Эта сумма будет содержать сумму всех возможных делителей, поэтому мы должны вычесть число n из суммы всех делителей, чтобы получить сумму соответствующих делителей.

Мы можем сгенерировать последовательность, сначала напечатав число n, а затем вычислив следующие члены, используя сумму подходящих делителей. Когда мы вычисляем следующий термин, мы проверяем, видели ли мы этот термин уже или нет. Если термин появляется снова, у нас есть повторяющаяся последовательность. Мы печатаем то же самое и разрываем цикл.

C ++

// Реализация оптимизированного подхода на C ++
// сгенерировать аликвотную последовательность
#include <bits/stdc++.h>

using namespace std;

  
// Функция для вычисления суммы всех собственных делителей

int getSum(int n)

{

    int sum = 0;  // 1 - правильный делитель

  

    // Обратите внимание, что этот цикл работает до квадратного корня

    // из n

    for (int i=1; i<=sqrt(n); i++)

    {

        if (n%i==0)

        {

            // Если делители равны, взять только один

            // их

            if (n/i == i)

                sum = sum + i;

  

            else // В противном случае взять оба

            {

                sum = sum + i;

                sum = sum + (n / i);

            }

        }

    }

  

    // вычисляем сумму только всех правильных делителей

    return sum - n;

}

  
// Функция для печати Аликвотной последовательности для ввода n.

void printAliquot(int n)

{

    // Распечатать первый член

    printf("%d ", n);

    unordered_set<int>  s;

    s.insert(n);

  

    int next = 0;

    while (n > 0)

    {

        // Рассчитать следующий термин из предыдущего

        n = getSum(n);

  

        if (s.find(n) != s.end())

        {

            cout << "\nRepeats with " << n;

            break;

        }

  

        // Распечатать следующий термин

        cout << n << " ";

        s.insert(n);

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    printAliquot(12);

    return 0;

}

Джава

// Java реализация Оптимизированного подхода
// сгенерировать аликвотную последовательность

import java.util.*;

  

class GFG 

{

  

    // Функция для расчета суммы

    // всех правильных делителей

    static int getSum(int n) 

    {

        int sum = 0; // 1 - правильный делитель

  

        // Обратите внимание, что этот цикл работает до

        // квадратный корень из n

        for (int i = 1; i <= Math.sqrt(n); i++)

        {

            if (n % i == 0

            {

                // Если делители равны, взять только один

                // их

                if (n / i == i) 

                {

                    sum = sum + i;

                }

                else // В противном случае взять оба

                {

                    sum = sum + i;

                    sum = sum + (n / i);

                }

            }

        }

  

        // вычисляем сумму только всех правильных делителей

        return sum - n;

    }

  

    // Функция для печати Аликвот

    // Последовательность для входа n.

    static void printAliquot(int n) 

    {

          

        // Распечатать первый член

        System.out.printf("%d ", n);

          

        TreeSet<Integer> s = new TreeSet<>();

        s.add(n);

  

        int next = 0;

        while (n > 0

        {

            // Рассчитать следующий термин из предыдущего

            n = getSum(n);

  

            if (s.contains(n) && n != s.last()) 

            {

                System.out.print("\nRepeats with " + n);

                break;

            }

  

            // Распечатать следующий термин

            System.out.print(n + " ");

            s.add(n);

        }

    }

  

    / * Код водителя * /

    public static void main(String[] args) 

    {

        printAliquot(12);

    }

}

  
// Этот код предоставлен Rajput-JI

python3

# Реализация оптимизированного подхода на Python
# генерировать последовательность аликвот

  

from math import sqrt

  
# Функция для вычисления суммы всех правильных делителей

def getSum(n):

    summ = 0 # 1 - правильный делитель

  

    # Обратите внимание, что этот цикл работает до квадратного корня

    № из п

    for i in range(1, int(sqrt(n)) + 1):

        if n % i == 0:

  

            # Если делители равны, возьмите только один

            # их

            if n // i == i:

                summ += i

  

            # В противном случае возьмите оба

            else:

                summ += i

                summ += n // i

  

    # вычислить сумму только всех правильных делителей

    return summ - n

  
# Функция для печати Аликвотной последовательности для входа n.

def printAliquot(n):

  

    # Распечатать первый термин

    print(n, end=" ")

    s = set()

    s.add(n)

  

    nextt = 0

    while n > 0:

  

        # Рассчитать следующий термин из предыдущего

        n = getSum(n)

  

        if n in s:

            print("Repeats with", n)

            break

  

        # Распечатать следующий термин

        print(n, end=" ")

        s.add(n)

  
Код водителя

if __name__ == "__main__":

    printAliquot(12)

  
# Этот код предоставлен
# sanjeev2552

C #

// C # реализация оптимизированного подхода
// сгенерировать аликвотную последовательность

using System;

using System.Collections.Generic;

  

class GFG 

  

    // Функция для расчета суммы

    // всех правильных делителей

    static int getSum(int n) 

    

        int sum = 0; // 1 - правильный делитель

  

        // Обратите внимание, что этот цикл работает до

        // квадратный корень из n

        for (int i = 1; i <= Math.Sqrt(n); i++) 

        

            if (n % i == 0) 

            

                // Если делители равны,

                // взять только один из них

                if (n / i == i) 

                

                    sum = sum + i; 

                

                else // В противном случае взять оба

                

                    sum = sum + i; 

                    sum = sum + (n / i); 

                

            

        

  

        // вычисляем сумму только всех правильных делителей

        return sum - n; 

    

  

    // Функция для печати Аликвот

    // Последовательность для входа n.

    static void printAliquot(int n) 

    

          

        // Распечатать первый член

        Console.Write(n+" "); 

          

        HashSet<int> s = new HashSet<int>(); 

        s.Add(n); 

  

        while (n > 0) 

        

              

            // Рассчитать следующий термин из предыдущего

            n = getSum(n); 

  

            if (s.Contains(n)) 

            

                Console.Write("\nRepeats with " + n); 

                break

            

  

            // Распечатать следующий термин

            Console.Write(n + " "); 

            s.Add(n); 

        

    

  

    / * Код водителя * /

    public static void Main(String[] args) 

    

        printAliquot(12); 

    

  
/ * Этот код был добавлен
от PrinciRaj1992 * /

Выход:

12 16 15 9 4 3 1 0 

Ссылка:
https://en.wikipedia.org/wiki/Aliquot_sequence

Эта статья предоставлена Суровым Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Аликвотная последовательность

0.00 (0%) 0 votes