0
$\begingroup$

I am interested in knowing if there is some closed form/formula for the following series: $S=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots$ (terms will reduce to zero after approximately $\log_p n$ terms). Here $n$ can be any natural number, but $p$ is a prime. This series appears in many places, and there is definitely some way to do this faster. The conventional method if implemented on the computer will take $O(\log n)$. But I am interested in knowing how to do it fast.Lets say we have to calculate this for a fixed n but varying primes, say some 100 primes so is there a way to get to know the answer for a prime if we know the answer for some previously calculated primes

$\endgroup$
  • $\begingroup$ Note that $S$ is the exponent of $p$ in the prime factorization of $n!$. This relation is known as Legendre's formula. Looks to me already like a pretty fast way to figure that out. $\endgroup$ – J.R. Jan 22 '14 at 15:48
  • $\begingroup$ Yes thats the reason i tagged it with factorial, S is also the number of trailing zeroes if n! is written in base p. $\endgroup$ – user103260 Jan 22 '14 at 15:50
1
$\begingroup$

If $n = \sum_{i=0}^k a_i p^i$ is the base-$p$ expansion of $n$ (with integers $0 \le a_i < p$), $\lfloor n/p^j \rfloor = \sum_{i=j}^k a_i p^{i-j}$, so $$S = \sum_{j=1}^k \sum_{i=j}^k a_i p^{i-j} = \sum_{i=1}^k \sum_{j=1}^i a_i p^{i-j} = \sum_{i=1}^k a_i \dfrac{p^{i}-1}{p-1} = (p-1)^{-1} \left( n - \sum_{i=0}^k a_i \right) $$ However, it will still be $\Omega(\log n)$ to compute all the base-$p$ digits of $n$.

$\endgroup$
  • $\begingroup$ Yes, thats what the Legendre's formula say too, however its efficiency is same. $\endgroup$ – user103260 Jan 22 '14 at 16:08

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.