Prime numbers are prime no matter what base they are represented in.

A prime number in a base other than 10 may not look prime at first glance.

For instance: 19 base 10 is 25 in base 7.



Several different prime numbers may be expressed as the "same" string when converted to a different base.

 107 base 10 converted to base 6 == 255
 173 base 10 converted to base 8 == 255
 353 base 10 converted to base 12 == 255
 467 base 10 converted to base 14 == 255
 743 base 10 converted to base 18 == 255
 1277 base 10 converted to base 24 == 255
 1487 base 10 converted to base 26 == 255
 2213 base 10 converted to base 32 == 255


Task
Restricted to bases 2 through 36; find the strings that have the most different bases that evaluate to that string when converting prime numbers to a base.

Find the conversion string, the amount of bases that evaluate a prime to that string and the enumeration of bases that evaluate a prime to that string.

Display here, on this page, the string, the count and the list for all of the: 1 character, 2 character, 3 character, and 4 character strings that have the maximum base count that evaluate to that string.

Should be no surprise, the string '2' has the largest base count for single character strings.



Stretch goal
Do the same for the maximum 5 character string.



#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <primesieve.hpp>
 
class prime_sieve {
public:
    explicit prime_sieve(uint64_t limit);
    bool is_prime(uint64_t n) const {
        return n == 2 || ((n & 1) == 1 && sieve[n >> 1]);
    }
 
private:
    std::vector<bool> sieve;
};
 
prime_sieve::prime_sieve(uint64_t limit) : sieve((limit + 1) / 2, false) {
    primesieve::iterator iter;
    uint64_t prime = iter.next_prime(); // consume 2
    while ((prime = iter.next_prime()) <= limit) {
        sieve[prime >> 1] = true;
    }
}
 
template <typename T> void print(std::ostream& out, const std::vector<T>& v) {
    if (!v.empty()) {
        out << '[';
        auto i = v.begin();
        out << *i++;
        for (; i != v.end(); ++i)
            out << ", " << *i;
        out << ']';
    }
}
 
std::string to_string(const std::vector<unsigned int>& v) {
    static constexpr char digits[] =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    std::string str;
    for (auto i : v)
        str += digits[i];
    return str;
}
 
bool increment(std::vector<unsigned int>& digits, unsigned int max_base) {
    for (auto i = digits.rbegin(); i != digits.rend(); ++i) {
        if (*i + 1 != max_base) {
            ++*i;
            return true;
        }
        *i = 0;
    }
    return false;
}
 
void multi_base_primes(unsigned int max_base, unsigned int max_length) {
    prime_sieve sieve(static_cast<uint64_t>(std::pow(max_base, max_length)));
    for (unsigned int length = 1; length <= max_length; ++length) {
        std::cout << length
                  << "-character strings which are prime in most bases: ";
        unsigned int most_bases = 0;
        std::vector<
            std::pair<std::vector<unsigned int>, std::vector<unsigned int>>>
            max_strings;
        std::vector<unsigned int> digits(length, 0);
        digits[0] = 1;
        std::vector<unsigned int> bases;
        do {
            auto max = std::max_element(digits.begin(), digits.end());
            unsigned int min_base = 2;
            if (max != digits.end())
                min_base = std::max(min_base, *max + 1);
            if (most_bases > max_base - min_base + 1)
                continue;
            bases.clear();
            for (unsigned int b = min_base; b <= max_base; ++b) {
                if (max_base - b + 1 + bases.size() < most_bases)
                    break;
                uint64_t n = 0;
                for (auto d : digits)
                    n = n * b + d;
                if (sieve.is_prime(n))
                    bases.push_back(b);
            }
            if (bases.size() > most_bases) {
                most_bases = bases.size();
                max_strings.clear();
            }
            if (bases.size() == most_bases)
                max_strings.emplace_back(digits, bases);
        } while (increment(digits, max_base));
        std::cout << most_bases << '\n';
        for (const auto& m : max_strings) {
            std::cout << to_string(m.first) << " -> ";
            print(std::cout, m.second);
            std::cout << '\n';
        }
        std::cout << '\n';
    }
}
 
int main(int argc, char** argv) {
    unsigned int max_base = 36;
    unsigned int max_length = 4;
    for (int arg = 1; arg + 1 < argc; ++arg) {
        if (strcmp(argv[arg], "-max_base") == 0)
            max_base = strtoul(argv[++arg], nullptr, 10);
        else if (strcmp(argv[arg], "-max_length") == 0)
            max_length = strtoul(argv[++arg], nullptr, 10);
    }
    if (max_base > 62) {
        std::cerr << "Max base cannot be greater than 62.\n";
        return EXIT_FAILURE;
    }
    if (max_base < 2) {
        std::cerr << "Max base cannot be less than 2.\n";
        return EXIT_FAILURE;
    }
    multi_base_primes(max_base, max_length);
    return EXIT_SUCCESS;
}