TITLE: Does this function have closed form?
QUESTION [1 upvotes]: Define $$f(p,n)=\sum_1^n s_i$$ where $s_i$ is defined as the maximal integer value such that $i= p^{s_i}r_i$ for integer $r_i$.
For example, we'd have $$f(2,15)=\sum_1^{15} s_i=1+2+1+3+1+2+1=11.$$
Does this function have any closed form? Or any faster algorithm than the one like the example? or any asymptotic formula？

REPLY [2 votes]: We can solve this by considering the sum "sideways" in a sense. How many elements of the sum are at least one $1$? Well, every integer $1\leq i \leq n$ which $p$ divides is greater $1$ - so there are $\left\lfloor \frac{n}p\right\rfloor$ such elements, each contributing $1$ to the sum. How many elements of the sum are greater than $2$? Those that $p^2$ divides - so there are $\left\lfloor \frac{n}{p^2}\right\rfloor$ of those - each of which contributes an additional $1$ to the sum (since we already counted them once). Terms that $p^3$ divides contribute an extra $1$. We can continue likewise to determine that the sum equals
$$f(p,n)=\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor$$
which, of course, only needs to be computed up to the first $p^k>n$.
We could also express the same idea as a recurrence
$$f(p,n)=\left\lfloor\frac{n}p\right\rfloor+f\left(p,\left\lfloor \frac{n}p\right\rfloor \right)$$
(A nice aside here is that computing sums this way is analogous to using a Lebesgue integral - where we measure the sets of "how much is $f(i)>n$?")
{"set_name": "stack_exchange", "score": 1, "question_id": 1093728}