# Summation of a curious series-repeated division by primes

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

• 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. – J.R. Jan 22 '14 at 15:48
• Yes thats the reason i tagged it with factorial, S is also the number of trailing zeroes if n! is written in base p. – user103260 Jan 22 '14 at 15:50

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