Why are all numbers below n / 2 factors of at least one number above n / 2?

Question

I was trying to solve Project Euler Question 5:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I have solved this problem and my question isn't really about this problem, but about something I noticed while trying to solve it.

Initially, for each whole number above 20, I thought of checking whether it is divisible by every number from 2 to 20. But every number that is divisible by 20 is also divisible by each of its factors. For example, 100 is divisible by 20 and therefore it is also divisible by 2, 4, 5 and 10. So I tried to make a list of numbers from 1 to 20 such that I only have to check if a number is divisble by numbers from that list. Here's my code for it.

def divisors(n):
'''
'''
sieve = [True] * (n + 1)
for i in range(n, 2, -1):
    if sieve[i]:
        for t in range(2, i // 2 + 1):
            if i % t == 0:
                sieve[t] = False
return ([i for i in range(2, n + 1) if sieve[i]])

What struck me was that for any value of n, the list of numbers does not change after I have excluded the factors of numbers greater than about 2/3 * n. So for n = 1000, after I have checked all the numbers from 1000 to 667, I don't need to check for factors of any smaller numbers; the list will stay the same regardless. What amazed me even more was that for each n, the final list contained all the numbers for (n/2) + 1 till n. For example, for n = 1000, the final list will be [551, 552, 553, ...... 998, 999, 1000]

I can't figure out why this is true. Can somebody please explain it to me? And I'm not a mathemaician. Please explain it in simple terms.

Answer 1

Since $2k$ is a multiple of $k$, if $N$ is a multiple of $2k$ then $N$ is also a multiple of $k$.

This means $LCM(1, 2, \ldots, 2n) = LCM(n+1, n+2, \ldots, 2n)$.

However, $LCM(667, 668, \ldots, 1000)$ is not the same as $LCM(1, 2, \ldots, 1000)$. This is because there are some prime numbers less than 667 which do not have multiples between 667 and 1000 (for example 503).

Hopefully this helps!

Answer 2

Think if it this way. If $k$ is smaller then than the range $\frac n2 + 1$ to $n$ then we can't have some multiple $mk \le \frac n2$ and then $mk + k > n$. $k$ is simply too small to step over the range. Formally:

Let $k \le \frac n2$

Let $m*k$ be the largest possible multiple of $k$ that is less then or equal to $\frac n2$ so $mk \le \frac n2$. (Note: $m$ might be $1$. $m$ will be $1$ if $k > \frac k4$. Doesn't matter. There will be some highest multiple. If $\frac n6 \le k < \frac n4$, $m$ will be $2$. If $k$ is smaller $m$ will be higher but there will be some highest multiple of $k$ that is $mk \le \frac n2$)

What is $m*k + k$?

$m*k + k = (m+1)k$ is a higher multiple of $k$ so $(m+1)k > \frac n2$.

But $mk \le \frac n2$ and $k \le \frac n2$ so $mk + k \le \frac n2 + \frac n2 = n$.

So $\frac n2 < (m + 1)k \le n$

Example $k = 500 \le 500;$ then $k + k = 1000$ in the range.

If $k = 499$ then $499 + 499$ is in the range.

If $k= ....$ say $.. 119$ then $4*119 = 476 < 500$. And $476 + 119 = 595$ in the range.

We can't possibly have $m*k \le 500$ outside the range and $m*k + k > 1000$ outside the range when $k \le 500$ is simply too small to step over the range. That would force $k$ to be bigger than $500$.