Find a factorial with n trailing zeros, quickly

Question

Problem

A fact you may have noticed about factorials is that as \$n\$ gets larger \$n!\$ will have an increasing number of \$0\$s at the end of it's base \$10\$ representation. In fact this is true for any base.

In this challenge you will be given a base \$b > 1\$ and an integer \$n > 0\$ and you will determine the smallest \$x\$ such that \$x!\$ has at least \$n\$ trailing \$0\$s in its base \$b\$ representation.

Of course you can easily do this by just checking larger and larger factorials. But this is super slow. The actual challenge is to do this quickly. So in order to be a valid answer you must have a worst case asymptotic complexity of \$O(\log(n)^3)\$ where \$n\$ is the number of trailing \$0\$s and \$b\$ is fixed. You should assume that basic arithmetic operations (addition, subtraction, multiplication, integer division, and modulo) are linear to the number of bits in the input.

This is code-golf so the goal is to minimize your source code as measured in bytes.

Examples

For a small example if \$b=2\$ and \$n=4\$ then the answer is \$6\$ since \$5!=120\$ which is not divisible by \$2^4=16\$, but \$6!=720\$ which is divisible by \$16\$.

For a bigger example if \$b=10\$ and \$n=1000\$ then the answer is \$4005\$, since \$4004!\$ has only \$999\$ trailing zeros in base 10, and multiplying by \$4005\$ is obviously going to introduce another \$0\$.

Answer 1

Python, 209 bytes

lambda b,n:max(h(g(b).count(s)*n,s,1)for s in g(b))
def h(n,s,*S,o=0):
 while S[-1]<n:S+=S[-1]*s+1,
 while S:*S,t=S;o+=n//t;o*=s;n%=t
 return o
g=lambda b,p=2,m=0:(b-p)*[0]and g(b,p+1)if b%p else[p]+g(b//p,p)

Attempt This Online!

Not very golfed yet. Hope to find time later.

g is based on one of @Lynn's neat tips and does prime factor decomposition of b. As `b´ is fixed it is technically O(1).

The main function f goes through all prime factors and lets h compute the smallest n such that that prime factor occurs sufficiently often in the factorial. It then simply takes the max. As b is fixed the complexity is that of h.

h works on p the current prime factor and n where n is the requested number of trailing zeros times the multiplicity of p in b. It is easy to convince oneself that p! has 1 p,p^2! has p+1 ps p^3! has p(p+1)+1 etc. So what we want to do is something like writing n in the mixed base (1,p+1,p(p+1)+1,...) and then reinterpret the digits in base p. Which is what h does, though I wish I had a few more test cases.

Complexity:

Disclaimer, I always get those wrong. But if I'm not mistaken this would be O(log(n)^2) (O(log(n)) steps in the while loop and O(log(n)) digits in the arithmetic operations.

Answer 2

JavaScript (Node.js), 136 128 117 bytes

b=>n=>eval("h=x=>x&&x+h(x/p);p=2n;for(e=m=0n;b>1;)if(b%p)e=p-p++;else{b/=p;for(x=n*~-p*++e;h(x++/p)<n*e;)m=m<x?x:m}")

Try it online!

Shortened by @Cool guy.

I'm not entirely clear about Wheat Wizard's time bound, but I think this is within it. To explain the method: the number of zeroes at the end of \$n!\$ in base b is equal to the minimum number of zeroes at the end of \$n!\$ in any prime power base dividing b, so I look at all prime powers dividing b, find the minimum possible x for all of them and take the maximum. Counting up the factors of p in the factors of \$x!\$ shows you that the number of zeroes at the end of \$x!\$ in a prime base p is $$\phi(x):=\sum_{j\ge 1} \lfloor{\frac{x}{p^j}}\rfloor \le \frac{x}{p-1},$$ meaning that the smallest possible x in a prime power base \$p^e\$ definitely can't be any smaller than \$n e (p-1) \$. So, for each prime power factor \$p^e\$ of b, I start with \$n e (p-1)\$ and count up by ones until I find a working x. Since the difference between \$\phi(x)\$ and \$x/(p-1)\$ is logarithmic in x, and \$\phi(x)\$ increases by at least one when x is increased by p, only a logarithmic number of iterations are necessary. (Each iteration means recomputing \$\phi(x)\$, which uses \$O(\log{x})\$ additions and divisions by p.)

Answer 3

JavaScript (Node.js), 118 bytes

n=>b=>(g=(p,k)=>b-!k?b%p?g(p+1,0,r=k&&(h=m=>H=N>=m&&(h(m*p+1)+(N-(N%=m))/m)*p)(1,N=n*k)>r?H:r):g(p,k+1,b/=p):r)(2,r=0)

Try it online!

Maybe \$O(\log(n))\$?

1. For every \$p^k\$ where \$p\$ is prime, \$k\$ is an integer, \$p^k\$ is a factor of \$b\$. Calculate \$F_p(k\cdot n)\$ using following steps; the answer is \$\max\$ of all results.
2. Convert \$k\cdot n\$ to a strange base \$\overline{d_md_{m-1}\dots d_1}\$ where $$ k\cdot n = \sum_{i=1}^m\left(d_i \cdot \frac{p^i-1}{p-1} \right) $$ $$ 0\le d_i \le p $$ $$ d_1=0 $$
3. Read the number \$\overline{d_md_{m-1}\dots d_1}\$ as base \$p\$, while digits \$p\$ is treated as \$10_{(p)}\$.

I know the code should be able to golf more. But the formula should just like this.