The solution provided by shovan85 is correct and easy to understand.goyalsau wrote:How many numbers are less than and prime to 600?
120
140
160
180
200
This is a quick approach. Thanks.Rahul@gurome wrote:The solution provided by shovan85 is correct and easy to understand.goyalsau wrote:How many numbers are less than and prime to 600?
120
140
160
180
200
May be this is irrelevant to this problem, but there is a standard method to calculate the number of relatively prime numbers less than a given number. This method is helpful for larger numbers. The method is as follows:For this problem,
- 1. Find the exponential prime factorization of the number.
2. Taking each term separately, change the term to 2 numbers:3. Multiply all the numbers together found in step 2.
- a. Subtract 1 from the base for the first number.
b. Subtract 1 from the exponent and evaluate the expression for the second number. (If the exponent is 1, the second number is always 1.)
600 = (2^3)*(3^1)*(5^2)Therefore, number of integers less than and coprime to 600 = [(1)*(4)]*[(2)*(1)]*[(4)*(5)] = 160.
- For 2 : First number = 2 - 1 = 1; Second number = 2^(3 - 1) = 4
For 3 : First number = 3 - 1 = 2; Second number = 1 (As exponent is 1)
For 5 : First number = 5 - 1 = 4; Second number = 5^(2 - 1) = 5
The correct answer is C.
Though your approach is correct, two things are wrong in your calculation/understanding. One of them includes how to find out the multiple of 5 but not multiple 2 and 3. This can be done using inclusion/exclusion principle of set theory.shovan85 wrote: All multiples of 5. I could not find way for this
discard 5,25,35,55,65,85,95
105,115,145,155,175,185 = 13 in 200 then 39 in 600.
I think 600 has been included in 161. So discard that 160.
Not sure
Yes!! Thanks a lot. Got it nowRahul@gurome wrote: @Shovan85: There are 40 such numbers. Your mistakes are:
- (1) Including 105 (= 3*5*7, contains 3) and excluding 125(= 5*5*5, doesn't contain 2 or 3).
(2) Exclusion of numbers like 215(= 5*43), 235(= 5*47) etc. This mistake is due to generalizing the fact that the numbers are uniformly distributed. Whereas this is impossible as this depends upon the distribution of prime numbers, which doesn't follow any known pattern.
(3) The red line is another mistake. You have excluded 600 when you have discarded the first 300 numbers which is divisible by 2.
This question can be reframed as " How many numbers that are less than 600 and not divisible by 2 or 3 or 5goyalsau wrote:How many numbers are less than and prime to 600?
120
140
160
180
200
Nice formula!!! Just an addition I tried out nowgmatmachoman wrote: This question can be reframed as " How many numbers that are less than 600 and not divisible by 2 or 3 or 5
Formula ( Got frm a friend)
N * ( 1- 1/a) * ( 1- 1/b) * ( 1-1/c)..... where a,b, c are the prime factors of N
SO N = 600 and a=2, b=3, c= 5
Applying the formula : 600 * 1/2 * 2/3 * 4/5
: 160
We can test this formula for small number like N = 10 and not divisible by 2 or 5
10 * ( 1-1/2) ( 1-1/5)
10 * 1/2 * 4/5
= 4
This formula is same as the one I have mentioned before. Just a rearrangement of terms gives it a simple look! Easy to remember also!gmatmachoman wrote:Formula ( Got frm a friend)
N * ( 1- 1/a) * ( 1- 1/b) * ( 1-1/c)..... where a,b, c are the prime factors of N
