Maths Query

[Karless]

Unclewolve's qn:

 

"Then the conjecture is: iterates of f(x) will eventually reach 1 for any

initial value of x.

 

Can you prove the conjecture?"

 

 

My understanding of iterates is like taking limit for the function(calculus). If my interpretation of the question is correct, then wat u wrote aint answering the qn.

 

 

Anyway, very well explanation to show us even divide by 2 will be even positive integer. And oso (odd + 1)/2 will be positive integer too. Just dunno how it is answering the question at the moment.

[Sosaria]

I figure iteration is a more simple process, but more time-consuming, than calculus. Normally best done by computer. But repeating the iteration, even millions of times, doesn't exactly prove anything.

 

So taking the two functions defined earlier:

f(x) = x/2 if x is even

f(x) = (3*x+1)/2 if x is odd

 

Let's choose any value of x, say, x=10.

 

x=10 is even so we use f(10)=10/2=5

 

5 is odd, so for the next iteration, we stuff this into f(5)=(3*5+1)/2=8.

 

8 is even, so back to f(8)=4/2=2, and so on...

 

This is the method of iteration. Supposedly, we have to prove that doing this many, many times, no matter what the initial value of x chosen, f(x) values will eventually converge to 1.

 

Maybe someone can quickly program this to see if it's true. Proving it is another matter, of course.

[Applecow]

ok this is one weird thread. I don't even know why I'm reading it.

[Poper]

Just want be with the crowd - NOT AGAIN!!!!!!

[Porker]

  Quote

Hey while we are at it..i have a problem...hope any math major can help.

 

It's called the 3X + 1 problem.

 

Let f(x) be a function defined on the positive integers such that:

 

f(x) = x/2 if x is even

f(x) = (3*x+1)/2 if x is odd

 

Then the conjecture is: iterates of f(x) will eventually reach 1 for any

initial value of x.

 

Can you prove the conjecture?

 

Logan,

 

You plot the two functions on a graph with x as the horizontal axis and f(x) as the vertical axis to find the shape. Beri simple one...

 

The conclusion is neither will reach 1 for any initial value of x.

 

x/2 for even numbers will only become larger as the x increases so it tends away from 1.

 

Same goes for the other function.

 

Sorry if I misunderstood your question. I from ah beng skool so more inclined to sharp combs and wearing US Master skool shoes

[T_k_w]

okay I wrote a xls file to plot the iterative function, pls note you have to see the graph as a iterative function and not as a normal y vs x graph, i have no time to analyse the graph now, maybe tonight after work.

 

for the curious, the plot function i wrote will find return 1 value of f(x) for 1 single value of x.

uncle wolf.xlsFetching info...

Edited January 25, 2008 by T_k_w

[Typhoonz]

The world's a better place without all these confusing mathematical things...

Edited January 25, 2008 by Typhoonz

[Redwood]

Why the questions you asked is so difficult one.

I long gave up on mathematics liao. Why? Because nothing to look forward to as,

1. Leonard Euler is dead so no one to compete.

2. Fermat Last Theorem has been proven by Andrew Wile.

3. Riemann hypothesis is too difficult to be solved in the next hundred years.

Edited January 25, 2008 by Redwood

[Redwood]

Proof:

 

1. Let Y be an integer. There can only be 2 cases for Y.

Y = 2^n (meaning Y is a multiple of 2) OR

Y = (2^m)*b where b is odd

 

2. To reduce any number to 1, requires f(x)=x/2 and not g(x)=(3*x+1)/2.

Why? Using g(x) implies that x = 1/3 contradicts x to be at least 1.

 

3. Using point 1 & 2, we only need to show that there exists an integer n such that both the function f(x) and g(x) can be written as (2^n) - where x is an integer - at some point of time during the iterations.

 

Thus, for

4. f(x) = x/2 = (2^n), implies, x = 2^(n+1) (n can be any integer to make x an integer)

5. g(x)=(3*x+1)/2 = (2^n), implies, x = [2^(n+1) - 1]/3

To make x integer, n = 2a+1 where a are integers >=0.

 

 

Q.E.D

Edited January 25, 2008 by Redwood

[Redwood]

Bro, spreadsheet is good to see patterns to generate ideas but not for mathematics proof.

 

Extracted from Wikipedia:

 

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true, within the accepted standards of the field. A proof is a logical argument, not an empirical one. That is, the proof must demonstrate that a proposition is true in all cases to which it applies, without a single exception. An unproven proposition believed or strongly suspected to be true is known as a conjecture.

[T_k_w]

yo, 2^n is not a multiple of 2. let me give you a contradiction, 2^n=10, find n.

:)

 

normally we define even number as (2*n) and odd number as (2*n+1) for all integer values of n.

 

your point 2 also abit fei, because we already know x are +ve integers and we know that the purpose of g(x)=(3*x+1)/2 is to change +ve odd integer to a +ve even integer and not for reducing +ve odd integer to 1.

 

so following your line of reasoning:

3. Using point 1 & 2, we only need to show that there exists an integer n such that both the function f(x) and g(x) can be written as (2*n) - where x is a +ve integer - at some point of time during the iterations.

 

Thus, for

4. f(x) = x/2 = (2*n), implies, x = 2*(n+1) (for all +ve integer values of n)

5. g(x)=(3*x+1)/2 = (2*n), implies, x = (2*n+1)/3.

 

Now, here is the problem, x = (2*n+1)/3, i can show that x is not always an integer for all possible +ve integer value of n, so how? let me know if you can sort this out.

[T_k_w]

Iterative functions are a particular breed of functions, there are several methods of proving iterative functions, that I came across when i was tutoring maths c students when teaching the newton-raphson topic, i recall that if we do fixed point iteration, must prove by drawing graph or something.

 

You read up on this here => http://math.fullerton.edu/mathews/n2003/FixedPointMod.html or google("proof for iterative functions");

 

I did not have time to read up, as I only have 10 mins this morning and someone requested to plot the function out so I just wrote the thing out to plot in excel lar.

[Redwood]

Yo,

 

Point 1:

you're correct to point out the mistake "Y is a multiple of 2". I should have wrote Y has 2 as the sole prime factor.

 

For point 1, what i'm saying is this, given any number we can always re-write it as either (2^n) or (2^m)*b. I give a few example,

8 = 2^3

10 = (2^1)*5

100 = (2^2)*25

Prime = (2^0)*Prime

Odd = (2^0)*Odd

 

Point 2:

I'm trying to explain that in order to end the iteration, f(x)=x/2 has to be used and not g(x)=(3x+1)/2. Thus giving the idea that at any step of the iteration, once the number can be re-written as (2^n) then we can always used f(x)=x/2 totally to reduce to the integer 1.

 

Point 3,4,5:

I'm saying that f(x) and g(x) can be written as (2^n) eventually if you do enough iterations which further implied that it can be reduce to 1 by using f(x) alone.

 

Using spreadsheet you can see the pattern and that will help you devise a proof. Observation from spreadsheet: At any iteration step, if the number can written as (2^n), the problem is considered solved.

 

I should clarify that the proof that i wrote is an informal one. I have not touch number theory since uni. days. If you have any ideas or alternative argument, pls share.

[Redwood]

For C maths student, most of the methods used can be found in any texts on numerical methods. To see mathematical proof, you have to look for numerical analysis.

 

In pure mathematics, proof cannot be done by any simulation to exhaust the possibilities. I only know of one theorem that does that, "Four Color Theorem".

[T_k_w]

you are right, just now i opened the spreadsheet to take a look.

 

I also noticed that if iterate until 2^n will always lead to endgame.

 

and so far i manually traced the 1st 20 values of x and they lead to endgame, and by doing so, it leads to more values of x to be proven true. Think uncle wolfy has thrown us a tricky question.

 

in your previous previous post, you prove that g(x)=(3x+1)/2 can achieve some 2^m for some value of x, also f(x)=x/2 can achieve some 2^n for some values of x, but not exhaustive enough i think...

[T_k_w]

Ya, I hate it when i know something is "correct" but cannot proof it.

 

But there is limit to my knowledge, only hope future generations can be better than what i know now.

 

Sometimes i feel hopeless for the young ones, they are not pushing (their personal) boundaries(in maths).

[Redwood]

in your previous previous post, you prove that g(x)=(3x+1)/2 can

achieve some 2^m for some value of x, also f(x)=x/2 can achieve some 2^n for

some values of x, but not exhaustive enough i think...

 

The expression already exhausted all case,

Assume now happen that after certain iterations, the number becomes,

say Y = (2^m)*b where b is odd. Using f(x)=x/2 will farther reduce to Y=b, b odd.

Substitute b in g(x), we get g(b)=(3*b+1)/2.

 

My point 5, says that b can be written as b = [2^(n+1)-1]/3 and to make b an integer,

n must be equal to 2a+1, where a are integers >=0.

So now n=2a+1 and g(b)=(3*b+1)/2 = (2^n). With a>=0, will already exhaust all the

cases for odd integers n, thus you have a list of n=1,3,5,7,9,...

for each a=0,1,2,3,4,... respectively.

 

All this odd n=1,3,5,7,9... can generate a list of set W=(2^n)={2,8,32,128,512,...} so that whenever g(b) fall into the set W we can have a endgame.

What if g(b) does not fall in the set W? Then we have to re-write g(b)=(2^m)*h for some m and h and the cycle repeats, trying to use set W to catch g(h).

 

You may ask that there are holes in the set W, i.e.

where are the set U={4,16,64,256,...}. Will substituting x in g(x) be equal to any value in the set U? This is statement to be proof! I do not have any idea to proof it yet.

Edited January 25, 2008 by Redwood

[Redwood]

Can you post your brilliant proof to enlighten us?