Consider fractions $a/b$ as primitive lattice points $(a,b)$. Let $T_{k}$ be the triangle bounded by lines $y=0$, $y=x$, $x=k$. An optimal set of points for this problem must contain all of the primitive lattice points inside $T_{k}$ for some value of $k$, otherwise the sum of denominators can be reduced by moving a point outside $T_{k}$ into $T_{k}$. There can be very few additional lattice points outside this $T_{k}$, because among any two neighboring lattice points, at least one is primitive (either $m,n$ are relatively prime or $(m+1),n$ are relatively prime). So if $N_{k}$ is the number of primitive lattice points in $T_{k}$, we will have $N_{k}\leq n \leq N_{k}+k+1$. Here $k = O(\sqrt{n})$. To get the correct order of magnitude for the sum of denominators, use the fact that the density of primitive points is $6/{\pi^{2}}$.

I am able to get \[ S \geq \[ 2\phi(2) + 3\phi(3) + \cdots + (k - 1)\phi(k - 1)\ + k\] where k satisfies \[ \phi(2) + \cdots + \phi(k) \geq n > \phi(2) + \cdots + \phi(k - 1)\] . Can anyone give an elementary proof from here on?

Lemma 1: For all $n\ge1$, $\left| \sum_{k=1}^{n}\frac{\mu(k)}{k^2} - \frac{6}{\pi^2} \right| \le \frac{1}{n}$. Proof: It's well-known that $1 = \sum_{k\ge1}\frac{1}{k^2}\sum_{k\ge1}\frac{\mu(k)}{k^2}$, so by the triangle inequality, \[ \left| \sum_{k=1}^{n}\frac{\mu(k)}{k^2} - \frac{6}{\pi^2} \right| = \left| \sum_{k\ge n+1}\frac{\mu(k)}{k^2} \right| \le \sum_{k\ge n+1}\frac{1}{k^2} < \sum_{k\ge n+1}\frac{1}{k(k-1)} = \frac{1}{n}.\blacksquare \] Lemma 2: For all $n\ge1$, $\left| \sum_{k=1}^{n}\phi(k) - \frac{3n^2}{\pi^2} \right| \le \frac{n\ln{n}}{2}+n$. Proof: By Möbius inversion, \[ \sum_{k=1}^{n}\phi(k) = \sum_{k=1}^{n}\sum_{d|k}\mu(d)\cdot\frac{k}{d} = \sum_{d=1}^{n}\mu(d)\sum_{k=1}^{\lfloor{n/d}\rfloor}k = \frac{1}{2}\sum_{d=1}^{n}\mu(d)\left\lfloor{\frac{n}{d}}\right\rfloor \left(\left\lfloor{\frac{n}{d}}\right\rfloor+1\right). \]But $x-1<\lfloor{x}\rfloor\le x$, so $\left|\lfloor{x}\rfloor\lfloor{x+1}\rfloor - x^2\right|\le x$ and by the triangle inequality, \[ \left| \sum_{k=1}^{n}\phi(k) - \frac{n^2}{2}\sum_{d=1}^{n}\frac{\mu(d)}{d^2} \right| \le \frac{n}{2}\sum_{d=1}^{n}\frac{1}{d} \le \frac{n}{2}\left(1+\int_{1}^{n}\frac{1}{x}\;dx\right) = \frac{n\ln{n}+n}{2}. \]Using lemma 1 (times $n^2/2$) and the triangle inequality yields \[ \left| \sum_{k=1}^{n}\phi(k) - \frac{3n^2}{\pi^2} \right| \le \frac{n\ln{n}+n}{2}+\frac{n}{2}, \]as desired.$\blacksquare$ Lemma 3: For all $x\ge e$ we have $\frac{\sqrt{\frac{3x^2}{\pi^2}+\frac{x\ln{x}}{2}+x-1}}{2} \le x$. Proof: Suppose otherwise. Expanding and using the fact that $\ln{x}/x$ and $2(x-1)/x^2$ are decreasing for $x\ge e$, we obtain \begin{align*} 4x^2 &< \frac{3x^2}{\pi^2} + \frac{x\ln{x}}{2}+x-1 \\ \implies 7 < 8-\frac{6}{\pi^2} &< \frac{\ln{x}}{x}+\frac{2(x-1)}{x^2} \le \frac{1}{e}+\frac{2(e-1)}{e^2} = \frac{3e-2}{e^2} < \frac{7}{4}, \end{align*}a contradiction. (Here we use the bounds $2<e<3$ and $\pi>3$.)$\blacksquare$ We prove the claim by strong induction on $n\ge 2$, where the base case is trivial (let $S_n$ denote the smallest possible sum of denominators, which is clearly realized by a greedy algorithm). Now suppose that $n\ge3$ and (for some $m\ge3$) \[ n_{m-1}=\phi(2)+\cdots+\phi(m-1)<n\le n_m=\phi(2)+\cdots+\phi(m). \]Then $S{}_{n{}_{m-1}}=2\phi(2)+\cdots+(m-1)\phi(m-1)$ and $S_{n}=2\phi(2)+\cdots+(m-1)\phi(m-1)+m(n-n_{m-1})$, so by the inductive hypothesis it suffices to show that \[ (n-n_{m-1})m \ge \frac{1}{3}(n^{3/2}-n_{m-1}^{3/2}). \]But $\frac{n^{3/2}-n_{m-1}^{3/2}}{n-n_{m-1}} < [x^{3/2}']_{x=n} = \frac{3\sqrt{n}}{2}$, so by lemmas 2 and 3, \[ \frac{n^{3/2}-n_{m-1}^{3/2}}{3(n-n_{m-1})} \le \frac{\sqrt{n}}{2} \le \frac{\sqrt{n_m}}{2} \le \frac{\sqrt{\frac{3m^2}{\pi^2}+\frac{m\ln{m}}{2}+m-1}}{2} \le m, \]as desired.

Be as simple as you can. Note that this is only P4. Solution. We first arrange the fractions in the following manner: $$\frac 12, \frac 13, \frac 23, \frac 14, \frac 24, \frac 34, \frac 15, \frac 25, \frac 35, \frac 45, \frac 16, \frac 26, \frac 36, \cdots$$Then we cut out the ones who share the same value with former ones, which turns out to be: $$\frac 12, \frac 13, \frac 23, \frac 14, \frac 34, \frac 15, \frac 25, \frac 35, \frac 45, \frac 16, \frac 56, \frac 17, \frac 27, \cdots$$Write the fractions $\frac {a_i}{b_i}$. A trivial observation is that the sum $S = \sum_{i=1}^n b_i$ won't decrease after we cut those out. Choose a positive integer $k$ for which $1+\cdots+k-1\le n < 1+\cdots +k$. Then $S\ge \sum_{i=2}^k i(i-1) = \frac{(k-1)k(k+1)}{3}$. Therefore we are reduced to prove $$\frac{(k-1)k(k+1)}{3}\ge \frac 13\left(\frac{k(k+1)}{2}\right)^{\frac 32},$$which is some easy algebra.$\blacksquare$

same solution as @above

Reminded me a bit of Brazil NMO 2022 P5