Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Rational-generating functions

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

(1) Let

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

(2) Take the difference nm. 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 I’ve been trying to solve. If I can solve this, I’ll have solved the other problem. dizzy

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


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

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

ganesh
Moderator
Registered: 2005-06-28
Posts: 12,962

Re: Rational-generating functions

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?


Character is who you are when no one is looking.

Offline

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

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Rational-generating functions

That’s correct. But the algorithm is supposed to work for ALL

. Can you prove that? smile

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


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

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

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Rational-generating functions

Okay, let’s take another example, say


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

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

ganesh
Moderator
Registered: 2005-06-28
Posts: 12,962

Re: Rational-generating functions

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


Character is who you are when no one is looking.

Offline

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

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: Rational-generating functions

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

Offline

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

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Rational-generating functions

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

Identity wrote:

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

Thanks. smile


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

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

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: Rational-generating functions

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)

Offline

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

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Rational-generating functions

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

tongue


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

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

Identity
Member
Registered: 2007-04-18
Posts: 934

Re: Rational-generating functions

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

Offline

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

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Rational-generating functions

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.


Why did the vector cross the road?
It wanted to be normal.

Offline

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

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Rational-generating functions

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.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

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

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Rational-generating functions

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)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.

Offline

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

TheDude
Member
Registered: 2007-10-23
Posts: 361

Re: Rational-generating functions

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.


Wrap it in bacon

Offline

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

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,908

Re: Rational-generating functions

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.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

Board footer

Powered by FluxBB