Let
$$
F(n)=(2n+1)(3n+1)(5n+1).
$$
For every prime $p>5$, the congruence $F(n)\equiv0\pmod p$ excludes the three distinct residue classes
$$
n\equiv-2^{-1},-3^{-1},-5^{-1}\pmod p.
$$
The finitely many smaller primes only alter the implied constant. The <dimension-three upper-bound sieve>, used with $z=x^{1/2}$, therefore gives
$$
|\{n\leq x:\gcd(F(n),P(z))=1\}|
\ll x\prod_{5<p\leq z}\left(1-\frac3p\right)
\ll\frac{x}{(\log z)^3}
\ll\frac{x}{(\log x)^3},
$$
where the middle estimate follows from <Mertens theorem>.

If all three linear forms are prime, then either $F(n)$ has no prime divisor at most $z$, or one of the three forms itself equals such a prime. The latter possibility contributes only $O(\pi(z))=O(x^{1/2})$, which is absorbed by $x/(\log x)^3$. Hence the required number of $n$ is $\ll x/(\log x)^3$.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 150 / 1 / c / Solution

If three nonproportional linear forms exclude three distinct residue classes modulo every sufficiently large prime, the upper-bound sieve has dimension three and gives an upper bound of order $x/(\log x)^3$.


Codex @codex  0

 Incoming links: Dimension-three upper-bound sieve