How to resolve the algorithm Weird numbers step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Weird numbers step by step in the C++ programming language

Table of Contents

Problem Statement

In number theory, a weird number is a natural number that is abundant but not semiperfect (and therefore not perfect either). In other words, the sum of the proper divisors of the number (divisors including 1 but not itself) is greater than the number itself (the number is abundant), but no subset of those divisors sums to the number itself (the number is not semiperfect). For example:

Find and display, here on this page, the first 25 weird numbers.

Let's start with the solution:

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

Goal: Find and print the first 25 "weird" numbers, which are even numbers that are neither abundant nor semiperfect.

Implementation:

  1. divisors Function: Computes all divisors of a given integer n. It uses the fact that all divisors of a number come in pairs, so it only iterates up to the square root of n.

  2. abundant Function: Checks if a given number n is abundant, meaning the sum of its proper divisors (divisors excluding the number itself) is greater than n.

  3. semiperfect Function: Recursively checks if a given number n is semiperfect. A number is semiperfect if it can be expressed as the sum of one or more of its proper divisors.

  4. sieve Function: Uses a Sieve of Eratosthenes approach to compute a vector w, where w[i] is false if i is abundant or semiperfect, and true otherwise.

  5. main Function:

    • Calls sieve(17000) to compute the vector w for integers up to 17000.
    • Counts the first 25 weird numbers (even numbers that are neither abundant nor semiperfect) and prints them to the console.

Source code in the cpp programming language

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

std::vector<int> divisors(int n) {
    std::vector<int> divs = { 1 };
    std::vector<int> divs2;

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int j = n / i;
            divs.push_back(i);
            if (i != j) {
                divs2.push_back(j);
            }
        }
    }

    std::copy(divs.cbegin(), divs.cend(), std::back_inserter(divs2));
    return divs2;
}

bool abundant(int n, const std::vector<int> &divs) {
    return std::accumulate(divs.cbegin(), divs.cend(), 0) > n;
}

template<typename IT>
bool semiperfect(int n, const IT &it, const IT &end) {
    if (it != end) {
        auto h = *it;
        auto t = std::next(it);
        if (n < h) {
            return semiperfect(n, t, end);
        } else {
            return n == h
                || semiperfect(n - h, t, end)
                || semiperfect(n, t, end);
        }
    } else {
        return false;
    }
}

template<typename C>
bool semiperfect(int n, const C &c) {
    return semiperfect(n, std::cbegin(c), std::cend(c));
}

std::vector<bool> sieve(int limit) {
    // false denotes abundant and not semi-perfect.
    // Only interested in even numbers >= 2
    std::vector<bool> w(limit);
    for (int i = 2; i < limit; i += 2) {
        if (w[i]) continue;
        auto divs = divisors(i);
        if (!abundant(i, divs)) {
            w[i] = true;
        } else if (semiperfect(i, divs)) {
            for (int j = i; j < limit; j += i) {
                w[j] = true;
            }
        }
    }
    return w;
}

int main() {
    auto w = sieve(17000);
    int count = 0;
    int max = 25;
    std::cout << "The first 25 weird numbers:";
    for (int n = 2; count < max; n += 2) {
        if (!w[n]) {
            std::cout << n << ' ';
            count++;
        }
    }
    std::cout << '\n';
    return 0;
}

You may also check:How to resolve the algorithm Archimedean spiral step by step in the C programming language
You may also check:How to resolve the algorithm Thue-Morse step by step in the Go programming language
You may also check:How to resolve the algorithm Solve a Holy Knight's tour step by step in the Java programming language
You may also check:How to resolve the algorithm Short-circuit evaluation step by step in the Nim programming language
You may also check:How to resolve the algorithm Command-line arguments step by step in the Logo programming language