Knuth's conjecture writing integers "using only one 4"

[Maximilian Hasler]

Dear Hugo,
I recently stumbled across the paper

Donald E. Knuth, "Representing numbers using only one 4",
Mathematics Magazine, Vol. 37, No. 5 (Nov., 1964), pp. 308-310

I intended to submit the sequences

%N number of operations "k -> floor(sqrt(k)) or "k -> k!" needed to
obtain n, starting with 4.
%S 2, 1, 10?, 0, 7, 11, 24??,

%N number of operations "k -> floor(sqrt(k)) or "k -> k!" needed to
obtain n, starting with 3.
%S 1, 2, 0, 20?, 4, 1, 14, 17, 31??, 6

which do not yet seem to exist in OEIS.

I saw on some (quite old) forum that you also looked into this
question, but I'm not sure if the goal there was to obtain the
shortest solution, or just any solution for as many n as possible ;
also I can't execute the perl code found there (something is ill
installed on my machine).
So I wrote my own "stupid" PARI code (not even using logs):
knuth(n,i=3,LIM=5000)={ local( found=[i;i], fnd=Set(i), need =
Set(vector(n,j,j)), t, j=0);
  while( j++,
     if( !setsearch( fnd, t=sqrtint( found[1,j] )),
        found = concat( found, [ t ; Str("s",found[2,j]) ]);
        fnd = setunion(fnd,Set( t ));
        t<=n & !setminus( need, fnd ) & break;
     );
     if( found[1,j]<LIM & !setsearch( fnd, t=found[1,j]! ),
        found = concat( found, [ t ; Str("f",found[2,j]) ]);
        fnd = setunion(fnd,Set( t ));
        t<=n & !setminus( need, fnd ) & break;
     );
  ); vector(#fnd=vecextract(vecsort(Vec(found),1),1<<n-1)),i,#fnd[i][2]-1)
}

I get e.g.
(21:47) gp > knuth(15,3,5000)
[1, "s3"]~65524
[6, "f3"]~65460
[2, "sf3"]~65456
[5, "ssff3"]~65424
[10, "sfssff3"]~64400
[7, "sssssssssssfff3"]~64272
[8, "ssfsssssssssssfff3"]~64016
[4, "ssssssfsssssssffssff3"]~64000
[14, "ssfssfsssssssssssfff3"]~47616
[11, "sssssfssssssssssssfsssfsff3"]~45568
[9, "ssssssssssfsssssssssssfsfsfssff3"]~45056
[15, "ssssssssssfsssssfsssssfssssfsff3"]~12288
[13, "sssssssfsssfsssssssssfssssfsssssssffssff3"]~4096
[12, "sssssfsssfssssssssssfsssssfsssssfssssfsff3"]~0
%434 = [1, 2, 0, 20, 4, 1, 14, 17, 31, 6, 26, 41, 40, 20, 31]

I am not sure if these terms are correct, the values >20 are likely
not to be minimal (in view of the limit of 5000 ! I impose
arbitrarily), but I'd like to know if at least the value for n=4 is
OK. (The "31" for n=9 remains "33" at least up to 1200 !)
It would be best to write an intelligent program, which for a given
number, looks if this can be obtained as factorial,
or else as sqrtint() of which numbers, and then tries to get a number
in that range (recursively ? with limited search depth that would be
gradually increased ?).
And/or use logs...

Maximilian