6 1 6 0 , 6 7 6 0 , 7 1 6 0 , …
How many reduced positive fractions less than 1 are there with the numerator equal to 60 and the denominators less than 10,000?
Clarification:
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
can we write the number of integers co prime to x , less than n , is equivalent to floor of each term of
n × ∏ ( 1 − p i 1 )
where p i denotes the prime factors of x ?
Log in to reply
Yes; we have ϕ ( n ) = ϕ ( p 1 e 1 ⋅ p 2 e 2 ⋯ ) = p 1 e 1 − 1 ( p 1 − 1 ) ⋅ p 2 e 2 − 1 ( p 2 − 1 ) ⋯ = p 1 e 1 ⋅ p 1 p 1 − 1 ⋅ p 2 e 2 ⋅ p 2 p 2 − 1 ⋯ = n ⋅ ( 1 − p 1 1 ) ⋅ ( 1 − p 2 1 ) ⋯ .
Log in to reply
This is the totient function of n
but I intend to find the number of integers co prime to x less than n where n = x
is it equal to the floor of each individual term in the expanded out version of
n × ∏ ( 1 − p i 1 )
where p i denotes the prime factors of x
Log in to reply
@Anirudh Sreekumar – I see what you mean, and is obvious when n is a multiple of x . It seem to work for other values as well. Do you have a proof?
2, 3, 4, and 5 are factors of 60. Since what ever divisible by 4 is also divisible by 2, we only consider 2, 3, and 5.
So number with units ending in even digit or 5 or 0 has to be rejected.
From 1 to 30, .........if the tenth digit is 0 unit digit 3 and 9 are rejected ,.................. This is true for tenth digit ç, if X=0. ........Two useful.
...............................if the tenth digit is 1 unit digit 1, 3, 7, and 9 are rejected ,........ This is true for tenth digit T equivalent X (mod 3), if X=1. ........Four useful.
...............................if the tenth digit is 2 unit digit 3 and 9 are rejected ,.................. This is true for tenth digit T equivalent X (mod 3), if X=2. ........Two useful.
So every such group of 30 has 8 useful numbers.
10000/30=333 + 1/3.
333 has 8 useful numbers. This 1/3 is T equivalent 0 (mod 3) , so has Two useful numbers.
Thus 333 * 8 + 2=2666 useful numbers. But 1 to 60 in this are not > 60. So we take away 2 * 8 =16.
Reduced positive fractions less than 1, =2666-16=
2
6
5
0
.
We mean to find all integers greater than 6 0 and less than 1 0 0 0 0 that are coprime to 6 0 , i.e. that are not multiples of any of the divisors of 6 0 . Since 6 0 = 2 2 ∗ 3 ∗ 5 , we are looking for all integers in this interval that are not multiples of 2 , 3 or 5 . One way to do this is to get the number of odd integers in this interval, take out the odd multiples of 5 , take out the odd multiples of 3 and finally add the odd multiples of both 3 and 5 (multiples of 1 5 ), given that we've accounted for them twice in the last two steps. Using the formula u n = u 1 + r . ( n − 1 ) , where n is the number of terms of the AP and r the common ratio, replacing the last term in the interval ( u n ) and the first one yields the number of terms n. STEP 1: ODD NUMBERS: 9 9 9 9 = 6 1 + 2 . ( n − 1 ) ≡ n = 4 9 7 0 . STEP 2: MULTIPLES OF 5: 9 9 9 5 = 6 5 + 1 0 . ( n − 1 ) ≡ n = 9 9 4 . STEP 3: ODD MULTIPLES OF 3: 9 9 9 9 = 6 3 + 6 . ( n − 1 ) ≡ n = 1 6 5 7 . STEP 4: ODD MULTIPLES OF 15: 9 9 7 5 = 7 5 + 3 0 . ( n − 1 ) ≡ n = 3 3 1 . SO, the answer is 4 9 7 0 − 9 9 4 − 1 6 5 7 + 3 3 1 = 2 6 5 0 .
Problem Loading...
Note Loading...
Set Loading...
In the set of possible denominators { 6 1 , 6 2 , … , 9 9 9 9 } we must find those that are coprime to 60.
Since g cd ( 6 0 , a + 6 0 b ) = g cd ( 6 0 , a ) , the pattern of valid denominators repeats with period sixty. The number of values between 0 and 5 9 that are coprime to 60 is ϕ ( 6 0 ) = 1 6 ( Euler totient function ).
Between 60 and 10,000 there are ⌊ ( 1 0 0 0 0 − 6 0 ) / 6 0 ⌋ = 1 6 5 such periods, accounting 1 6 5 × 1 6 = 2 6 4 0 valid denominators. We only need to look at the denominators beyond the last full period, i.e. d > 9 9 6 0 . Because of symmetry, the first half period ( 9 9 6 0 ≤ d < 9 9 9 0 ) contains 1 6 / 2 = 8 valid denominators. Finally, we consider the number of valid denominators between 9 9 9 0 and 9 9 9 9 , which is the same as the number of values between 3 0 and 3 9 that are coprime to 60. Only 3 1 and 3 7 qualify; therefore we have a total of 2 6 4 0 + 8 + 2 = 2 6 5 0 denominators that are coprime to 60, and therefore 2650 reduced fractions of the kind required.