I am dealing with divisibility problems, such as:
Find the number of positive integers that is divisible by either of 2 or 5 within 1000. In this case, I decide to look at how many integers are divisible by 2 or 5 within 10, that is 6. So we can deduce that there are 600 numbers that could be divided by 2 or 5 within 1000.
But, what if we are trying to find number of positive integers that is divisible by both 3 or 7 within 1000, I found that the number block of '10' cannot work here, and if we try number block of '21', meaning that to find how many number is divisible by 3 or 7 within 21, and then use 1000 divides 21 to see how many blocks are there within 100, that will work. May I know what is the mechanism behind this or is there any general rule for dealing with this type problem?

Thank you so much for you guy's replies

  • $\begingroup$ There are $\lfloor\frac{1000}2\rfloor+\lfloor\frac{1000}3\rfloor-\lfloor\frac{1000}6\rfloor=667$ numbers between $1$ and $1000$ divisible by $2$ or $3$. $\endgroup$ – saulspatz Feb 1 '20 at 16:44
  • $\begingroup$ Sorry, sorry, is not divisible by 2 or 5... $\endgroup$ – Henry Cai Feb 1 '20 at 16:48
  • $\begingroup$ @saulspatz hello sir, your method can also be used. Thank you very much. This is much help. $\endgroup$ – Henry Cai Feb 1 '20 at 16:49
  • $\begingroup$ Sure I will change it now $\endgroup$ – Henry Cai Feb 1 '20 at 16:54

The size of the number block is the least common multiple of the divisors. If the divisors do not have a common factor it is just the product, but if your divisors are $4,6$ the minimum block would be $12$. It is the shortest block which goes through an integer number of cycles of all the divisors.

  • $\begingroup$ Thank you very much sir $\endgroup$ – Henry Cai Feb 1 '20 at 16:53

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.