18
\$\begingroup\$

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 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\$.

\$\endgroup\$
4
  • 4
    \$\begingroup\$ I have an algorithm which solves this in \$O(\log(\log (n))\log(n))\$. Can you do better? \$\endgroup\$
    – Wheat Wizard
    Feb 9 at 12:12
  • \$\begingroup\$ More testcases please? \$\endgroup\$
    – tsh
    Feb 10 at 5:33
  • \$\begingroup\$ This is in some sense an inverse of Zeroes at the end of a factorial - which you might enjoy if you like this. \$\endgroup\$ Feb 10 at 13:11
  • \$\begingroup\$ Actually, the inverse is more like Zeroes at end of n! in base m (that one isn't tagged factorial, which is why I couldn't initially find it). \$\endgroup\$ Feb 10 at 13:24

3 Answers 3

6
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ You don't have to run it on all of the prime factors. Just the largest one, it will always have the maximum result for h. \$\endgroup\$
    – Wheat Wizard
    Feb 9 at 15:48
  • 1
    \$\begingroup\$ ,@WheatWizard is that true if a smaller factor has sufficiently high multiplicity? My hunch is that each prime factor has asmptotically fixed density max n p^n|N! \propto N. So if the smaller factor is x times denser then we pick as a base Pp^z with z>x and P,p are the large and small prime factors, no? \$\endgroup\$
    – loopy walt
    Feb 9 at 16:00
  • 1
    \$\begingroup\$ Sorry by biggest I mean the prime factor times it's multiplicity. \$\endgroup\$
    – Wheat Wizard
    Feb 9 at 16:01
  • 2
    \$\begingroup\$ @WheatWizard From a golfing point of view just taking the max after applying h is probably cheaper than predicting the max. I guess there will be hairy edge cases like ties between primes times multiplicity. It is also free complexity-wise as b is fixed. \$\endgroup\$
    – loopy walt
    Feb 9 at 16:10
  • 2
    \$\begingroup\$ As far as I can see \$O(\log(n)^2)\$ is correct. \$\endgroup\$
    – Wheat Wizard
    Feb 9 at 16:17
6
\$\begingroup\$

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.)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ If I understand this correctly it should be \$O(\log(n)^3)\$ and \$\omega(\log(n)^2)\$. At least from the description. I cannot read the JS. This would make it definitely within the bounds of the challenge. \$\endgroup\$
    – Wheat Wizard
    Feb 9 at 21:33
  • \$\begingroup\$ 120 \$\endgroup\$
    – Cool guy
    Feb 11 at 5:43
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ The formula 2., 3. (i.e., h) is good, but applying it to the largest factor \$p^k\$ of \$b\$ will not always work. Try to find the smallest \$n\$ such that \$n!\$ ends with 10 zeros in base 544. \$\endgroup\$ Feb 10 at 7:32
  • \$\begingroup\$ @Polichinelle should be fixed. Is this currently correct? \$\endgroup\$
    – tsh
    Feb 10 at 9:43
  • \$\begingroup\$ Yes, I think so. \$\endgroup\$ Feb 10 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.