Counting problem

Originally posted by royalchicken
Yes 😀!

I was going to write a proof, first that each natural number yields exactly one rational (trivial) and then that the reverse is true (a little harder).

It's more interesting to look at each little bit and see how it fits together, because your function is remarkably constructive--intelligent design I'd say.

Yes, it's a function of the Lego school; I think it's fairly obvious what I'm trying to do at each step. I'd be intrigued to know how your sequence works, though.

First, we'll prove that for any relatively prime a and b, there exists some n such that x(n) = a and x(n+1) = b. We'll do so by induction on a+b.

If a+b = 2 then a = b = 1 = x(0) = x(1).

Suppose a+b = k and a > b. Also suppose b = x(n+1), a-b = x(n).

Thus x(2n+2) = a, x(2n+2+1) = b

Now do the same for b > a. This proves that every rational appears in the sequence. This does not guarantee, for example, that 2/4 doesn't show up, because we haven't shown that every pair x(n), x(n+1) is a pair of coprimes.

Next we show that gcd(x(2n+1), x(2n+2)) = 1 for all n. This is true when n = 0. Now suppose it's true for all k such that 0=<k<=n for some n. By the definition of x, x(2n+3) and x(2n+4) only share a factor if x(n+1) and x(n+2) do. Our induction hypothesis is that x(2k+1) and x(2k+2) are coprime for all k in [0,n], so x(2(n/2) + 1) and x(2(n/2)+2) are coprime, and thus x(2n+3) and x(2n+4) are.

Now we know that all positive rationals appear in this sequence and that they are all in lowest terms. To show it's a bijection, we just need to show that if x(n) = x(m) then x(n+1) \= x(m+1) unless m = n. Suppose the opposite. Then x(m)x(n+1) = x(n)x(m+1). Since x(n+1) and x(n) are coprime, an since LHS and RHS must have the same prime factorization, we must have x(m) = x(n) and x(m+1) = x(n+1).

Thus the sequence contains every rational number exactly once, and every integer clearly generates a rational, so it's a bijection.

That doesn't really explain how it works so much as that it works 😳.

I thought of it like this, which is sort of equivalent to my simple Twenty Questions strategy (the one that bbarr played with like a degrading fascist wolf 😉):

Just picture a graph which branches in two directions, with 1 at the top and m/(n+m) and (m+n)/m coming out of m/n.

I spent a great deal of time on your ''spiral/zigzag'' idea, but I couldn't make an explicit function.

In the last bit, I forgot to include the detail that x(m) and x(m+1) are also coprime.

Originally posted by Acolyte
I don't, but I can try to reconstruct it. Going from N to Q:

1 -> 0

For other numbers:
n even -> n/2
n odd -> -(n-1)/2
and then factorise the result into primes.
Now we change the power x of each prime in this factorisation as f ...[text shortened]... xample: 97 -> -48 -> -2^4*3 -> -2^2*3^-1 = -4/3

Does this work?

It seems to work fine for N to Q mapping. But it is not clear , how in this scheme you go about the Q to N mapping. Can you give some more details? The most difficult part is the proof of bijection. Is it not possible that two different natural numbers would yield the same rational?

Originally posted by sarathian
It seems to work fine for N to Q mapping. But it is not clear , how in this scheme you go about the Q to N mapping. Can you give some more details? The most difficult part is the proof of bijection. Is it not possible that two different natural numbers would yield the same rational?

The key assumption I make is that of unique factorisation, ie that each natural number has exactly one factorisation into primes, and that something similar works for rationals (which is fairly obvious given that the naturals are an Euclidean domain). If you believe that, the rest is easily reversible.

Originally posted by Acolyte
The key assumption I make is that of unique factorisation, ie that each natural number has exactly one factorisation into primes, and that something similar works for rationals (which is fairly obvious given that the naturals are an Euclidean domain). If you believe that, the rest is easily reversible.

I am not very familiar with Euclidian domains. But can you give an example? For example, on what natural numbers will the rationals, 8/81, -8/81, 81/8, and - 81/8 map to?

Originally posted by sarathian
I am not very familiar with Euclidian domains. But can you give an example? For example, on what natural numbers will the rationals, 8/81, -8/81, 81/8, and - 81/8 map to?

8/81 = 2^3*3^-4 -> 2^6*3^7 -> 2*2^6*3^7 = 279936

-8/81 -> 279937

81/8 = 2^-3*3^4 -> 2^5*3^8 -> 2*2^5*3^8 = 419904

-81/8 -> 419905

Where N -> Q has the even/odd split, Q -> N splits on positive/negative.

Originally posted by Acolyte
8/81 = 2^3*3^-4 -> 2^6*3^7 -> 2*2^6*3^7 = 279936

-8/81 -> 279937

81/8 = 2^-3*3^4 -> 2^5*3^8 -> 2*2^5*3^8 = 419904

-81/8 -> 419905

Where N -> Q has the even/odd split, Q -> N splits on positive/negative.

Wow , that's a really beautiful ,and really very simple bijection indeed. You can indeed find the rational corresponding to any arbitrarily chosen natural number , and vice versa.

Originally posted by sarathian
Wow , that's a really beautiful ,and really very simple bijection indeed. You can indeed find the rational corresponding to any arbitrarily chosen natural number , and vice versa.

Both the mappings ( due to Acolyte as well as that due to Royalchicken) are bijections . But Acolytes' mapping is simple & beautiful and works bothways quite simply and directly without much hassles.