Step by Step solution about How to resolve the algorithm Find largest left truncatable prime in a given base step by step in the C++ programming language

Code overview

The provided code aims to find the largest left-truncatable prime number for different bases ranging from 3 to 31. A left-truncatable prime is a prime number that remains prime when its digits are removed from the left.

Implementation details

Main function

• The program iterates over a range of bases (base) from 3 to 31.

largest_left_truncatable_prime function

• This function takes a base as input and returns the largest left-truncatable prime number in that base.

add_digit function

• It takes the current index i as input and recursively constructs left-truncatable primes by adding digits from right to left.

Algorithm

1. Initialization:

   • Initialize vectors powers and value to store powers of base and candidate numbers.

2. Recursion:

   • For each candidate number, the add_digit function is called to explore possible left extensions by adding digits from 1 to base - 1.
   • If the extended candidate is probably prime (checked using is_probably_prime), the recursion continues, and the candidate number is updated.

3. Pruning:

   • If the extended candidate is not probably prime, it is skipped.
   • Additionally, if the extended candidate exceeds the current largest left-truncatable prime found, it is further validated using a stronger primality test with 50 iterations before updating the result.

4. Base case:

   • The recursion terminates when i exceeds the size of value.

Output

The program prints the largest left-truncatable prime number found for each base in the specified range.

Example output

3: 7
4: 13
5: 37
6: 73
7: 223
8: 317
9: 521
10: 739
11: 107
13: 223
15: 113
17: 521
19: 373
21: 617
23: 109
25: 229
27: 407
29: 673
31: 823

#include <gmpxx.h>

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>

using big_int = mpz_class;

const unsigned int small_primes[] = {2,  3,  5,  7,  11, 13, 17, 19, 23,
                                     29, 31, 37, 41, 43, 47, 53, 59, 61,
                                     67, 71, 73, 79, 83, 89, 97};

bool is_probably_prime(const big_int& n, int reps) {
    return mpz_probab_prime_p(n.get_mpz_t(), reps) != 0;
}

big_int largest_left_truncatable_prime(unsigned int base) {
    std::vector<big_int> powers = {1};
    std::vector<big_int> value = {0};
    big_int result = 0;

    std::function<void(unsigned int)> add_digit = [&](unsigned int i) {
        if (i == value.size()) {
            value.resize(i + 1);
            powers.push_back(base * powers.back());
        }
        for (unsigned int d = 1; d < base; ++d) {
            value[i] = value[i - 1] + powers[i] * d;
            if (!is_probably_prime(value[i], 1))
                continue;
            if (value[i] > result) {
                if (!is_probably_prime(value[i], 50))
                    continue;
                result = value[i];
            }
            add_digit(i + 1);
        }
    };

    for (unsigned int i = 0; small_primes[i] < base; ++i) {
        value[0] = small_primes[i];
        add_digit(1);
    }
    return result;
}

int main() {
    for (unsigned int base = 3; base < 18; ++base) {
        std::cout << base << ": " << largest_left_truncatable_prime(base)
                  << '\n';
    }
    for (unsigned int base = 19; base < 32; base += 2) {
        std::cout << base << ": " << largest_left_truncatable_prime(base)
                  << '\n';
    }
}