powers of 2 ending in many nines

pow2.cc

#include <cinttypes>
#include <cstdlib>
#include <iostream>

typedef uint64_t M;

// 9*5^26 overflows, so m is only guaranteed to be correct modulo 2^(D-d).
#define D (64+25)

static char trail[D];
static int b = 0;

// Backtracking search.
//
// d: number on digits on the trail so far
// c: remaining cost (every non-9 digit costs 1)
// m: the trail taken as a base 10 number equals  m*2^d (mod 2^D)
// v: the value of the current digit is  v*2^d = 10^d (mod 2^D)
//
static void search(int d, int c, M m, M v)
{
    if (d >= b) {
        // improved solution --> print
        for (int i = d-1; i >= 0; i--)
            std::cout << static_cast<int>(trail[i]);
        std::cout << " (" << d << ")" << std::endl;
        b = d;
    }
    if (d == D)
        // reached capacity
        return;
    if (m % 2 == 1) {
        // appending 9 is possible at no cost
        trail[d] = 9;
        search(d+1, c, (m+9*v)/2, v*5);
    }
    if (c == 0)
        return;
    // try all other digits, skipping 0 if d == 0 (ensuring coprimality with 5)
    for (int i = d == 0; i < 9; i++) {
        if (m % 2 == i % 2) {
            // append digit i
            trail[d] = i;
            search(d+1, c-1, (m+static_cast<M>(i)*v)/2, v*5);
        }
    }
}

int main()
{
    search(0, 13, 0, 1);
}

/*
8:
9999999999999198999959999999999999968999999799296 (49)
user    0m0.175s
2^5436902276490237942293233461725232

9:
9999999999999999939996398999999999999999968999999799296 (55)
user    0m1.565s
2^42760780360969445702066972798891412732

10:
9999999999999999997999999999962999599999999999999937999999598592 (64)
user    0m13.975s
2^108395825863276441778086271515443868227350233

11:
999999999999999999999999978999999392494999999999999999968999999799296 (69)
user    2m5.592s
2^556032162023246903513788101669779375142641412732

12:
9999999999099699999999699999999999999999969999999899399999999999727990996992 (76)
9999999993993999999999999999997999999999962999599999999999999937999999598592 (76)
user    18m58.191s
2^15310575267962486902762478501786799525668075284758353
2^57537519301969242350473833466909971466615743227350233

13:
9999999969992999999999999999999999999978999999392494999999999999999968999999799296 (82)
9999999999999909997959999999999999998999999999981499799999999999999968999999799296 (82)
user    173m33.476s
2^1107641190153300089814326859082208802398672655171938287732
2^919477310773447891501179178631828196492424562520571100232
 */