Giving $n$ people a gift with rules below... (mark people $1, 2, \cdots, n$ starting from the frontest one.)
1. If $n$ is prime: give "$1$" a gift.
2. Else, for smallest prime $p$ s.t. $p | n$, give $m\cdot p$ a gift. ( $1\leq m \leq \frac n p, m \in \Bbb{N}.)$
3. A person (or people) given a gift gets out of the room.
After giving a gift, remark people $1, 2, \cdots$ i.s.w. (when a person is left, the gift-giving ends.)
Let's say we give a gift $f(n)$ times, and the remaining person's first mark was $g(n).$
Find the general form of $f(n)$ and $g(n)$.
This problem is from the Olympiad book.
\begin{align} \newcommand{\title}{\color{blue}} \newcommand{\theory}{\color{red}} \newcommand{\claim}{\color{lightgreen}} \newcommand{\proof}{\color{brown}} \newcommand{\lemma}{\color{violet}} & \text{let } n_0 = n. \\ \text{let} \; & \sigma_0=\left\{n_0, n_0, \frac {n_0} {p_0}, p_0\right\}. (p_i: \min(p) \text{ s.t. } p_i | n_i, p \geq 2.) \\ & \sigma_i=\left\{n_i, n_i', \frac {n_i}{p_i}, p_i\right\}.(n_i = |\text{people}|, n_i' = 1^{\text{st}} \text{ mark of } n_i) \\ & t_i: \sigma_{i-1} \to \sigma_i \\ \Rightarrow \; & \small t_i = \left\{n_{i-1}, n_{i-1}', \frac {n_{i-1}}{p_{i-1}}, p_{i-1}\right\} \to \left\{ n_{i-1}-\frac {n_{i-1}}{p_{i-1}}, n_i', \frac {(p_{i-1}-1)n_{i-1}}{p_i \cdot p_{i-1}}, p_i \right\} \normalsize \\ \ \\ &\title{1. \ \Bbb{Group \ Theory}} \\ &\theory{\text{let } G_j: (t_{k_j}, t_{k_j+1}, \cdots, t_{k_{j+1}-1}). ( k_j: j^{th} k \text{ s.t. } n_{k-1} | n.)} \\ \theory{\Rightarrow} \; & \theory{G_j: n_{k_j-1} \to \frac {n_{k_j-1}} {p_{k_j-1}}.} \\ &\claim{\text{Claim) } k_{j+1}-k_j=f(p_{k_j-1}).} \\ \proof{pf)} \; & \proof{\text{let } n = q_1^{e_1} q_2^{e_2}\cdots q_{\alpha}^{e_{\alpha}}. (q_1 < q_2 < \cdots < q_{\alpha}, q_{\boxed{}}: \text{ prime.})} \\ & \proof{j = e_1 + e_2 + \cdots + e_{\beta}+r. (0 \leq r < e_{\beta + 1}).} \\ \proof{\Rightarrow} \; & \proof{n_{k_j-1} = q_{\beta + 1}^{e_{\beta+1}-r} q_{\beta + 2}^{e_{\beta}+2} \cdots q_{\alpha}^{e_{\alpha}}.} \\ & \lemma{\text{Lemma) } p_{k_j-1} \geq p_{k_j}~P_{k_{j+1}-2}. (p_{k_j-1}=q_0.)} \\ & \lemma{\text{if } \exists s \text{ s.t. } p_{k_j-1} < p_{k_j+s}, 1 \leq s \leq k_{j+1}-k_{j}-2:} \\ & \lemma{p_{k_j+s} \in \{q_{\theta+1}, q_{\theta+2}, \cdots, q_{\alpha}\} \Rightarrow \text{ conflicts w/ definition of } G_s.} \\ & \proof{\Rightarrow \; k_{j+1}-k_j: \text{eliminating } q_{\beta+1}. \left(n_{k_j-1} \to \frac {n_{k_j-1}} {q_{\beta+1}}\right)} \\ & \proof{\Rightarrow \; k_{j+1}-k_j = f(q_{\beta + 1}).} \\ & \proof{p_{k_j-1} = q_{\beta + 1} \Rightarrow \; k_{j+1}-k_j=f(p_{k_j}-1). \blacksquare} \\ \theory{\therefore \; } & \theory{n = q_1^{e_1} q_2^{e_2} \cdots q_{\alpha}^{e_{\alpha}} (q_1 < q_2 < \cdots < q_{\alpha}, q_{\boxed{}}: \text{prime})} \\ \theory{\Rightarrow \; } & \theory{f(n)=\sum_{i=1}^{\alpha} e_i \cdot f(q_i).} \\ \ \\ & \title{2. \ g(n)\Bbb{'s \ Decreasing \ Form \ with \ Group \ Theory}} \\ \theory{\text{let}} \; & \theory{\lambda_0=\{1, 2, \cdots, n; n\}} \\ & \theory{\lambda_i = \{\alpha_1, \alpha_2, \cdots, \alpha_{n_i}; n_i\} ( \{ \alpha_k \}: i^{\text{st}} \text{ sequence of people.})} \\ \theory{\Rightarrow} \; & \theory{\alpha_{n_i} = n_i'}. \\ & \theory{s_i = \lambda_{i+1} \to \lambda_i \Rightarrow \text{eliminating } \alpha_{\frac{n_{j-1}}{p_{i-1}}} \text{ for } \forall k \text{ s.t. } 1 \leq k \leq p_{i-1}.} \\ & \theory{\text{let } w_j = \lambda_{k_j-1}, x_j = \alpha_{n_{k}-1}}. \\ \theory{\Rightarrow} \; &\theory{x_{e_1} \equiv \frac{p_1^{e_1}-1}{p_1-1} (g(p_1)+1)-1 (\text{ mod } p_1^{e_1})} \\ &\theory{\text{In $w_0$ ~ $w_{e_1}$, remaining number(s)} \equiv \dfrac{p_i^{e_i}-1}{p_i-1}(g_(p_i)+1)-1} \end{align}
I can't see any clue of the problem... Any hints?
