Prime numbers question

Math Junior
,
1

Prove that there are 1000 consecutive natural numbers such that only 10 of them are prime numbers.

2 Likes
2

\color{red}{\text{𝓑𝓮𝓪𝓾𝓽𝓲𝓯𝓾𝓵 𝓹𝓻𝓸𝓫𝓵𝓮𝓶 }\heartsuit}

1 Like
3

\color{lime}{\text{Proof:}}

For each integer \color{yellow}{n \ge 1}, let
\color{magenta}{f(n) = \#\{\text{primes in the block } \{n+1,n+2,\dots,n+1000\}\}}

\color{cyan}{\text{(1) A prime–rich block}}
Between \color{yellow}{2} and \color{yellow}{1001} there are \color{yellow}{\pi(1001)=168>10} primes, so \color{orangered}{f(1)=168}

\color{cyan}{\text{(2) A prime–free block}}
Let \color{yellow}{N=1001}. Then the \color{yellow}{1000} consecutive numbers
\color{yellow}{N!+2,\,N!+3,\,\dots,\,N!+N}
are all composite, since \color{yellow}{N!+k} is divisible by \color{yellow}{k} for each \color{yellow}{2 \le k \le N}. Thus the block starting at \color{yellow}{n_0 := N!+1} has no primes: \color{orangered}{f(n_0)=0}

\color{cyan}{\text{(3) Discrete continuity}}
Shifting the window by one step removes at most one integer and adds at most one. Hence
\color{yellow}{f(n+1)-f(n) \in \{-1,0,1\}} for every \color{yellow}{n}

\color{cyan}{\text{(4) Interpolation}}
Starting from \color{orangered}{f(1)=168} and moving step-by-step to \color{orangered}{f(n_0)=0}, the values of \color{yellow}{f} change by at most \color{yellow}{1} each time. Therefore \color{yellow}{f} attains every integer value between \color{yellow}{0} and \color{yellow}{168}, in particular \color{orangered}{f(n)=10} for some \color{yellow}{n}

Thus there are \color{yellow}{1000} consecutive integers with exactly \color{yellow}{10} primes \blacksquare :partying_face:

\color{lime}{\text{*Remark:}} The same argument shows that for each \color{yellow}{t \in \{0,1,\dots,168\}} there is a block of \color{yellow}{1000} consecutive integers containing exactly \color{yellow}{t} primes

\color{lime}{\text{Thought process:}}

  • \color{cyan}{\text{Goal:}} Find \color{magenta}{1000} consecutive numbers with a prescribed number of primes
  • \color{cyan}{\text{Step 1:}} Look for an interval with many primes: the first \color{magenta}{1000} numbers already give \color{magenta}{168>10}
  • \color{cyan}{\text{Step 2:}} Look for an interval with none: the factorial trick guarantees \color{magenta}{1000} consecutive composites
  • \color{cyan}{\text{Step 3:}} As the sliding window moves, the prime count changes by at most \color{magenta}{1}, so all intermediate values must appear
  • \color{cyan}{\text{Conclusion:}} In particular, the value \color{magenta}{10} is realized somewhere :+1:
1 Like