20
\$\begingroup\$

Related: Zeroes at the end of a factorial

Today, we are going to calculate how many zeroes are there at the end of \$n!\$ (the factorial of \$n\$) in base \$m\$.

Or in other words: For given integers \$n\$, and, \$m\$. Calculate the integer \$p\$ which is the highest power of \$m\$ dividing \$n!\$: \$p \in \mathbb{N}_0\$ which holds \$ \left( m^p \mid n! \right) \land \left( m^{p+1} \nmid n! \right) \$. Here, \$n!\$ is the factorial of \$n\$ which equals to the product of all positive integers less than or equal to \$n\$. The value of \$0!\$ is \$1\$.

Input / Output

  • Two integers \$n\$, \$m\$.
  • One integer: How many zeroes at end of \$n!\$ in base \$m\$.

Rules

  • As , the shortest codes in bytes win.
  • Your program is required to support \$0\le n\le 1{,}000{,}000\$; \$2\le m\le 1{,}000\$ at least. The program should be able to output correct results for any inputs in above range with reasonable resource (typically, <1 minutes on a normal laptop).
  • As this question is only talking about integers. No floating point errors may allowed in your output. You may, however, output 3.0 when 3 is required. But 2.9999999999999996 is certainly not allowed.

Testcases

      n,    m -> output
      0,    2 -> 0
      1,    2 -> 0
      2,    2 -> 1
      3,    2 -> 1
      4,    2 -> 3
      9,    6 -> 4
     10,  100 -> 1
     80,  100 -> 9
      4,    8 -> 1
     15,   12 -> 5
     16,   12 -> 6
     39,   45 -> 8
    100,    2 -> 97
    100,    3 -> 48
    100,    4 -> 48
    100,    5 -> 24
    100,    6 -> 48
    100,    7 -> 16
    100,    8 -> 32
    100,    9 -> 24
    100,   10 -> 24
    100,   13 -> 7
    100,   36 -> 24
    100,   42 -> 16
    100,   97 -> 1
    100,  100 -> 12
1000000,    2 -> 999993
1000000,    3 -> 499993
1000000,    4 -> 499996
1000000,    6 -> 499993
1000000,    7 -> 166664
1000000,    8 -> 333331
1000000,    9 -> 249996
1000000,  999 -> 27776
1000000, 1000 -> 83332

Above \$n\$ is written in base 10. You are allowed to receive \$n\$ as an array of integers in base \$m\$ if you want.

Related OEIS

It is interesting that this question involve at least 14 sequences on OEIS. Maybe you can find out some helpful formula to solve this problem on it.

OEIS includes sequences for every \$2 \le m \le 16\$:

Also, by treating above sequences as a matrix, there are other related sequences:

  • A090622: Square array read by antidiagonals of highest power of k dividing n! (with n,k>1).
  • A098094: T(n,k) = greatest e such that k^e divides n!, 2<=k<=n (triangle read by rows).
  • A011776: a(1) = 1; for n > 1, a(n) is defined by the property that n^a(n) divides n! but n^(a(n)+1) does not.
Improve this question
\$\endgroup\$
2
  • 4
    \$\begingroup\$ I see on the internet that \$1000000!\$ is a more than 5Mo text file :D count me out, anyway I do enough maths at work already ;) interesting challenge though, I'll be lurking the answers \$\endgroup\$
    – Kaddath
    Mar 18, 2021 at 10:07
  • \$\begingroup\$ @Kaddath A textual representation of \$2^{2^{4\cdot 10}}-1\$ in base 2 requires a tebibyte. \$\endgroup\$
    – Jonathan Frech
    Mar 22, 2021 at 5:53

9 Answers 9

Reset to default
10
\$\begingroup\$

Wolfram Language (Mathematica), 22 bytes

#!~IntegerExponent~#2&

Try it online!

Improve this answer
\$\endgroup\$
4
  • 7
    \$\begingroup\$ hello downvoters...!!! Can you please explain what I'm missing here? \$\endgroup\$
    – ZaMoC
    Mar 18, 2021 at 9:49
  • 2
    \$\begingroup\$ It is a magic built-in. \$\endgroup\$
    – tsh
    Mar 18, 2021 at 10:19
  • 1
    \$\begingroup\$ This is a boring builtin answer. It takes 10 seconds to look up how to do this with a builtin in Mathematica and another 10 seconds to write the optimal golf. Maybe worth answering, but categorically not worth upvoting. \$\endgroup\$
    – pxeger
    Mar 18, 2021 at 19:30
  • \$\begingroup\$ @pxeger thanks for sharing your thoughts \$\endgroup\$
    – ZaMoC
    Mar 18, 2021 at 19:57
5
\$\begingroup\$

Jelly, 12 bytes

Æfµ⁹ọ€S:ċⱮ`Ṃ

A dyadic Link accepting the base, \$m\$, on the left and the factorial-input, \$n\$, on the right that yields the number of trailing zeros of \$n!_{m}\$ as an integer.

Try it online!

How?

Æfµ⁹ọ€S:ċⱮ`Ṃ - Link: integer, m; integer, n   e.g. 72 100
Æf           - prime factorisation (m)             [ 2, 2, 2, 3, 3]
  µ          - start a new monadic chain - f(x=that)
   ⁹ €       - for each i in [1..n]:
    ọ        -   (i) order (vectorised across x)
                                                   [[0,0,0,0,0],[1,1,1,0,0],[0,0,0,1,1],[2,2,2,0,0],...]
      S      - sum (vectorises)                    [97,97,97,48,48]
          `  - use x as both arguments of:
         Ɱ   -   map across (x) with:
        ċ    -     count occurrences               [ 3, 3, 3, 2, 2]
       :     - integer divide                      [32,32,32,24,24]
           Ṃ - minimum                             24
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Python 2, 133 130 bytes

Saved 3 bytes thanks to kops!

n,m=input()
f=()
i=2
k=lambda n,p:n and n/p+k(n/p,p)
exec"while m%i<1:m/=i;f+=i,\ni+=1\n"*m
print min(k(n,p)/f.count(p)for p in f)

Try it online!

Creates a list of all the prime factors of m. The program then computes the highest power of each prime factor that divides n! using the lambda function k. This number is divided by the number of times the prime factor is found in f. Finally, the program prints out the min of these values.

A math.stackexchange.com question with answers explaining how this works:

https://math.stackexchange.com/questions/391067/power-of-a-number-in-a-factorial

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 130 bytes; you don't need the [] in the last line because min can take a generator expression instead of a list. \$\endgroup\$
    – kops
    Mar 19, 2021 at 21:29
3
\$\begingroup\$

Charcoal, 49 bytes

ＮθＮηＷ¬⁼ηΠυ⊞υ§Φ…·²η¬﹪÷η∨Πυ¹κ⁰Ｉ⌊Ｅυ÷↨Ｅ↨θι↨…↨θιμι¹№υι

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input n and m.

Ｗ¬⁼ηΠυ⊞υ§Φ…·²η¬﹪÷η∨Πυ¹κ⁰

Find m's prime factors.

  Ｅυ                    Map over prime factors
       ↨θι              Convert `n` to base `p`
      Ｅ    …↨θιμ        All prefixes
          ↨     ι       Converted from base `p`
     ↨           ¹      Take the sum
    ÷                   Integer divided by
                  №υι   Frequency of prime factor
 ⌊                      Take the minimum
Ｉ                       Cast to string
                        Implicitly print
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 13 bytes

ÆFZọ€Ḣ}S:ʋ@ẎṂ

Try it online!

After the 4, 48 fix it's too slow to run all of the test cases in one go, but I think it can still handle them all individually.

I'm not sure why ɓ (or ð for that matter) refuses to work here.

Takes \$m\$ on the left and \$n\$ on the right.

ÆF               Factor m into [prime, exponent] pairs.
  Z              Zip.
         ʋ@      With [[primes], [exponents]] as the right argument:
    €            For each integer in [1 .. n],
   ọ             how many times is it divisible by
     Ḣ}          each prime? (the list of which is popped from the pair)
       S         Sum the divisibilities,
        :        and floor-divide the sums by the exponents.
           Ẏ     Dump inner lists (not entirely sure why they're singletons),
            Ṃ    and return the minimum.
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Fails at (4,48). (Expected answer is 0 but yours gives 1) \$\endgroup\$
    – Bubbler
    Mar 18, 2021 at 11:43
  • 1
    \$\begingroup\$ FYI you need Ẏ because the Ḣ pops the head off of [[p1,...],[e1,...]] leaving [[e1,...]], which : then vectorises across which means you end up with [[s1/e1,...]] from which you require the minimum s/e element. \$\endgroup\$
    – Jonathan Allan
    Mar 18, 2021 at 18:29
2
\$\begingroup\$

C (gcc), 242 237 bytes

f(n,b){int*p=malloc(12*b),d=2,k,l;for(;b/d;++d){for(k=b;k%d<1;k/=d)p[d]++;for(k=2;p[d]&&k<d;p[d]*=d%k++>0);}for(k=0;n/++k;)for(d=2;k/d&&b/d;++d)for(l=k;p[d]&&l%d<1;l/=d)++p[b-~d];for(n=d=0;b/++d;k&&n<1|k/p[d]<n?n=k/p[d]:0)k=p[b-~d];d=n;}

Try it online!

Annotated version

f(n,b){
 int*p=malloc(12*b) /* Since `b>=2` holds,
                           `12*b>=8*b+8==2*4*(b+1)==2*(b+1)*sizeof(int)`.
                       The pointer `p` represents two sparse arrays of
                       length `b+1` only indexed by primes, the first
                       storing the base's prime factorization.
                       Its latter half's `b+1` elements stores how many of
                       `k`'s (where `1<=k<=n`) prime factors with
                       multiplicities. */
 ,d=2,k,l;
 for(;b/d;++d{      // first half of `p`
  for(k=b;k%d<1;
  k/=d)
   p[d]++;
  for(k=2;p[d]
  &&k<d;
  p[d]*=d%k++>0)
   ;
 }
 for(k=0;n/++k;)    // all factors of $n!$
  for(d=2;k/d
  &&b/d;++d)        // all divisors $d | k$
   for(l=k;p[d]     // which are prime factors of $b$
   &&l%d<1;l/=d)
    ++p[b-~d];
   for(n=d=0;b/++d; /* calculate the minimum of $n!$'s factors
                       weighted according to $b$'s factor's
                       multiplicity */
   k&&n<1|k/p[d]<n
   ?n=k/p[d]:0)
    k=p[b-~d];
 d=n;}              // return

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Perl 5 -MList::Util, 131 bytes

131 bytes without newlines, indentation and comments.

sub f{
  %d=();                                     #init counting hash to empty
  sub e{$M%$_ or$d{$_}++,$M/=$_,redo for@_}  #sub that counts given factors of $M
  e 2..($M=pop);                             #count factors of M
  (%c,%d)=%d;                                #store and reset counts
  for$M(2..pop){e keys%c}                    #count active factors of N! (N=pop)
  ~~min map$d{$_}/$c{$_},keys%d              #how many of last counts in first
}

Try it online!

print f(100, 13);        # prints 7
print f(1000000, 999);   # prints 27776
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

MATLAB, 107 bytes

function F(n,m)
for i=1:max(n,m),f{i}=factor(i);end
c=f{m};fix(min(sum([f{1:n}]'==c)./sum(c==c')))
end

First get all factors from 1 to the maximum of n or m. This guarantees that all factors of 1-n are captured as well as the factors of m. Then, divide the sum of the appearance of each factor by the duplicity of that factor to determine the minimum amount of pairs of the factors of m appear in n!, which is the maximum power that m can be raised to to divide n!.

For example: F(80,100)

  1. f -> all factors from 1-100 in a 1x100 cell array, where f{i}=factor(i)
  2. c -> [2 2 5 5]
  3. sum([f{1:n}]'==c) -> [78 78 19 19], there are 78 2s in all of f and 19 5s in all of f.
  4. sum(c==c') -> [2 2 2 2], there are two of each factor
  5. (3)/(4) -> [39 39 9.5 9.5]. element-wise division shows that at a minimum, 9 whole sets of factors of m are contained in n!'s factors, therefore n! is divisible by at most m^9
  6. fix(min(3.3)) -> 9, which is the correct answer
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python 3 + SymPy, 118 bytes

lambda n,m:min(g(n,f)//p for f,p in factorint(m).items())
g=lambda n,p:n and n//p+g(n//p,p)
from sympy.ntheory import*

Try it online!

This is my reference implementation which generate all testcases:

from sympy.ntheory import factorint

def f(n, m):
    factor_count = lambda n, p: n // p + factor_count(n // p, p) if n else 0
    return min(factor_count(n, factor) // power for factor, power in factorint(m).items())
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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