How to resolve the algorithm Ruth-Aaron numbers step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Ruth-Aaron numbers step by step in the C++ programming language

Table of Contents

Problem Statement

A Ruth–Aaron pair consists of two consecutive integers (e.g., 714 and 715) for which the sums of the prime divisors of each integer are equal. So called because 714 is Babe Ruth's lifetime home run record; Hank Aaron's 715th home run broke this record and 714 and 715 have the same prime divisor sum.

A Ruth–Aaron triple consists of three consecutive integers with the same properties.

There is a second variant of Ruth–Aaron numbers, one which uses prime factors rather than prime divisors. The difference; divisors are unique, factors may be repeated. The 714, 715 pair appears in both, so the name still fits.

It is common to refer to each Ruth–Aaron group by the first number in it.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Ruth-Aaron numbers step by step in the C++ programming language

This code in C++ finds and prints the first 30 Ruth-Aaron numbers using two different methods: sum of prime factors and sum of prime divisors. Additionally, it finds and prints the first Ruth-Aaron triple for both methods.

A Ruth-Aaron number is a positive integer whose sum of prime factors (or sum of prime divisors) is equal to the sum of prime factors (or sum of prime divisors) of the next consecutive integer.

Here's how the code works:

  1. Main Function:

    • main() function initializes variables and sets a limit of 30 for finding Ruth-Aaron numbers.
    • It then prints the first 30 Ruth-Aaron numbers based on prime factors and divisors separately.
    • Finally, it finds and prints the first Ruth-Aaron triple for both methods.

  2. Prime Factor and Divisor Functions:

    • prime_factor_sum(n): This function calculates the sum of the prime factors of the integer n. It uses bitwise operations to efficiently check for factors of 2 and then applies a loop to check for odd prime factors up to the square root of n.
    • prime_divisor_sum(n): Similar to prime_factor_sum, this function calculates the sum of the prime divisors of n. It uses a modified version of the algorithm used for prime factor sum to avoid counting the same prime multiple times when it occurs as a divisor.

  3. Printing Ruth-Aaron Numbers:

    • The code uses two loops to iterate through integers starting from 2.
    • For each integer n, it calculates the sum of prime factors or divisors for n and the next integer n+1.
    • If the sums match, indicating a Ruth-Aaron number, it prints n-1 (since the code starts with 2 but the problem statement asks for the first Ruth-Aaron number to be 1).
    • It also keeps track of the count to print 10 numbers per line.

  4. Finding Ruth-Aaron Triples:

    • After printing the first 30 Ruth-Aaron numbers, the code looks for the first Ruth-Aaron triple.
    • It does this by continuing the loops and checking for consecutive integers where the last three sums for either prime factors or divisors match.
    • When a triple is found, it prints the result.

Source code in the cpp programming language

#include <iomanip>
#include <iostream>

int prime_factor_sum(int n) {
    int sum = 0;
    for (; (n & 1) == 0; n >>= 1)
        sum += 2;
    for (int p = 3, sq = 9; sq <= n; p += 2) {
        for (; n % p == 0; n /= p)
            sum += p;
        sq += (p + 1) << 2;
    }
    if (n > 1)
        sum += n;
    return sum;
}

int prime_divisor_sum(int n) {
    int sum = 0;
    if ((n & 1) == 0) {
        sum += 2;
        n >>= 1;
        while ((n & 1) == 0)
            n >>= 1;
    }
    for (int p = 3, sq = 9; sq <= n; p += 2) {
        if (n % p == 0) {
            sum += p;
            n /= p;
            while (n % p == 0)
                n /= p;
        }
        sq += (p + 1) << 2;
    }
    if (n > 1)
        sum += n;
    return sum;
}

int main() {
    const int limit = 30;
    int dsum1 = 0, fsum1 = 0, dsum2 = 0, fsum2 = 0;

    std::cout << "First " << limit << " Ruth-Aaron numbers (factors):\n";
    for (int n = 2, count = 0; count < limit; ++n) {
        fsum2 = prime_factor_sum(n);
        if (fsum1 == fsum2) {
            ++count;
            std::cout << std::setw(5) << n - 1
                      << (count % 10 == 0 ? '\n' : ' ');
        }
        fsum1 = fsum2;
    }

    std::cout << "\nFirst " << limit << " Ruth-Aaron numbers (divisors):\n";
    for (int n = 2, count = 0; count < limit; ++n) {
        dsum2 = prime_divisor_sum(n);
        if (dsum1 == dsum2) {
            ++count;
            std::cout << std::setw(5) << n - 1
                      << (count % 10 == 0 ? '\n' : ' ');
        }
        dsum1 = dsum2;
    }

    dsum1 = 0, fsum1 = 0, dsum2 = 0, fsum2 = 0;
    for (int n = 2;; ++n) {
        int fsum3 = prime_factor_sum(n);
        if (fsum1 == fsum2 && fsum2 == fsum3) {
            std::cout << "\nFirst Ruth-Aaron triple (factors): " << n - 2
                      << '\n';
            break;
        }
        fsum1 = fsum2;
        fsum2 = fsum3;
    }
    for (int n = 2;; ++n) {
        int dsum3 = prime_divisor_sum(n);
        if (dsum1 == dsum2 && dsum2 == dsum3) {
            std::cout << "\nFirst Ruth-Aaron triple (divisors): " << n - 2
                      << '\n';
            break;
        }
        dsum1 = dsum2;
        dsum2 = dsum3;
    }
}

You may also check:How to resolve the algorithm Curzon numbers step by step in the C programming language
You may also check:How to resolve the algorithm Sorting algorithms/Bogosort step by step in the Raku programming language
You may also check:How to resolve the algorithm FizzBuzz step by step in the LaTeX programming language
You may also check:How to resolve the algorithm Factorial step by step in the Axe programming language
You may also check:How to resolve the algorithm IBAN step by step in the Oberon-2 programming language