Smallest subset of fractions needed to cover the whole set. Consider an integer $n \geq 2$ and the set of fractions $X_n = \{x_1, \dots, x_n\} = \{\frac11, \frac12, \frac13, \dots, \frac1n\}$.  We say that a subset $C_n \subseteq X_n$ is complete if all the values in $X_n$ can be made by adding and subtracting integer multiples of the values in $C_n$.

What is the size of the smallest complete subset $C_n$?

My guess was $\pi(n)$ (the prime counting function) but I don't know how to prove it.
 A: Let $$C_n=\{\,\tfrac1{p^k}\mid p\le n, p\text{ prime},k=\lfloor \log_pn\rfloor\,\}$$
Note that $|C_n|=\pi(n)$.
Claim. If $n>1$, then $C_n$ is complete.
Proof. (By induction).
Let $1\le m\le n$ and assume we already know that $x_{m'}$ is generated by $C_n$ for all $m'$ with $1\le m'<m$. I claim that also $x_m$ is generated by $C_n$:


*

*If $m=1$, pick any $x_d\in C_n$ (note that $C_n\ne\emptyset$ for $n\ge2$!) and note that $x_1=d\cdot\frac 1d$ is generated.

*If $m=p^r$ is a prime power with $r\ge 1$, then necessarily $p\le n$, hence some $\frac1{p^k}\in C_n$. From $m\le n$, we conclude $r\le\lfloor \log_pn\rfloor =k$, hence $\frac1m=p^{k-r}\cdot\frac1{p^k}$ is generated by $C_n$.

*In all remaining cases, we can write $m=ab$ with $\gcd(a,b)=1$ and integers  $a,b>1$. By induction hypothesis, we know that $x_a$ and $x_b$ are generated by $C_n$. From Bezout, we know that $ua+vb=1$ for some integers $u,v$ and hence
$$ x_m=\frac 1m=\frac{ua+vb}{ab}=u\cdot \frac 1a+v\cdot \frac 1b=u\cdot x_a+v\cdot x_b$$
is generated by $C_n$.
$\square$
Claim 2. Any complete set $C_n'\subseteq X_n$ has at least $\pi(n)$ elements.
Proof.
Let $C_n'\subseteq X_n$ be complete.
Let $p$ be a prime $\le n$ and $k=\lfloor \log_p n\rfloor$. 
Assume $C_n'$ contains no $x_m$ with $p^k\mid m$.
Then for all $m$ with $x_m\in C_n'$ we have $m=p^{r_m}u_m$ with $0\le r_m<k$ and $p\nmid u_m$. Let $u$ be the least commn multiple of all $u_m$. Then $p^{k-1}ux_m$ is an integer for all $x_m\in C_n'$. It follows that for all $x$ generated by $C_n'$, we have that $p^{k-1}ux$ is an integer. But $p^{k-1}u\frac1{p^k}$ is not an integer, contradicting completeness. We conclude that $C_n'$ contains some $x_m$ with $p^k\mid m$.
So for each $p\le n$, we can pick $m(p)$ such that $x_{m(p)}\in C_n'$ and $p^{\lfloor \log p n\rfloor}\mid m(p)$. 
Assume that $m(p)=m(q)$ for two distinct primes $p,q$.
Then $p^{\lfloor \log p n\rfloor}q^{\lfloor \log q n\rfloor}\mid m(p)\le n$.
From $p^{\lfloor \log p n\rfloor}\cdot p>n$ it then follows that $p> q^{\lfloor \log q n\rfloor}\ge q$. Similary, we find $q\ge p$, hence $p=q$. We conclude that the map $p\mapsto m(p)$ is injective and the claim follows.
$\square$
