Solution

Let us call two positive integers \(m, n\) friends if \(p(m)+p(n)\) and \(q(m)+q(n)\) are both even integers. We start by noting that the pairs \((p(k), q(k))\) modulo 2 can take at most 4 different values; thus, among any five different positive integers there are two which are friends.

In addition, both functions \(p\) and \(q\) satisfy \(f(a b)=f(a)+f(b)\) for any \(a, b\). Therefore, if \(m\) and \(n\) are divisible by \(d\), then both \(p\) and \(q\) satisfy the equality \(f(m)+f(n) = f(m/d) + f(n/d) + 2f(d)\). This implies that \(m, n\) are friends if and only if \(m/d, n/d\) are friends.

Let us call a set of integers \(\left\{n_{1}, n_{2}, \ldots, n_{5}\right\}\) an interesting set if for any indexes \(i, j\), the difference \(d_{i j}=\left|n_{i}-n_{j}\right|\) divides both \(n_{i}\) and \(n_{j}\). We claim that if elements of an interesting set are all positive, then we can obtain a special integer. Indeed, if we were able to construct such a set, then there would be a pair of integers \(\left\{n_{i}, n_{j}\right\}\) which are friends, according to the first observation. Additionally, the second observation yields that the quotients \(n_{i} / d_{i j}, n_{j} / d_{i j}\) form a pair of friends, which happen to be consecutive integers, thus giving a special integer as desired.

In order to construct a family of interesting sets, we can start by observing that the set \(\{0,6,8,9,12\}\) is an interesting set. Using that \(72=2^{3} \cdot 3^{2}\) is the least common multiple of all pairwise differences in this set, we obtain a family of interesting sets by considering

\[\{72 k, 72 k+6,72 k+8,72 k+9,72 k+12\}\]

for any \(k \geqslant 1\). If we consider the quotients (of these numbers by the appropriate differences), then we obtain that the set

\[S_{k}=\{6 k, 8 k, 9 k, 12 k, 12 k+1,18 k+2,24 k+2,24 k+3,36 k+3,72 k+8\}\]

has at least one special integer. In particular, the interval \([1,100 k]\) contains the sets \(S_{1}, S_{2}, \ldots, S_{k}\), each of which has a special number. Any special number can be contained in at most ten sets \(S_{k}\), from where we conclude that the number of special integers in \([1,100 k]\) is at least \(k/10\). Finally, let \(N=100 k+r\), with \(k \geqslant 1\) and \(0 \leqslant r<100\), so that we have \(N<100(k+1) \leqslant 200k\). Then the number of special integers in \([1, N]\) is at least \(k/10 > N/2000\), as we wanted to prove. **Comment 1.** The statement is also true for \(N \geqslant 15\) as at least one of the numbers \(7,14,15\) is special. **Comment 2.** Another approach would be to note that if \(p(2 n), p(2 n+1), p(2 n+2)\) all have the same parity then one of the numbers \(n, 2n, 2n+1\) is special. Indeed, if \(q(n)+q(n+1)\) is even then \(n\) is special since \(p(n)+p(n+1) \equiv p(2n) + p(2n+2) \equiv 0 \pmod {2}\). Otherwise, if \(q(n)+q(n+1)\) is odd, so is \(q(2n) + q(2n+2)\) which implies that exactly one of the numbers \(2n, 2n+1\) is special. Unfortunately, it seems hard to show that the set of such \(n\) has positive density: see a recent paper [https://arxiv.org/abs/1509.01545](https://arxiv.org/abs/1509.01545) for the proof that all eight patterns of the parities of \(p(n), p(n+1), p(n+2)\) appear for a positive proportion of positive integers.