We are given a prime number $\leq 10^{18}$ and an integer N $(\leq N\leq 10^{18})$ how to find the number of integers lying in the range $1\leq n\leq N$ for which the order(n!) is a multiple of p? order=multiplicity of prime p in n!.
for example: for N=6 and p=2, we have integers 1,2,3,4,5,6 and their factorials as 1, 2, 6, 24, 120, 720 respectively
The multiplicities of 2 in these numbers are: 0, 1, 1, 3, 3, 4. Exactly two of these are divisible by 2 (0 and 4), so answer = 2.
I know the formula to find multiplicity of a prime in n!
$∑\lfloor(n/p^i)\rfloor$
but as N is very big so checking each no. for multiplicity and then for being divisible by p leads to timeout, please suggest me some logic/algorithm to solve this. thanks!
P.S. I want a programming version of the solution.
EDIT: the full algorithm:
The full algorithm can be summarized as follow:
First check if $N<p$. If it is, then the answer is $N$. Otherwise proceed to next step.
Calculate $M=\lfloor\frac{N}{p}\rfloor$. As explained in the explanation part, now we need to find the number of $k$ such that $kp$ is a valid $n$, and that $0\leq k\leq M$. This is equivalent to finding the number of $k$ with such bound such that the sum of digit in base $p$ of $k$ is $0$ in modulo $p$. We proceed by dividing into a number of cases:
Case: $0\leq\lfloor\frac{k}{p}\rfloor<\lfloor\frac{M-1}{p}\rfloor$. As explained below, the number of $k$ here is in fact $\lfloor\frac{M-1}{p}\rfloor$, as every possible value of $\lfloor\frac{k}{p}\rfloor$ corresponde to exactly an unique $k$. For each possible $k$, there are exactly $p$ possible value of $n$, with the exception of $k=0$ where, since $0$ is not counted, there are only $p-1$ possible $n$. Hence this give you $p\lfloor\frac{M-1}{p}\rfloor-1$.
Case: $\lfloor\frac{k}{p}\rfloor=\lfloor\frac{M-1}{p}\rfloor$ and $k\leq M-1$. There are either only 1 possible $k$ here, or none. To find out, convert $M-1$ to base $p$ representation: $m_{k}\ldots m_{1}$. Then if $(\sum\limits_{i=1}^{k}m_{i})\mod p\leq m_{1}$, then there is $1$ value of $k$; otherwise there are none. Each value of $k$ corresponde to $p$ value for $n$. So this case contribute either $p$ or $0$ to the total.
Case: $k=M$. Clearly there are at most $1$ possible value of $k$ here. We simply convert $M$ to base $p$, and sum up its digit modulo $p$: if that result in $0$, then $k=M$ is a valid value for $k$, otherwise it is not. If $k=M$ is a valid value, then the number of possible $n$ would almost be $p$ as usual, except that since we are too close to the bound, we might actually get less. The actual number is $n-Mp+1$.
That is all $3$ cases. Once we got everything, simply sum them up.
Example: let pick $N=46,p=3$. Then all the valid $n$ are $1,2,15,16,17,21,22,23,33,34,35,39,40,41,45,46$ so there are $16$ values. Let's see the algorithm:
-Clearly $46>3$.
-Calculate $M=\lfloor\frac{46}{3}\rfloor=15$.
-First case give $3\lfloor\frac{15-1}{3}\rfloor-1=11$.
-Convert $M-1=14$ to base $3$ give us $112$. We have $(1+1+2)\mod 3=1\leq 2$ so second case give us $3$.
-Convert $M=15$ to base $3$ give us $120$. We have $(1+2+0)\mod 3=0$ so third case give us $45-15\times 3+1=2$.
Total: $11+3+2=16$ as expected.
Explanation:
Let $k=\lfloor\log_{p}N\rfloor$. For each number $n$ associate with it a $k$-tuple $(a_{n,1},\ldots,a_{n,k})$ defined as $a_{n,i}=\lfloor\frac{N}{p^{i}}\rfloor$. Also associate with it a $k$-tuple $(b_{n,1},\ldots,b_{n,k})$ defined as $b_{n,i}=a_{n,i}\mod p$.
Notice that:
$a_{n,1}=(b_{n,k}\ldots b_{n,1})_{p}$ (where $(b_{n,k}\ldots b_{n,1})_{p}$ denote a number in base $p$ with where each $b_{n,i}$ is a digit in the usual order).
For each $a_{n,1}$ corresponde to exactly 1 possible tuple $(b_{n,1},\ldots,b_{n,k})$.
$a_{n,1}\leq\lfloor\frac{N}{p}\rfloor$.
$\sum\limits_{i=1}^{k}a_{n,i}\equiv\sum\limits_{i=1}^{k}b_{n,i}(\mod p)$
For each possible $a_{n,1}$, there are exactly $p$ possible value of $n$ corresponding to it, except for perhaps the largest possible value of $a_{n,1}$.
Hence an idea:
Calculate $M=\lfloor\frac{N}{p}\rfloor$.
Convert $M-1$ to base $p$.
Find all number of number in base $p$ that is less than or equal to $M-1$ and the digit sum is divisible by $p$ (this should not be too hard, as the bound are easily checked once you had base $p$ of $M-1$; I have not checked carefully but there might even be recursive algorithm to find the number of number, but even a naive brute force should still run in polynomial time; EDIT: see below). Multiply that by $p$ to get the number of possible $n$ corresponding to $a_{n,1}$ up to $M-1$.
Handle the exceptional case of $a_{n,1}=M$ separately.
EDIT:
To check the number of number, without a bad bound is very easy. Once you fixed every digit except the final digit, then the final digit is unique to satisfy the fact that the sum is divisible by $p$. Hence the number of possible $a_{n,1}$ such that $b_{n,k}<B$ for some bound $B$ is simply $B\times p^{k-2}$. Now $M$ might not be such a nice number, but I'm sure you can still adapt this technique.
EDIT:
If $M-1=(c_{k},\ldots,c_{1})_{p}$ (where $c_{k}$ could be $0$) then the number of possible number in base $p$ less than or equal to $M-1$ is $l+\sum\limits_{i=2}^{k}c_{i}p^{i-2}$, where $l=1$ if there exist a $b\leq c_{1}$ such that $b+\sum\limits_{i=2}^{k}c_{i}\equiv 0(\mod p)$, and $l=0$ otherwise.