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

You are not logged in. #1 20071226 09:00:31
Rationalgenerating functionsThis is an interesting problem I ran into while trying to solve another problem. (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 I’ve been trying to solve. If I can solve this, I’ll have solved the other problem. Last edited by JaneFairfax (20071226 20:55:05) #2 20071226 16:42:30
Re: Rationalgenerating functionsLet m=4, n=7, m/n=4/7. Character is who you are when no one is looking. #3 20071226 20:52:39
Re: Rationalgenerating functionsThat’s correct. But the algorithm is supposed to work for ALL . Can you prove that?Last edited by JaneFairfax (20071226 20:53:13) #4 20071226 21:11:12
Re: Rationalgenerating functionsOkay, let’s take another example, say #5 20071227 01:26:21
Re: Rationalgenerating functionsTo begin with, m and n are coprimes. Since m/n<1 and m/n is a rational number, m and n are natural numbers (assuming we are talking about nonzero positive integers only). Character is who you are when no one is looking. #6 20071227 02:14:14
Re: Rationalgenerating functionsI'll program this on my calculator and see if I can do a proof by exhaustion. #7 20071227 02:32:09
Re: Rationalgenerating functions
Yes, but I need a rigorous formal proof.
Thanks. #8 20071227 02:53:32
Re: Rationalgenerating functionsI'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. Code:Input "Numerator", m Input "Denominator", n While m/n ≠ 1/2 If nm<m Then nm>m nm>n Else nm>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 (20071227 03:02:31) #9 20071227 03:31:51
Re: Rationalgenerating functionsa similar thing. The Beginning Of All Things To End. The End Of All Things To Come. #10 20071227 04:10:42
Re: Rationalgenerating functionsYeah but that settles down to four. With this algorithm it passes by 1/2 then goes off into oblivion and division by zero. #11 20071227 06:47:48
Re: Rationalgenerating functionsNo it doesn't. Why did the vector cross the road? It wanted to be normal. #12 20071227 07:53:55
Re: Rationalgenerating functionsGood 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. "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..." #13 20071227 20:16:30
Re: Rationalgenerating functionsI 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 (20071227 20:23:01) #14 20071228 04:08:59
Re: Rationalgenerating functionsI'm not sure if this is rigorous enough for you, but here's my shot at it. 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 #15 20080823 09:37:20
Re: Rationalgenerating functionsHere'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. 