02 Sep 03
Uhm, I meant "probability" in the sense of "what percentage of rational numbers have even denominators" or "what is the density of the even-denominator rationals in the rationals". This type of question is at the root of huge amounts of number theory, for example the famous Prime Number Theorem asserts weakly that the probability of choosing a prime randomly out of all integers is 0, and that out of the first N integers is 1/log N.
These questions just involve taking a limit, that's all.
03 Sep 03
Originally posted by royalchickenSorry, but I'm still not convinced.
THe answer is 1/3. Good going iamatiger!
Here's my proof. Let S(d) be the number of rationals in (0,N] with denominator d for some integer N.
Clearly, we are counting pairs (m,d) such that gcd(m,d)=1. If d is prime, then:
S(d) = N(1-1/d)
If d has k distinct prime factors, then:
S(d) = N(1-1/p1 - 1/p2 - ...-1/pk + 1/p1p2+...+1/p1p2p3p4 ...[text shortened]... t being even guarantees the presence of a prime factor, 2, while being odd guarantees nothing.
You said:
'Thus if d is odd, then for all a, S(d*2^a) = S(d)/2.'
This is true of course, but then you compare an odd k with 2k. and thus also {1,3,5,7,9,11} with {2,6,10,14,18,22} and conclude that the second set 'makes' half as many rationals as the first. While you want to look at {1,2,3,...,11,12}. Or even worse, you compare an odd k with an infinite mumber of rationals which each 'makes' half as many rationals as k.
03 Sep 03
Originally posted by FiathahelNo, Fiathahel. All I proved is that IN ANY FINITE INTERVAL (for any finite maximum denominator), S(d) = 2S(2d) for odd d. S(d) counts the number of rationals of denominator d with a numerator less than or equal to N. For example, let d = 3 and N = 5. Then we can use the set of rationals {1/3, 2/3, 4/3, 5/3}. Thus S(3) = 4 in this case. Now for 2d = 6, we can have {1/6, 5/6}, so S(6) = S(3)/2. In general, as was shown, for any integer N and odd denominator d, there are twice as many rationals with numerator at most N with denom. d as there are for denom. 2d. Your argument doesn't apply here, since the second set allows larger numerators than the first.
Sorry, but I'm still not convinced.
You said:
'Thus if d is odd, then for all a, S(d*2^a) = S(d)/2.'
This is true of course, but then you compare an odd k with 2k. and thus also {1,3,5,7,9,11} with {2,6,10,14,18,22} and conclude that the second set 'makes' half as many rationals as the first. While you want to look at {1,2,3,...,11,12}. Or eve ...[text shortened]... with an infinite mumber of rationals which each 'makes' half as many rationals as k.
In any case, a google search yields the following:
http://www.inwap.com/pdp10/hbaker/hakmem/number.html
it does not give a proof, but does give the same result.
- Joined
- 26 Apr 03
- Moves
- 26771
03 Sep 03
Originally posted by royalchickenWhat was wrong with my proof anyway, if we are quibbling about proofs? I can restate it a bit more clearly if you like...
No, Fiathahel. All I proved is that IN ANY FINITE INTERVAL (for any finite maximum denominator), S(d) = 2S(2d) for odd d. S(d) counts the number of rationals of denominator d with a numerator less than or equal to N. For example, let d = 3 and N = 5. Then we can use the set of rationals {1/3, 2/3, 4/3, 5/3}. Thus S(3) = 4 in this case. Now for 2d ...[text shortened]... com/pdp10/hbaker/hakmem/number.html
it does not give a proof, but does give the same result.
04 Sep 03
Originally posted by royalchickenWhat your prove says is that lim S(1)+S(3)+S(5)+S(7)+...+S(2n+1) = lim 2*[S(2)+S(6)+S(10)+S(14)+...+ S(4n+2)]. And not lim S(1)+S(3)+S(5)+S(7)+... S(2+1n) = 2*[S(2)+S(4)+S(6)+S(8)+S(10)+S(14)+...+S(2n+2)]. Or I'm missing something?
No, Fiathahel. All I proved is that IN ANY FINITE INTERVAL (for any finite maximum denominator), S(d) = 2S(2d) for odd d. S(d) counts the number of rationals of denominator d with a numerator less than or equal to N. For example, let d = 3 and N = 5. Then we can use the set of rationals {1/3, 2/3, 4/3, 5/3}. Thus S(3) = 4 in this case. Now for 2d ...[text shortened]... com/pdp10/hbaker/hakmem/number.html
it does not give a proof, but does give the same result.
04 Sep 03
Originally posted by Fiathahellim S(1)+S(3)+S(5)+S(7)+...+S(2n+1) does not converge. I think that you're forgetting that S is functionally related to TWO numbers, namely the denominator d and the maximum numerator N. My proof merely says that in any interval for which the upper (integral) bound is the maximum numerator in a set of rationals, there are twice as many odd denominator rationals as even denominator rationals. The ratio in question is:
What your prove says is that lim S(1)+S(3)+S(5)+S(7)+...+S(2n+1) = lim 2*[S(2)+S(6)+S(10)+S(14)+...+ S(4n+2)]. And not lim S(1)+S(3)+S(5)+S(7)+... S(2+1n) = 2*[S(2)+S(4)+S(6)+S(8)+S(10)+S(14)+...+S(2n+2)]. Or I'm missing something?
Ko = lim (N->inf) [S(1) + S(3) + S(5) + ... + S(2n+1) + ....]/[S(2) + S(4) + ... + s(2n)+...]
=2. This proves it.
- Joined
- 26 Apr 03
- Moves
- 26771
05 Sep 03
Originally posted by royalchickenThanks for the encouragement!
I'd like to see a restatement, because I think it's good.
Every positive rational number has a unique representation as a fraction m/n with mutually prime integers m and n. Each of m and n has its own prime number decomposition. Let these be
m = p1^a1 p2^a2 ... pr^ar, and n = q1^b1 q2^b2 ... qs^bs,
Form the number K(m/n) = p1^(2a1) p2^(2a2) ... pr^(2ar) q1^(2b1-1) q2^(2b2-1) ... qs^(2bs-1).
K is a function that maps any rational positive number onto a positive integer. A point of note is that K is a 1-1 correspondence.
If we pick a random integer X and generate its corresponding rational number M/N then we have a good method of randomly selecting a rational number (assuming we have a way to choose X!)
From the above, for N to divisible by two, X must contain an odd power of two.
So the probability of choosing an even N rational is the same as the probability of choosing an X which has a highest even divisor that is an odd power of two.
Exactly half of all integers have a highest even divisor 2^0 (i.e they are odd)
Exactly half of the remaining integers have a highest even divisor of 2^1
Exactly half of the remaining integers have a highest even divisor of 2^2
and so on
So the probability that X will have a highest even divisor that is an odd power of two = 1/4 + 1/16 + 1/64 + ... = 1/3
Therefore the probability that a random rational number will have an even divisor is also 1/3
06 Sep 03
Originally posted by royalchickenNow I'm confused. Why not count the number of d-denominator rationals in (0,N]? Also, why not set N=1, if it saves confusion?
Ok, I made a typo, but not exactly the one Fiathahel meant. If S(d) referred to the number of d-denominator rationals in (0,N] as I said, then indeed
S(d) = dN(1-1/p1)....(1-1/pk) as Fiathehel said. However, I meant to say that S(d) counts rationals with NUMERATORS IN (0,N], ie those rationals in (0,N/d] so that the rest is as I said.
S(d) = N(1- ...[text shortened]... h makes S(d) pretty meaningless since we can't make comparisons among different denominators.
06 Sep 03
Originally posted by iamatigerBy making m/n this way, you allow them to be like 4/2 as well as 6/3 while they are the same. But I don't know if that's makes any difference, cause you count all rationals infinite times this way.
Thanks for the encouragement!
......
Therefore the probability that a random rational number will have an even divisor is also 1/3
You can't pick an integer X randomly uniform distributed, but you can apply this proof for X in [0,Q] for all Q. So it is also true for the Q --> inf.
- Joined
- 26 Apr 03
- Moves
- 26771
06 Sep 03
1 edit
Originally posted by FiathahelI thought about that, it would change the odds I think but since m and n are mutually prime each fraction is only counted once. Fractions that are not in their lowest form can by identified by m & n having a common factor that can be divided out - which due to the way m&n are constructed, cannot be the case here.
By making m/n this way, you allow them to be like 4/2 as well as 6/3 while they are the same. But I don't know if that's makes any difference, cause you count all rationals infinite times this way.
You can't pick an integer X random ...[text shortened]... of for X in [0,Q] for all Q. So it is also true for the Q --> inf.
06 Sep 03
Originally posted by iamatigersorry, my fault. The construction methode works a bit different then I thought.
I thought about that, it would change the odds I think but since m and n are mutually prime each fraction is only counted once. Fractions that are not in their lowest form can by identified by m & n having a common factor that can be divided out - which due to the way m&n are constructed, cannot be the case here.