1000000 consecutive numbers divisible by the square of a prime

Question

I am trying to prove there exist 1000000 consecutive numbers divisible by the square of a prime.

I have already tried several ways

• prove that the alternative is impossible didn’t work because it’s easy to find a million numbers that are not all non-prime;
• I tried ‘constructing’ a list, by starting from a random list and multiplyingcto get squares of primes, no luck…

I am currently traveling with limited network, so it’s difficult to look up tips online. If anyone can give me a hint in the right direction, that would be much appreciated…

Thanks!

Answer 1

Pick three primes $p, q,$ and $r$. Use the Chinese Remainder Theorem to solve the system

$$n \equiv 0 \pmod{p^2}$$ $$n \equiv -1 \pmod{q^2}$$ $$n \equiv -2 \pmod{r^2}$$

Then $p^2\mid n$, $q^2\mid n+1$, $r^2\mid n+2$.

So there are three consecutive numbers divisible by the square of a prime.

Answer 2

First, let's tackle smaller versions of the problem.

Let $f(n)$ be the smallest positive integer $k$ such that all $n$ integers between $k$ and $k + n - 1$ are divisible by the square of a prime. By simple brute force:

• $f(1) = 4$
• $f(2) = 8$
• $f(3) = 48$
• $f(4) = 242$
• $f(5) = 844$

And this is enough values to search OEIS and find that someone has already implemented this sequence and published it as A045882. So you “just” need an efficient algorithm to find $f(1000000)$, which according to the linked page does exist because the sequence is infinite.