Kind of an interesting one....

S(d*2^a) = S(d)/2, of course, provided d is odd. Maybe I mentioned, maybe not. If d is even, say d=2, then S(d) = N/2. But S(4) = N/2 as well. Just to clarify.

But unfortunately seeing as there is no possible way of randomly selecting a rational number the original question made no sense...

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.

Originally posted by royalchicken
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.

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 even worse, you compare an odd k with an infinite mumber of rationals which each 'makes' half as many rationals as k.

Originally posted by Fiathahel
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.

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 = 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.

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.

Originally posted by royalchicken
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.

What was wrong with my proof anyway, if we are quibbling about proofs? I can restate it a bit more clearly if you like...

Originally posted by royalchicken
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.

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?

Originally posted by Fiathahel
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?

lim 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:

Ko = lim (N->inf) [S(1) + S(3) + S(5) + ... + S(2n+1) + ....]/[S(2) + S(4) + ... + s(2n)+...]

=2. This proves it.

Originally posted by iamatiger
What was wrong with my proof anyway, if we are quibbling about proofs? I can restate it a bit more clearly if you like...

I'd like to see a restatement, because I think it's good.

Originally posted by royalchicken
I'd like to see a restatement, because I think it's good.

Thanks for the encouragement!

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

Looks good sir. I don't see any major problems right off. Nice going 😀!

Originally posted by royalchicken
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.

Now 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?

Originally posted by iamatiger
Thanks for the encouragement!

......

Therefore the probability that a random rational number will have an even divisor is also 1/3

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 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.

Originally posted by Fiathahel
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.

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.

Originally posted by iamatiger
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.

sorry, my fault. The construction methode works a bit different then I thought.