Let $p=g(n)$ be the least prime dividing $n$. Then $n-p$, $n-2p$,...,$n-(\lceil\frac{n}{2p}\rceil-1) p$ all satisfy the condition. So if $(\lceil\frac{n}{2p}\rceil-1)>k$ we are done and $n$ can't be a solution. The only cases left are those when $\frac{n}{p}$ is bounded above by a constant $K=2(k+1)$. So if $n=pt$ with $t>1$, it follows that $p\leq g(t)\leq t\leq K$, which means $n=pt\leq K^2$, which implies $n$ is bounded. If $n=p$, then $f(n)=0<k$ since $k$ is a strictly positive integer. Therefore there are only finitely many such $n$ (at most $[2(k+1)]^2$).

cadaeibf wrote: Let $p=g(n)$ be the least prime dividing $n$. Then $n-p$, $n-2p$,...,$n-(\lceil\frac{n}{2p}\rceil-1) p$ all satisfy the condition. Why? Can someone explain this?

This message is regarding this post.

I did an overkill solution for this problem. I'll post it for storage purposes. We prove two lemmas that will kill the problem. $\textbf{Lemma 1.}$ For all composite $n$, $\varphi(n)\leq n-\sqrt{n}.$ $\textbf{Proof:}$ Let $1<d\leq\sqrt{n}$ be a divisor of $n$. Then all multiples of $d$ are not coprime with $n$ and since there are $\frac{n}{d}\geq\sqrt{n}$ of them between $1$ and $n$, we get the desired result. $\square$ $\textbf{Lemma 2.}$ For all $\epsilon >0$ there exists $N_{\epsilon}$ such that for all $n>N_{\epsilon}$ we have $d(n)<n^{\epsilon}$, where $d(n)$ is the number of divisors of $n$. $\textbf{Proof:}$ Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. We have $$\frac{d(n)}{n^{\epsilon}}=\prod_{1\leq i\leq k}\frac{\alpha_i+1}{p_i^{\alpha_i\epsilon}}.$$If $p_i>e^{\frac{1}{\epsilon}}$, from the well known inequality $e^x\geq x+1$, we get that the factor $\frac{\alpha_i+1}{p_i^{\alpha_i\epsilon}}<1$. If $p_i<e^{\frac{1}{\epsilon}}$, since for large $\alpha_i$ we have $p_i^{\alpha_i\epsilon}>\alpha_i+1$, the function $f_i(x)=\frac{x+1}{p_i^{x\epsilon}}$ has a maximum with $x\in[1,\infty],$ and thus is bounded by some $C_{p_i}$, that only depends on $p_i$. Thus, if $C=\prod_{p<e^{\frac{1}{\epsilon}}}C_p$, we have $$\frac{d(n)}{n^{\epsilon}}\leq C,$$and we got a uniform upper-bound, achieving the desired result. $\square$ Now, see that $f(n)=n-\varphi(n)-d(n)$. If $n=p$ prime, $f(n)=0$ which is not a positive integer. If $n$ is composite, by lemmas $1$ and $2$ $$f(n)\geq n^{\frac{1}{2}}-d(n)>n^{\frac{1}{2}}-n^{\frac{1}{3}},$$for big $n$, which explodes for large values of $n$, and thus any value only appears finitely many times in the image of $f$, as wanted. $\blacksquare$

jrsbr wrote: $f(n)=n-\varphi(n)-d(n)$ Interesting approach, though the mentioned preposition should be $f(n)=n-\varphi(n)-d(n) + 1$, since number one is counted twice in $\varphi(n)$ and $d(n)$

Since $f(p)=0$ and $k\in Z^+,$ we won't consider the case that $n$ is prime. \[a\in S\iff 0<a<n, \ (a,n)>1, \ a\not| n \]And $f(n)=|S|$. Let's show that there exist at least $\lfloor \frac{n}{2}\rfloor-\frac{\phi(n)}{2}-1$ numbers in $S$ among the numbers between $\lfloor \frac{n}{2}\rfloor$ and $n$. Since $(d,n)=1\iff (n-d,n)=1,$ there are at most $\frac{\phi(n)}{2}+1$ integers in $[\lfloor\frac{n}{2}\rfloor,n]$ which are coprime with $n$. Hence there are at least $\lfloor \frac{n}{2}\rfloor -\frac{\phi(n)}{2}-1$ integers $\geq \lfloor \frac{n}{2}\rfloor$ in $S$. Now we will show that $\lfloor\frac{n}{2}\rfloor-\frac{\phi(n)}{2}-1>k$ for some $n\geq N$. Since $n$ cannot be prime, we can write $n=p_1^{\alpha_1}...p_k^{\alpha_k}$ where $k\geq 2$. We have $p_1...p_k-(p_1-1)...(p_k-1)>p_2...p_k\iff p_2...p_k(p_1-1)>(p_1-1)(p_2-1)...(p_k-1)$ which is true. $\lfloor\frac{n}{2}\rfloor-\frac{\phi(n)}{2}-1\geq \frac{n}{2}-\frac{\phi(n)}{2}-2=\frac{1}{2}(p_1^{\alpha_1-1}...p_k^{\alpha_k-1}(p_1...p_k-(p_1-1)...(p_k-1)))-2>\frac{1}{2}(p_1^{\alpha_1-1}p_2^{\alpha_2}...p_k^{\alpha_k})-2$ $=\frac{n}{2p_1}-2$ which is larger than $t$ for sufficiently large $n$ since it has at least $2$ prime divisors ($\frac{n}{2p_1}>\frac{\sqrt{n}}{2})$. Thus, we get the desired result.$\blacksquare$