Prove there are infinite many integer $n>0$ such that exactly two numbers among $n, n+1, n+2, n+3$ contain an even number of different prime divisors We say a natural number is good if it has an even number of different prime divisors. Prove there's infinitely many numbers $n$ such that ${n,n+1,n+2,n+3}$ contains exactly $2$ good numbers.
Hi guys, I found this question in an Olympiad problem set. It doesn't say what contest it's from, but I'm pretty sure it's somewhere near state level. Here's my work so far.
We can prove there's infinitely many numbers with an even number of different prime divisors by assuming the opposite. Let's assume there's a finite number of numbers with an even number of different prime divisors. Lets take the maximum of those numbers and say it's $x$. We can take primes $p,q$ such that they're bigger than $x$ and the number $x\cdot p\cdot q$ will also have an even number of prime divisors and be bigger than $x$, therefore we have a contradiction.
After this, I looked at assuming that $n$ is a good number and looking at what that means for the other three numbers. If we assume $n$ is even (which we can using a similiar proof like the one above, but for even numbers exclusively) and the other $3$ aren't good we know that numbers $2\cdot n$ and $2\cdot (n+1)$ will be good. So the group ${2\cdot n, 2\cdot n + 1, 2\cdot n + 2,2\cdot n + 3}$ will have atleast $2$ good numbers. I'm not sure where to go from here, any help is appreciated, thanks!
 A: Let $h(n)$ count how many good numbers are in $\{n,n+1,n+2,n+3\}$. Then $h(n)$ is a natural number between $0$ and $4$, and furthermore, the difference between $h(n+1)$ and $h(n)$ is at most $1$ (when passing from $\{n,n+1,n+2,n+3\}$ to $\{n+1,n+2,n+3,n+4\}$, we lose at most one good number and gain at most one).
The main property of such functions is that "discrete intermediate value theorem" holds for them – for any $a<b$ every natural number in the interval $[h(a),h(b)]$ is attained as some $h(c)$ with $c \in [a,b]$. This is very intuitive – as in each step $h$ changes by at most $1$, we cannot jump over $h(c)$.
In particular, using your reasoning, if we have even $n$ which is good, and with $h(n)=1$, then $h(2n) \geqslant 2$, so there is at least one $m \in [n,2n]$ with $h(m)=2$. This is already half of the problem – if we had only finitely many $n$ with $h(n)=2$, then for large enough $n$ we need to have either $h(n) \leqslant 1$ or $h(n) \geqslant 3$. The first case follows from your solution, and you can try to solve the other one in a similar fashion – you take some particular large $n$, and you try to produce some number with $h(m) \leqslant 2$.
A: I'll start with radekzak's observation that if there are not infinite many $n$ with $h(n)=2$, then either $h(n)\le1$ or $h(n)\ge3$ from some large $n$ and onward.
The idea is to show that, as $n$ grows, on average half the integers are good.
If $h(n)\le1$, then at most a quarter of the integers are good; if $h(n)\ge3$, at least three quarters of them are good. Neither is possible if half of them are good.
Let $\chi(n)=(-1)^\text{number of distinct prime factors}$ which is $1$ if $n$ is good, $-1$ if $n$ is not good. Then, for $s>1$, define
$$
\xi(s) = \sum_{n=1}^\infty\frac{\chi(n)}{n^s}
= \prod_{p\text{ prime}}\left(1-p^{-s}-p^{-2s}-\cdots\right).
$$
Note that the factors in the product are positive, but less than $1-p^{-s}$,
so
$$
0\le\xi(s)
= \prod_{p\text{ prime}}\left(1-p^{-s}-p^{-2s}-\cdots\right)
\le\prod_{p\text{ prime}}\left(1-p^{-s}\right)
=\frac{1}{\zeta(s)}
$$
where $\zeta(s)=\sum_{n=1}^\infty n^{-s}$ is Riemann's zeta function. The limit of the right hand side as $s\rightarrow 1$ is zero, which gives the limit
$$
\xi(1):=\lim_{s\rightarrow 1^+}\xi(s)=0.
$$
If $h(n)\ge3$ for large $n$, then
$$
\frac{\chi(n)}{n}+\frac{\chi(n+1)}{n+1}
+\frac{\chi(n+2)}{n+2}+\frac{\chi(n+3)}{n+3}>0
$$
which would force $\xi(1)>0$. If $h(n)\le1$, it would make $\xi(1)<0$. Since $\xi(1)=0$, this is not possible, and so there must be infinitely many $n$ with $h(n)=2$.
