Rational-generating functions

JaneFairfax · 2007-12-25 10:00:31

This is an interesting problem I ran into while trying to solve another problem.

(1) Let

, where m < n and gcd(m,n) = 1, be a rational number between 0 and 1.

(2) Take the difference n−m. If

, let , otherwise let .

(3) Repeat step (2) with

. The thing is

Conjecture: After only FINITELY many steps involving the procedure above, you will always arrive at the number

, no matter what you started out with.

True or false? I need help with this.

This is part of another problem Ive been trying to solve. If I can solve this, Ill have solved the other problem.

Last edited by JaneFairfax (2007-12-25 21:55:05)

Jai Ganesh · 2007-12-25 17:42:30

Let m=4, n=7, m/n=4/7.
m'/n'=3/7.
Now n'-m'=4>m'
Therefore,
m/(n-m) = 3/4=m''/n''
n''-m''=1<m''
Therefore,
(n-m)/m=1/3=m'''/n'''.
n'''-m'''=2>m'''
Therefore,
(n-m)/m=2/1=m''''/n''''

Have I made some mistake?

JaneFairfax · 2007-12-25 21:52:39

Thats correct. But the algorithm is supposed to work for ALL

. Can you prove that?

Last edited by JaneFairfax (2007-12-25 21:53:13)

JaneFairfax · 2007-12-25 22:11:12

Okay, lets take another example, say

Jai Ganesh · 2007-12-26 02:26:21

To begin with, m and n are co-primes. Since m/n<1 and m/n is a rational number, m and n are natural numbers (assuming we are talking about non-zero positive integers only).
The difference between m and n is diminished in each step of the algorithm or n=x times m and x is being diminshed in each step of the algorithm.
The final result : The inevitable : The least possible difference between n and m is 1, and x=2 where n= x times m, because x got to be a natural number and the lease number for unequal m and n is n=2.
However, proving the algorithm leads to 1/2 whatever values of m and n we start with, under the given conditions, is quite difficult (for me!).

Identity · 2007-12-26 03:14:14

I'll program this on my calculator and see if I can do a proof by exhaustion.

JaneFairfax · 2007-12-26 03:32:09

ganesh wrote:

To begin with, m and n are co-primes. Since m/n<1 and m/n is a rational number, m and n are natural numbers (assuming we are talking about non-zero positive integers only).
The difference between m and n is diminished in each step of the algorithm or n=x times m and x is being diminshed in each step of the algorithm.
The final result : The inevitable : The least possible difference between n and m is 1, and x=2 where n= x times m, because x got to be a natural number and the lease number for unequal m and n is n=2.
However, proving the algorithm leads to 1/2 whatever values of m and n we start with, under the given conditions, is quite difficult (for me!).

Yes, but I need a rigorous formal proof.

Identity wrote:

I'll program this on my calculator and see if I can do a proof by exhaustion.

Thanks.

Identity · 2007-12-26 03:53:32

I've done a lot of tests so far, and in all of them, even if gcd(m,n) =/= 1, I still end up with 1/2.

So far the only restrictions I think there need to be are that m and n are positive and m<n.

Input "Numerator", m
Input "Denominator", n
While m/n ≠ 1/2
If n-m<m Then
n-m->m
n-m->n
Else
n-m->n
EndIf
EndWhile
Disp "Fraction is", m/n

Of course, I was joking about 'proof by exhaustion'... but hopefully this makes you feel more confident that this is TRUE

Last edited by Identity (2007-12-26 04:02:31)

luca-deltodesco · 2007-12-26 04:31:51

a similar thing.

Start with any word, and replace it by the word for how many letters there were, repeat you already end with 'four'

example:

hydrochloride : 13
thirteen : 8
eight : 5
five : 4
four

Identity · 2007-12-26 05:10:42

Yeah but that settles down to four. With this algorithm it passes by 1/2 then goes off into oblivion and division by zero.

mathsyperson · 2007-12-26 07:47:48

No it doesn't.
For 1/2, m=1 and n=2. Then, n-m=1. n-m<n is false and so we take m'/n' to be m/(n-m) = 1/1 = 1.
Doing that again gets to 0/1, and it stays there.

Anyway, judging by Jane's 23/51 example, it looks like the numerator and denominator for each step are being generated by an inefficient version of Euclid's algorithm.
Euclid's algorithm is designed to find the HCF of two numbers, and so since hcf(m,n) is defined to be 1, it follows that iterating this process a sufficient amount of times will get the result 1/k, for some k≥2.

If k is 2 then we're happy, and if it's not we take another step and produce 1/(k-1).
From here, each step just keeps knocking down the denominator until it reaches 2.

Ricky · 2007-12-26 08:53:55

Good observation mathsyperson. Always remember, start with easy and then generalize. What holds in the general case must hold in special cases, so look at special cases and see what happens.

If m = 1, n is any natural number, then the algorithm holds trivially.
If m = n-1, then the algorithm holds by in one step since it reduces to the 1/(n-1) case above.

My next move was to start working with just primes.

2/3 => 1/2
2/5 => 2/3
2/7 => 2/5
2/11 => 2/9 => 2/7

And now it should be clear. Given m and n, we may immediately say that:

m' = m
n' = n (mod m) + m

This is what the right path (second case from the inequality) means. Now we are forced to go by the left path since:

n (mod m) + m - m = n (mod m) < m

So this gives us n (mod m) / m. Now we repeat the process, and what we want to show is that n (mod m) is eventually 1.

JaneFairfax · 2007-12-26 21:16:30

I should have added that when you reach 1⁄2, you stop. 1⁄2 is supposed to be the last number in the iterating sequence. So, starting with ANY positive rational number less than 1 in its lowest terms, can you, after finitely many iterations, ALWAYS come down to 1⁄2?

Last edited by JaneFairfax (2007-12-26 21:23:01)

TheDude · 2007-12-27 05:08:59

I'm not sure if this is rigorous enough for you, but here's my shot at it.

Our first observation is that we can't get stuck in a cycle (unlike the Collatz conjecture). This is due to the fact that our denominator n is always decreasing, as it is always set to either m (which is less than n) or to n - m, which is also less than n. We also know that m never increases (as it is either set to m or n - m, whichever is less) and must stay less than n, so we know that over (finite) time it will decrease.

Since we can never get stuck in a repeating cycle the only way that we won't reach 1/2 is if m' = 0 or m' = n'. Note that in order for m' to reach 0 we would need m = n in the previous step, so we need only consider this mode of failure.

Now, in order to reach m' = n', we need 2m = n in the previous step. This is equivalent to saying that our previous fraction was m/2m. This fact is easy to show, as no matter which direction we go from the previous step, in order for m' = n' we find that n - m = m -> n = 2m.

Now, it gets a little messy from here. What I'm going to try to show is that if an' = bm', a<b and a and b are positive coprime integers, then there exist positive coprime integers c and d, c<d, where cn = dm. If this is the case, then n and m cannot be coprime, and we'll never reach a point by going backwards where n and m can be coprime. Since they must be coprime when we start we know that we can never reach the point where m = n.

This all tells us that to get to an' = bm' we need either an = (a+b)m or bn = (a+b)m. Since both a and b are coprime to and less than a+b, let c = a or b and d = a+b, and we have our two new coprime multiples.

Finally, we need to show that if a<b are coprime integers and an = bm implies that m and n are not coprime (likely, there is already a named theorem that shows this, but I don't know of one so I'll prove it for the sake of completeness). From an = bm we find that a = m * (b/n). Since a and b are coprime, every prime factor of b must be present in n to be eliminated. If n has more prime factors than are required to eliminate b, then they must also be present in m, since a is an integer. This would mean that m and n are not coprime. However, if n has only the exact same prime factors as b, then n = b. This would further imply that m = a. However, this is no possible, as m<n but a<b. This means that m and n must share prime factors.

Finally, as stated above, no matter how far back we trace we can never find an instance where m and n are not coprime. Thus, every fraction where m and n are coprime will eventually reach 1/2. The only way this isn't true is if there is a failure mechanism other than a repeating cycle or m = n, which have been shown to be impossible.

krassi_holmz · 2008-08-22 11:37:20

Here's some nice way to visualise the process: you start with 2 sticks (lengths m,n), you put them one over the other with 1 common end, and you cut at the other end. Then remove one of the same sticks, which you just made, and continue. It's intuitial that you'll eventually end with 2 identical sticks, unless the initial lengths dont' have gcd (if you start with sticks with length 1 and pi for example, the process won't stop but will converge). This thing looks like the Ecld gcd. Formally, at each step the difference between the lengths of the sticks strictly decreases (which is not obvious using rationals, because they give us the relative difference between the two sticks - the numerator and denominator). The last thing is that just before the sticks become with same length, the one is twice the other.

Math Is Fun Forum

#1 2007-12-25 10:00:31

Rational-generating functions

#2 2007-12-25 17:42:30

Re: Rational-generating functions

#3 2007-12-25 21:52:39

Re: Rational-generating functions

#4 2007-12-25 22:11:12

Re: Rational-generating functions

#5 2007-12-26 02:26:21

Re: Rational-generating functions

#6 2007-12-26 03:14:14

Re: Rational-generating functions

#7 2007-12-26 03:32:09

Re: Rational-generating functions

#8 2007-12-26 03:53:32

Re: Rational-generating functions

#9 2007-12-26 04:31:51

Re: Rational-generating functions

#10 2007-12-26 05:10:42

Re: Rational-generating functions

#11 2007-12-26 07:47:48

Re: Rational-generating functions

#12 2007-12-26 08:53:55

Re: Rational-generating functions

#13 2007-12-26 21:16:30

Re: Rational-generating functions

#14 2007-12-27 05:08:59

Re: Rational-generating functions

#15 2008-08-22 11:37:20

Re: Rational-generating functions

Board footer