How to resolve the algorithm Super-Poulet numbers step by step in the C++ programming language

Published on 7 June 2024 03:52 AM
#cpp

How to resolve the algorithm Super-Poulet numbers step by step in the C++ programming language

Table of Contents

Problem Statement

A super-Poulet number is a Poulet number (or Fermat pseudoprime to base 2) whose every divisor d evenly divides 2d − 2.

Let's start with the solution:

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

This C++ program generates and finds super-Poulet numbers up to a specified limit. Super-Poulet numbers are a type of Poulet number that meet specific mathematical conditions.

Here's a detailed explanation of the code:

  1. divisors Function:

    • Calculates all the divisors of an unsigned integer n.
    • Uses trial division to find divisors, including prime factors and their powers.
    • Returns a vector containing all the divisors in ascending order.

  2. modpow Function:

    • Computes modular exponentiation efficiently, which is used for modular arithmetic.
    • Takes three parameters: base, exp, and mod.
    • Returns (base^exp) % mod.

  3. is_prime Function:

    • Checks if an unsigned integer n is prime.
    • Uses Fermat's Little Theorem for quick prime checking.
    • Also includes special checks for numbers 2, 3, and 5 as they are known primes.

  4. is_poulet_number Function:

    • Checks if an unsigned integer n is a Poulet number.
    • Uses modpow to check if 2^(n-1) % n is equal to 1.
    • Additionally, makes sure that n is not a prime number (as primes are not Poulet numbers).

  5. is_sp_num Function:

    • Checks if an unsigned integer n is a super-Poulet number.
    • First, it calls is_poulet_number to verify that n is a Poulet number.
    • Then, it calculates the divisors of n using the divisors function.
    • It checks if all divisors of n (except for 1 and n itself) satisfy the condition 2^d % d = 2.
    • If all divisors meet this condition, it returns true, indicating that n is a super-Poulet number.

  6. main Function:

    • Sets the locale to use commas for number formatting.
    • Initializes n to 1 and count to 0.
    • Prints the first 20 super-Poulet numbers.
    • For various limits (10^6, 10^7, and 10^8), it finds the first super-Poulet number greater than that limit and prints its index and value.

Source code in the cpp programming language

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

std::vector<unsigned int> divisors(unsigned int n) {
    std::vector<unsigned int> result{1};
    unsigned int power = 2;
    for (; (n & 1) == 0; power <<= 1, n >>= 1)
        result.push_back(power);
    for (unsigned int p = 3; p * p <= n; p += 2) {
        size_t size = result.size();
        for (power = p; n % p == 0; power *= p, n /= p)
            for (size_t i = 0; i != size; ++i)
                result.push_back(power * result[i]);
    }
    if (n > 1) {
        size_t size = result.size();
        for (size_t i = 0; i != size; ++i)
            result.push_back(n * result[i]);
    }
    return result;
}

unsigned long long modpow(unsigned long long base, unsigned int exp,
                          unsigned int mod) {
    if (mod == 1)
        return 0;
    unsigned long long result = 1;
    base %= mod;
    for (; exp != 0; exp >>= 1) {
        if ((exp & 1) == 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
    }
    return result;
}

bool is_prime(unsigned int n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    if (n % 3 == 0)
        return n == 3;
    if (n % 5 == 0)
        return n == 5;
    static constexpr unsigned int wheel[] = {4, 2, 4, 2, 4, 6, 2, 6};
    for (unsigned int p = 7;;) {
        for (unsigned int w : wheel) {
            if (p * p > n)
                return true;
            if (n % p == 0)
                return false;
            p += w;
        }
    }
}

bool is_poulet_number(unsigned int n) {
    return modpow(2, n - 1, n) == 1 && !is_prime(n);
}

bool is_sp_num(unsigned int n) {
    if (!is_poulet_number(n))
        return false;
    auto div = divisors(n);
    return all_of(div.begin() + 1, div.end(),
                  [](unsigned int d) { return modpow(2, d, d) == 2; });
}

int main() {
    std::cout.imbue(std::locale(""));
    unsigned int n = 1, count = 0;
    std::cout << "First 20 super-Poulet numbers:\n";
    for (; count < 20; n += 2) {
        if (is_sp_num(n)) {
            ++count;
            std::cout << n << ' ';
        }
    }
    std::cout << '\n';
    for (unsigned int limit = 1000000; limit <= 10000000; limit *= 10) {
        for (;;) {
            n += 2;
            if (is_sp_num(n)) {
                ++count;
                if (n > limit)
                    break;
            }
        }
        std::cout << "\nIndex and value of first super-Poulet greater than "
                  << limit << ":\n#" << count << " is " << n << '\n';
    }
}

You may also check:How to resolve the algorithm Anadromes step by step in the Raku programming language
You may also check:How to resolve the algorithm Pascal's triangle/Puzzle step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Esthetic numbers step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Rosetta Code/Find unimplemented tasks step by step in the Maple programming language
You may also check:How to resolve the algorithm Flow-control structures step by step in the Fortran programming language