Numerator sixty

60 61 , 60 67 , 60 71 , \frac{60}{61},\ \frac{60}{67},\ \frac{60}{71},\ \ldots

How many reduced positive fractions less than 1 are there with the numerator equal to 60 and the denominators less than 10,000?


Clarification:

  • The fraction 60 122 \frac{60}{122} does not count because it can be reduced to 30 61 \frac{30}{61} .
  • The fractions 60 3 \frac{60}3 and 60 60 \frac{60}{60} do not count because they are not less than 1.


The answer is 2650.

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.

3 solutions

Arjen Vreugdenhil
Mar 19, 2017

In the set of possible denominators { 61 , 62 , , 9999 } \{61, 62, \dots, 9999\} we must find those that are coprime to 60.

Since gcd ( 60 , a + 60 b ) = gcd ( 60 , a ) \gcd(60, a+60b) = \gcd(60, a) , the pattern of valid denominators repeats with period sixty. The number of values between 0 0 and 59 59 that are coprime to 60 is ϕ ( 60 ) = 16 \phi(60) = 16 ( Euler totient function ).

Between 60 and 10,000 there are ( 10 000 60 ) / 60 = 165 \lfloor(10\:000 - 60)/60\rfloor = 165 such periods, accounting 165 × 16 = 2640 165 \times 16 = 2640 valid denominators. We only need to look at the denominators beyond the last full period, i.e. d > 9960 d > 9960 . Because of symmetry, the first half period ( 9960 d < 9990 9960 \leq d < 9990 ) contains 16 / 2 = 8 16/2 = 8 valid denominators. Finally, we consider the number of valid denominators between 9990 9990 and 9999 9999 , which is the same as the number of values between 30 30 and 39 39 that are coprime to 60. Only 31 31 and 37 37 qualify; therefore we have a total of 2640 + 8 + 2 = 2650 2640 + 8 + 2 = \boxed{2650} denominators that are coprime to 60, and therefore 2650 reduced fractions of the kind required.

can we write the number of integers co prime to x x , less than n n , is equivalent to floor of each term of

n × ( 1 1 p i ) \begin{aligned}n\times\prod\left( 1- \dfrac{1}{p_{i}}\right)\end{aligned}

where p i p_{i} denotes the prime factors of x x ?

Anirudh Sreekumar - 4 years, 2 months ago

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 1 p 1 p 2 e 2 p 2 1 p 2 = n ( 1 1 p 1 ) ( 1 1 p 2 ) . \phi(n) = \phi(p_1^{e_1}\cdot p_2^{e_2}\cdots) = p_1^{e_1-1}(p_1-1) \cdot p_2^{e_2-1}(p_2-1) \cdots \\ = p_1^{e_1}\cdot\frac{p_1-1}{p_1}\cdot p_2^{e_2}\cdot\frac{p_2-1}{p_2}\cdots \\ = n\cdot\left(1-\frac1{p_1}\right)\cdot\left(1-\frac1{p_2}\right)\cdots.

Arjen Vreugdenhil - 4 years, 2 months ago

Log in to reply

This is the totient function of n n

but I intend to find the number of integers co prime to x x less than n n where n x n\neq x

is it equal to the floor of each individual term in the expanded out version of

n × ( 1 1 p i ) \begin{aligned}n\times\prod\left( 1- \dfrac{1}{p_{i}}\right)\end{aligned}

where p i p_{i} denotes the prime factors of x x

Anirudh Sreekumar - 4 years, 2 months ago

Log in to reply

@Anirudh Sreekumar I see what you mean, and is obvious when n n is a multiple of x x . It seem to work for other values as well. Do you have a proof?

Arjen Vreugdenhil - 4 years, 2 months ago

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= 2650. \Large \color{#D61F06}{2650}.



Tomás Carvalho
Apr 12, 2017

We mean to find all integers greater than 60 60 and less than 10000 10000 that are coprime to 60 60 , i.e. that are not multiples of any of the divisors of 60 60 . Since 60 = 2 2 3 5 60 = 2^{2} * 3 * 5 , we are looking for all integers in this interval that are not multiples of 2 , 3 2, 3 or 5 5 . One way to do this is to get the number of odd integers in this interval, take out the odd multiples of 5 5 , take out the odd multiples of 3 3 and finally add the odd multiples of both 3 3 and 5 5 (multiples of 15 15 ), given that we've accounted for them twice in the last two steps. Using the formula u n = u 1 + r . ( n 1 ) 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 u_{n} ) and the first one yields the number of terms n. STEP 1: ODD NUMBERS: 9999 = 61 + 2. ( n 1 ) 9999 = 61 + 2.(n-1) n = 4970 \equiv n = 4970 . STEP 2: MULTIPLES OF 5: 9995 = 65 + 10. ( n 1 ) 9995 = 65 + 10.(n-1) n = 994 \equiv n = 994 . STEP 3: ODD MULTIPLES OF 3: 9999 = 63 + 6. ( n 1 ) 9999 = 63 + 6.(n-1) n = 1657 \equiv n = 1657 . STEP 4: ODD MULTIPLES OF 15: 9975 = 75 + 30. ( n 1 ) 9975 = 75 + 30.(n-1) n = 331 \equiv n = 331 . SO, the answer is 4970 994 1657 + 331 = 2650 4970 - 994 - 1657 + 331 = 2650 .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...