Correspondingly, here is the improved version of a1,

a1:=proc(b)
local A,i,j,k,arem,rem,dig;
arem:=proc() rem:=irem(b*j,i); dig:=convert(j,base,b); 
     seq(`if`(member(k*i-rem,dig),NULL,b*j+k*i-rem),
          k = 1 .. iquo(b-1+rem,i)) end;
A[1] := [$1..b-1];
for i from 2 do
     A[i] := [seq](arem(), j = A[i-1]);
     if A[i] = [] then break fi od;
i-1 = A[i-1]
end:

For decimal system, it works very fast,

tt:=time(): a1(10); time()-tt;

                           9 = [381654729]

                                0.016

In addition to the values in the worksheet, I calculated

a1(21);
                   18 = [509504810627259318940020]

a1(22);

                   19 = [5213608783930183587520297]

a1(23);

  21 = [3017921136920002608782486643, 3202513921881602294966195322,

        10912277070078955588719411381, 11506928512609494037599575154,

        19136629049078922486640055262, 19563154864313291881366262910,

        20927442077211608842020972981, 22095893110934309880723905997,

        24479055281091281744429147151, 26034588683899462487295851544,

        27944901128718982841182304058, 28236074834439966722409861288,

        30327538677373615144106864301, 30327538677373615144106864322,

        33286709815522787435710859625, 33637644479370238638607793874,

        39311846134353288073052119134]

Now, compiled procedures should run much faster. Here is the first try,

a2 := proc(b::integer[4], A::Array(datatype = integer[4]))::
integer[4];
local i::integer[4], j::integer[4], K::integer[4],
s::integer[4], r::integer[4];
    A[1] := 1;
    i := 2;
    K := 1;
    s := 1;
    while 0 < i do
        if s = 1 then
            r := irem(A[1], i);
            for j from 2 to i - 1 do r := irem(r*b + A[j], i)
            end do;
            r := irem(r*b, i);
            if r = 0 then
                A[i] := 0; K := max(K, i); i := i + 1
            elif b - 1 + r < i then i := i - 1; s := 0
            else A[i] := i - r; K := max(K, i); i := i + 1
            end if
        else
            if A[i] + i < b then
                A[i] := A[i] + i; i := i + 1; s := 1
            else i := i - 1
            end if
        end if
    end do;
    K
end proc:

a3:=Compiler:-Compile(a2):
A:=Array(1..100,datatype=integer[4]):

While a2 is slower than a, the compiled procedure a3 is much faster. For example,

tt:=time(): a3(10,A); time()-tt;
                                  25
                                0.016

It should be called as a3(b,A) where b is the base and A is a predefined Array with datatype=integer[4] and length greater than the expected maximal number of digits. It returns the maximal number of digits. In particular, for b from 17 to 21 the maximal number of digits has appeared to be 45, 48, 48, 52, 53.