I have a few things that may of be of use. First off, here is a base 10 spigot algorithm that is in O(n^2) time.
Where v(p,k) is the multiplicity of the prime p in k (the exponent of p in the multiplicative decomposition of k in prime powers, another name is "p-adic valuation").
Example : v(3,18)=2 since 18=2⋅32
I tried and failed to implement this awhile back, but now that there is modulo and floor, it will be much easier.
Another base 10 algorithm is described here:
The hardest part will be summing binomial coefficients, but it also should be pretty simple to implement.
But I really haven't made much progress. Go ahead and give it a shot, and show me what you are doing along the way