Fractions between 0 and 1Date: 07/29/2001 at 12:45:17 From: Courtney Allison Subject: Way to find number of fractions between 0 and 1 with denominators from 2 to 100 Dear Dr. Math, Is there a way to find the number of different (no equivalent fractions) fractions between 0 and 1 with denominators from 2 to 100 without writing out every fraction and counting them? Or is this information already charted somewhere on the Web? Thanks, Courtney Date: 07/30/2001 at 13:14:40 From: Doctor Greenie Subject: Re: Way to find number of fractions between 0 and 1 with denominators from 2 to 100 Hi, Courtney - I don't see a way to come up with a formula that will tell you explicitly how many different fractions there will be with denominators less than or equal to some integer n. That is, I can't come up with an explicit formula that will give the answer to the question "how many irreducible fractions are there with denominators less than or equal to 123?" (Note that there is a huge amount of work that has been done in number theory with which I am not familiar. It is quite conceivable to me that there might be a way to develop an explicit formula using some of these more advanced techniques.) But there at least appears to be a way to determine the number of irreducible fractions for any denominator n without writing out all the proper fractions with that denominator and counting the ones which can't be reduced. Let's think first of counting the fractions with denominator n which CAN be reduced. These are the fractions whose numerators have a factor in common with the denominator. Suppose the prime factorization of the denominator contains the prime factors (p1, p2, p3, p4, ...). Let A, B, C, D, ... be the sets consisting of all the numbers less than the denominator n which are multiples of the prime factors p1, p2, p3, p4, ..., respectively. The number of fractions with denominator n that CAN be reduced is the number of elements in the union of sets A, B, C, D, .... Recognizing that for a large denominator n the list of distinct prime factors can be large, I will sipmlify the discussion from this point on by describing the case where the prime factorization contains only (at most) four distinct primes. The inclusion/exclusion principle tells us how to count the number of elements in the union of sets A, B, C, and D. If I use the notation that "a" is the number of elements in set A, "ab" is the number of elements in the intersection of sets A and B, ..., and "abcd" is the number of elements in the intersection of sets A, B, C, and D, then the number of elements in the union of sets A, B, C, and D is (a+b+c+d) - (ab+ac+ad+bc+bd+cd) + (abc+abd+acd+bcd) - (abcd) (*) Then the number of fractions with denominator "n" that can NOT be reduced is the total number of numerators less than n (i.e., n-1), minus the number given by the preceding equation (*). So we have the following for the number of irreducible fractions with denominator n: (n-1) - [(a+b+c+d) - (ab+ac+ad+bc+bd+cd) + (abc+abd+acd+bcd) - (abcd)] or (n-1) - (a+b+c+d) + (ab+ac+ad+bc+bd+cd) - (abc+abd+acd+bcd) + (abcd) Here, in words, is a description of this method (following this description, I will show several examples). Number of irreducible fractions with denominator n = (number of numerators less than n) - (number of numerators less than n that are divisible by some prime factor of n) + (number of numerators less than n that are divisible by two different prime factors of n) - (number of numerators less than n that are divisible by three different prime factors of n) + (number of numerators less than n that are divisible by four different prime factors of n) ... and, in the general case, there may be more terms to be added or subtracted, depending on the number of different prime factors in the prime factorization of the denominator.... Here are some examples... n = 51: prime factorization is 51 = 3*17 The number of numerators less than 51 is 51-1 = 50 The number of numerators less than 51 and divisible by 3 is (51/3)-1 = 16 The number of numerators less than 51 and divisible by 17 is (51/17)-1 = 2 The number of irreducible fractions with denominator 51 is (50) - (16+2) = 50-18 = 32 n = 52: prime factorization is 52 = 2*2*13 The number of numerators less than 52 is 52-1 = 51 The number of numerators less than 52 and divisible by 2 is (52/2)-1 = 25 The number of numerators less than 52 and divisible by 13 is (52/13)-1 = 3 The number of numerators less than 52 and divisible by both 2 and 13 is (52/26)-1 = 1 The number of irreducible fractions with denominator 52 is (51) - (25+3) + (1) = 51-28+1 = 24 n = 53: 53 is prime; all 52 numbers less than 53 are relatively prime to 53; the number of irreducible fractions with denominator 53 is 52. n = 54: prime factorization is 2*3*3*3 The number of numerators less than 54 is 54-1 = 53 The number of numerators less than 54 and divisible by 2 is (54/2)-1 = 26 The number of numerators less than 54 and divisible by 3 is (54/3)- 1= 17 The number of numerators less than 54 and divisible by both 2 and 3 is (54/6)-1 = 8 The number of irreducible fractions with denominator 54 is (53) - (26+17) + (8) = 53-43+8 = 18 There are only a few denominators less than 100 where the prime factorization contains enough factors to make the process more complicated than the examples above. Here is one of them... n = 60: prime factorization is 2*2*3*5 The number of numerators less than 60 is 60-1 = 59 The number of numerators less than 60 and divisible by 2 is (60/2)-1 = 29 The number of numerators less than 60 and divisible by 3 is (60/3)-1 = 19 The number of numerators less than 60 and divisible by 5 is (60/5)-1 = 11 The number of numerators less than 60 and divisible by both 2 and 3 is (60/6)-1 = 9 The number of numerators less than 60 and divisible by both 2 and 5 is (60/10)-1 = 5 The number of numerators less than 60 and divisible by both 3 and 5 is (60/15)-1 = 3 The number of numerators less than 60 and divisible by 2, 3, and 5 is (60/30)-1 = 1 The number of irreducible fractions with denominator 60 is (59) - (29+19+11) + (9+5+3) - (1) = 59-59+17-1 = 16 Thanks for sending us this problem. I got a lot of good mental exercise from it. Please write back if you have further questions on this problem. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/