Verify A068994 up to 2^(10^10)

pow2-fast.cc

#include <iostream>
#include <cstdint>
#include <vector>

constexpr int64_t min_k = 12;     // 2^12 = 4096
constexpr int64_t max_k = 1e10;   // 2^(10^10)

static int64_t FindCounterexample(size_t digit_count) {
    std::vector<char> digits(digit_count);
    digits[0] = 1;
    for (int64_t k = 1; k <= max_k; ++k) {
        char carry = 0;
        char has_odd = 0;
        for (char &digit: digits) {
            digit = 2*digit + carry;
            carry = (digit >= 10);
            digit -= 10*carry;
            has_odd |= carry;
        }
        if (!has_odd && k >= min_k) {
            std::cerr << "2^" << k << " = ...";
            for (int i = digit_count - 1; i >= 0; --i) std::cerr << (char)(digits[i] + '0');
            std::cerr << " has no odd digits in the last " << digit_count << " digits\n";
            return k;
        }
    }
    return -1;
}

int main() {
    size_t digit_count = 2;
    while (FindCounterexample(digit_count) != -1) digit_count *= 2;
    std::cerr << "Found no counterexample between 2^" << min_k << " and 2^" << max_k << " (inclusive) using " << digit_count << " digits.\n";
}