2

Let us consider a function $ f:\mathbb{N}_0 \to \mathbb{N}_0 $ following the relations:

  1. $ f(0)=0$

  2. $f(n) = n+f\left(\left\lfloor \frac{n}{p} \right\rfloor\right)$ when the $n$ is not divisible by $p$

  3. $ f(np) = f(n) $

Here $p>1$ is a positive integer .$ \mathbb{N}_0 $ is the set of all non-negative integers and let $ a_k $ be the maximum value of $ f(n) $ for $ 0<n \leq p^k $ .

How can I find the value of $ a_k ?$

Felix Marin
  • 89,464
Way to infinity
  • 1,884

1 Answers1

1

Proof by induction on $n$: $$\begin{eqnarray} f(p^{n+1}-1)=\\ f((p-1)(1+p+p^2+ \cdots p^{n-1}+p^n))=\\ f((p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1) p^{n-1} + (p-1)p^n)=\\ ((p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1) p^{n-1} + (p-1)p^n) + f( \lfloor \frac{p-1}{p} + (p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1)p^{n-1} \rfloor)=\\ p^{n+1}-1 + f( (p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1)p^{n-1})=\\ p^{n+1} + p^{n} + \cdots + 1 -(n+2)=\\ \frac{p^{n+2}-1}{p-1} -n-2 \end{eqnarray}$$

Proof by induction on $n$:

$$0 \le a_i \lt p , \forall i: \;0 \le i \le n$$ $$\begin{eqnarray} f(a_0+a_1p+a_2p^2+ \cdots a_{n-1} p^{n-1} + a_n p^n) = \\ (0 \; \text{if} \; a_0=0, \; \text{otherwise} \; a_0+a_1 p+a_2p^2+ \cdots a_{n-1} p^{n-1} + a_n p^n) + \\f( \lfloor \frac{a_0}{p}+a_1+a_2p+ \cdots a_{n-1} p^{n-2} + a_n p^{n-1} \rfloor) \\ \le ((p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1) p^{n-1} + (p-1)p^n) \\ +f( \lfloor \frac{p-1}{p} + (p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1)p^{n-1} \rfloor) =\\ f((p-1)+(p-1)p+(p-1)p^2+ \cdots (p-1) p^{n-1} + (p-1)p^n)= \\ f((p-1)(1+p+p^2+ \cdots p^{n-1}+p^n))=\\ f(p^{n+1}-1) \end{eqnarray}$$ So the maximum on $\{0,\cdots , p^n\}$ is $f(p^n-1)= \frac{p^{n+1}-1}{p-1} -n-1$

miracle173
  • 11,049