2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thank you. I couldn't understand it at first but now I have figured it out. $\endgroup$ – Huzaifa Hussain Jun 1 '17 at 14:53
  • $\begingroup$ If I multilpy all the numbers from 26 to 50 by 2, I'll get an (even) number between 51 and 100. Therefore, the LCM of numbers from 51 to 100 is also the LCM of numbers from 26 to 50. By the same logic, the LCM of numbers from 26 to 50 is also the LCM of numbers from 13 to 25. But since the LCM of numbers of 51 to 100 is also the LCM of numbers from 26 to 50. Therefore the LCM of numbers from 51 to 100 is also the LCM of numbers from 13 to 50. We can keep following this logic till we get to 2 so that the LCM of numbers from 51 t 100 is also the LCM of numbers from 2 to 50. $\endgroup$ – Huzaifa Hussain Jun 1 '17 at 15:00
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.