Measure of $A = \{n \in \mathbb{N} : n = k + \tau(k)\}$ over $\mathbb{N}$ Let's consider $A = \{n \in \mathbb{N} : n= k+\tau(k); k \in \mathbb{N}\}$, where $\tau$ is number of divisors function. We want to examine whether this set has full measure or not, i.e. $\mathbb{N}$ \ $A$ is finite or not.
Actually I thought this problem is quiet easy and I tried to construct some counter example. But I've got stuck and decided that is true. Then I've tried to work with $A_k = \{p_1 \cdot ... \cdot p_s + 2^s; s \le k\}$ and $B_k = \{p^s + s + 1 ; s \le k\}$ to construct all $\mathbb{N}$ numbers. But I'm not sure that $\bigcup_k (A_{k}\cup \bigcup_{p}B_k)$  covers all naturals. 
Actually I've found theOEIS for this problem.
Edit: I guess there is an idea to prove, but I'm not sure how to complete it. Let's divide $\mathbb{N} = [1;a_1]\cup [a_1 + 1;a_2] \cup \dots$. .For every disjoint segment let's prove that there is exists $a^i_j \in [a_i+1,a_{i+1}]$, s.a. $a^{j}_i \ne k + \tau(k)$. For this proof we may try to use inequalities about $\tau(k)$. F.e. we may divide this segments by following rule: next segment is constructed(if it possible) by only elements of previous one. So we can give the worst bound  for $\tau \le 2\sqrt{n}$ and try to find element, bad element in other segment.
Any hints?
 A: We define:
$$A=\{k+\tau(k) \mid k \in \mathbb{N}\}$$

Claim: The set $A$ does not have full measure, i.e.
  $$|\overline{A}| = \infty$$

Assume the contrary. We have:
$$S=\overline{A}=\{n \mid \not\exists \space k \in \mathbb{N} \text{ s.t. } n = k+\tau(k) \space; n \in \mathbb{N}\}$$
where $|S| = m$ is finite.
Let $N \in \mathbb{N}$ be sufficiently large. We consider the values $k+\tau(k) \space (1 \leqslant k \leqslant N)$. From $1$ to $N$, there are only $m$ numbers which cannot be expressed as $k+\tau(k)$ amd thus, the remaining numbers can be expressed as $k+\tau(k)$. For $n=k+\tau(k)$ where $n \leqslant N$, we will also have $k \leqslant N$ as if $k>N$, then $n=k+\tau(k)>k>N$ (which is false).
This means that out of the $N$ values $k+\tau(k) \space (1 \leqslant k \leqslant N)$ :


*

*$N-m$ values are the elements of $\{1,2,3,\ldots,N\}-S$

*The remaining $m$ values are numbers less than $2N$ as $k+\tau(k) <2N$.


Thus:
$$\sum_{k=1}^N (k+\tau(k)) < \sum_{i=1}^N i - \sum_{t \in S} t + (2N)m \leqslant \frac{N(N+1)}{2}-\frac{m(m+1)}{2}+2Nm$$
But we also have:
$$\sum_{k=1}^N (k+\tau(k)) = \sum_{k=1}^N k + \sum_{k=1}^N \tau(k) = \frac{N(N+1)}{2}+
\sum_{i=1}^N \bigg\lfloor \frac{N}{i} \bigg \rfloor$$
$$\sum_{k=1}^N (k+\tau(k)) > \frac{N(N+1)}{2}+N\sum_{i=1}^N \frac{1}{i}-N>\frac{N(N+1)}{2}+N\log{N}-N$$
Thus, we have:
$$\frac{N(N+1)}{2}-\frac{m(m+1)}{2}+2Nm>\frac{N(N+1)}{2}+N\log{N}-N$$
$$2Nm-\frac{m(m+1)}{2}>N\log{N}-N \implies (2m+1)N>N\log{N} \implies 2m+1>\log{N}$$
This is obviously a contradiction as $N$ can get arbitrarily large. Thus, our claim is true and we have proved the required.
