Get famous by figuring even one of these out, some are over 100 years old and unsolved.....
http://mathworld.wolfram.com/UnsolvedProblems.html
http://mathworld.wolfram.com/UnsolvedProblems.html
17 unsolved Math Problems
- Thread starter Ryanwb
- Start date
- Joined
- Jun 5, 2003
- Posts
- 26,989
- Reaction score
- 3,984
oh my head...
Took one look and ran
- Joined
- Aug 19, 2005
- Posts
- 46,247
- Reaction score
- 11,851
great googly moogly
- Joined
- Aug 19, 2005
- Posts
- 46,247
- Reaction score
- 11,851
CardFan67 said:
[crowd] BOOOOOOO [/crowd]
jenna2891
potential get-away driver: go!
- Joined
- Aug 16, 2005
- Posts
- 9,352
- Reaction score
- 4
i sent that link on to my older brother, who is prolly the smartest person i will ever know (although he'd never admit to that). here's his response, which, if you can bring yourself to read the whole thing, is rather interesting. also, he likes to footnote things, so there is one of those, although considering his penchant for it, i'm surprised there is just one.
jenna's too smart older brother said:
CardFan67 said:Jenna's brother's keyboard does not capitalize the beginnings of sentences either... It is a family keyboard problem...
Unless....
There is no brother, Jenna is actually Bobby Joe Keller in prison and the shift keys were broken off over a fight in the prison library over the last copy of "Margaret Thatcher: My Brief Moment".
He found this site after the craze in prison dating sites were posted on here about a year ago
For Collatz, The gist of the "solution" is that the (3x+1) Conjecture is not a Theorem within the whole number system, at all. Instead, it's just a Statistical Property, which has a multitude of mappings, even within the real numbers, that is: outside the integers.
Maybe this is all that has to be said about the infamous Conjecture: that it is not very interesting, in the end. Herewith I mean that its contribution to Number Theory may be of NULL value. But Probability Theory is another story. probably ;-) Yes, I think the major hurdle to be taken is the idea: that the Theory of Probability can yet be used as a proper description, of processes which are quite Deterministic in nature ! (Meanwhile claiming that I am Not the first one who says this)
*) Sample of Pure Applicable Mathematics
Modified definition
To begin with, the definition of the problem (by Eric Roosendaal) will be modified slightly, as follows:
For any positive integer N a sequence Si can be defined
by putting
S0 = N
and for all i > 0:
Si = Si-1 / 2 if Si-1 is even
Si = (Si-1 * 3 + 1) / 2 if Si-1 is odd
Division by 2 in the 'odd' case eliminates the fact that any subsequent value in the sequence is necessarily an even number and hence eliminates trivial 'even' steps.
Statistical Approach
Suppose that the number N is completely arbitrary, essentially meaning that it is not known. Now consider an arbitrary large set of subsequent natural numbers, for example the collection:
1 2 3 4 5 6 7 ... 132 133 134 ... 123421412
And suppose the number N is in such a set, called S . If the number of elements in S is T, then there are two possibilities:
If T = even then the number of even integers in S is T/2
and the number of odd integers in S is T/2
If T = odd then the number of even integers in S is (T-1)/2
and the number of odd integers in S is (T+1)/2
Now suppose that the number of elements in S is very large. Then we may define the probability P that an integer N in S will be even or odd:
If T = even then P(even) = (T/2) / T = 1/2
and P(odd) = (T/2) / T = 1/2
If T = odd then P(even) = ((T-1)/2) / T -> 1/2
and P(odd) = ((T+1)/2) / T -> 1/2
In the limiting case, of an infinitely large set S, we find, quite as expected:
P(even) = P(odd) = 1/2
And this property does not change, no matter how large the set S will become. Such an limiting case - an almost infinitely large set S of contiguous natural numbers - could easily be renamed to: THE NATURAL NUMBERS. For who on Earth can possibly explain me what the difference would be with a "truly" infinite set of natural numbers ?
Cantor's Counter-Intuition
The above means that there are "as many" even numbers as there are odd numbers. But it also means that Half of the natural numbers would be Even (and odd for the other half, of course). Quite in agreement with Common Sense.
But "NO", says the Pure Mathematician. The following reasoning has been coined up by Cantor, and has been swallowed quite uncritically ever since, by the entire mathematical community. A one-to-one relationship (bijection) is assumed to exist between all Natural numbers and all Even numbers:
1 2 3 4 5 6 7 8 9 10 11 12 ...
2 4 6 8 10 12 14 16 18 20 22 24 ...
I would say now: Give me more, give me more ! But no, these theorists have already drawn their "inevitable" conclusion: the cardinality of the set of all natural numbers must be equal to the cardinality of the set of all even numbers. In layman's terms: there are as many even numbers as there are natural numbers. And this is Wrong !
Let's re-create earthly circumstances in the first place. Instead of Cantor's Actual Infinity, which can only exist in the Heaven of Mathematics, there is only Potential Infinity, kind of "two times larger every time again". Re-consider now a very large, but nevertheless finite set of contiguous natural numbers. Then it is very clear that the number of even integers in that set is approximately half the total number of integers. And this approximation becomes better as the set becomes larger. This is the common way in which limiting cases are explored, everywhere in mathematics where it has accomplished its great success stories, such as in differential and integral calculus. But when it comes to number theory, all these wise lessons seem to have been forgotten. Thus rendering further fruitful mathematical research virtually impossible ! So please, let us finally speak the Truth and only but the Truth:
There exist precisely Half as many Even numbers as there exist Whole numbers.
But Han, what are you doing ?! Don't you understand that so many great results in Mathematics will no longer be valid, if you dare to take such a position !
My answer is simple: this only proves that sound scientific reasoning gradually has been replaced by intimidation. I have been involved with mathematics for 40 years. And I have never encountered any significant theory which could not have been developed without the Cantor doctrine. But yes, some of the "results" which have been rendered with help of Cantor's methodology certainly will become unavailable. Such as the (in)famous Continuum Hypothesis. As a physicist, I find it utterly incredible that the whole discussion about Transfinite Numbers is not treated on the same footing as the stories about Flying Saucers. But NO ! Is it a coincidence that at least one of the board members of the sceptics organization in Holland is a mathematician ? By creating another smoke screen, it seems, they are effectively preventing the de-mystification of their own profession.
Resuming Statistics
Having said all this, consider the 'even' step in the Collatz algorithm:
Si = Si-1 / 2
This results in:
Si-1 = 2 4 6 8 10 ... 132 134 136 138 ...
Si = 1 2 3 4 5 ... 66 67 68 69 ...
Hence the probability that the result of the division will become even is equal to the probability that it will become odd. Both probabilities are equal to 1/2.
Rewrite the 'odd' step in the Collatz algorithm as follows:
Si = Si-1 + (Si-1+1)/2
This results in:
Si-1+1 = 2 4 6 8 10 ... 132 134 136 138 ...
Si = odd + 1 2 3 4 5 ... 66 67 68 69 ...
Hence the probability that the result of the addition will become even is equal to the probability that it will become odd. Both probabilities are equal again to 1/2.
Summarizing. Given an arbitrary (that is: unknown) positive integer, which is either even or odd with a probability of 50 % , then any step in the Collatz process will generate another positive integer, which is even or odd with the same probability, namely 50 % . Numbers are enlarged by the odd steps, while they are diminished by the even steps.
Infinite Loops
It is not known (yet) whether infinite loops can actually occur with the original Collatz sequence (with exception of the trivial loop (1,2)). But if we modify the procedure a little bit
5 instead of 1), then non-trivial closed loops definitely can occur:
S0 = N
and for all i > 0:
Si = Si-1 / 2 if Si-1 is even
Si = (Si-1 * 3 + 5) / 2 if Si-1 is odd
We find, for example:
19 31 49 76 38 19
Which from now on will repeat itself.
Not every modification of the (3x+1) problem necessarily has the property that it will loop somewhere. Let us consider, for example, the sequence:
S0 = N
and for all i > 0:
Si = Si-1 / 2 if Si-1 is even
Si = (Si-1 * 3 + 3) / 2 if Si-1 is odd
It can easily be shown that this "(3x+3)" sequence is, in fact, completely equivalent to the original Collatz problem, where every number in the Collatz sequence corresponds with 3 times this number in the (3x+3) = 3(x+1) problem.
Some Lemmas
Let O = the number of 'odd' iterations and D = the total length of the sequence.
An arbitrary (part of a) Collatz sequence can be written in the form:
SD = PD . S0 + QD
with PD = 3O / 2D
While QD is defined by a (3x+1)-like algorithm:
Q0 = 0
and for all 1 < i ≤ D :
Qi = Qi-1 / 2 if Si-1 is even
Qi = (Qi-1 * 3 + 1) / 2 if Si-1 is odd
The proof of this Lemma is by complete induction to D . The Lemma is certainly true for D = 0, since:
S0 = P.S0 + Q where P = 30 / 20 and Q = 0
Suppose that the Lemma is true for a sequence of length D. Then for D+1 and for odd numbers:
SD+1 = ( 3 ( PD.S0 + QD ) + 1 ) / 2 = 3O+1 / 2D+1 . S0 + (QD.3+1)/2
And for even numbers:
SD+1 = ( PD.S0 + QD ) / 2 = 3O / 2D+1 . S0 + QD/2
Let O = the number of 'odd' iterations, D = the total length of the sequence and N = S0 the number the sequence starts with.
Then, for an arbitrary (part of a) Collatz sequence, the following holds:
SD < 3O/2D ( N + 2D-O )
It is easy to see that Q in the previous Lemma has a maximum value, which occurs in sequences of the form eeeee ... ooooo, where e are even steps and o are odd steps. Experimentally, we find that this maximum value of Q is given by:
Qmax = 3O/2O - 1
It's easy to verify this by complete induction. The Lemma is obviously true for O = 1, since, starting with Q = 0:
Qmax := (3*0+1)/2 = 1/2 = 31/21 - 1
Suppose that the Lemma is true for O, then for O+1 we find:
Qmax = (3*(3O/2O-1)+1)/2 = 3O+1/2O+1-1
Rearranging terms gives for the maximum value of S:
SD = 3O/2D.N + 3O/2O - 1 < 3O/2D ( N + 2D-O )
Real Valued Bound
From the above Lemma, we may conclude that an arbitrary but finite (part of a) Collatz sequence has always another, real valued, sequence as its Upper Bound. For define the other sequence by:
R0 = N + 2D-O
and for all i > 0:
Ri = Ri-1 / 2 if Si-1 is even
Ri = 3 * Ri-1 / 2 if Si-1 is odd
The the outcome after D steps will be:
RD = 3O/2D ( N + 2D-O ) > SD
It's possible to construct a much tighter Upper Bound by traversing the Collatz sequence in reverse order:
y = (3.x + 1)/2 ==> x = (2.y - 1)/3 < 2.y/3
y = x/2 ==> x ≤ 2.y
Resulting in the following starting value for the bounding Real Valued sequence:
R0 = 2D/3O
Any sequence of integer numbers may thus be conveniently bounded by a similar one of real-valued numbers. We have already seen, in addition, that the choices 'odd' and 'even' are in fact random choices, with equal probabilities.
The convergence behaviour of Collatz sequences is thus mimicked by a procedure where random decisions are made, for example by generating random numbers in the interval (0,1) and setting up the following algorithm, for some real and sufficiently large number S:
R := Random;
if R > 0.5 then S := S + S/2;
if R < 0.5 then S := S - S/2;
This can even be generalized to arbitrary 0 < p < 1:
p := Random;
while true do
begin
R := Random;
if R > 0.5 then S := S*(1+p);
if R < 0.5 then S := S*(1-p);
end;
A sloppy argument already reveals that, in the long run, there will be as many even steps as there are odd steps, on the average. Thus the behaviour of S is roughly described by:
S := (1+p)D/2(1-p)D/2.S = (1 - p2)D/2.S
Which converges to zero, given the fact that (1 - p2) < 1.
Binomial Distribution
A definite advantage of the Real number sequences, associated with the integer Collatz sequences, is the fact that their convergence behaviour is solely determined by the factor 3O/2D :
RD = 3O/2D.R0
And we know that the accompanying Collatz sequence is entirely below it. Hence if the Real number sequence converges, then the Collatz sequence must also converge.
Now the convergence of the Real number sequence is only dependent upon the factor 3O/2D, that is: quite independent on the precise layout of the even/odd sequence. Thus we may consider all even/ odd sequences with just the same number of even/odd choices as equivalent. Then we may consider the Probability P that an even/odd sequence of length D contains a number of O odd choices. It is easy to see that this gives rise to a Binimial Distribution:
P(O) = D! / ((D-O)!.O!).(1/2)O.(1-1/2)D-O
= D! / ((D-O)!.O!) / 2D
Mean value and variance of this distribution are given by:
<O> = D.1/2 = D/2 ; <O2> - (<O>)2 = D.1/2.(1-1/2) = D/4
The Binomial Distribution may be approximated well by a Normal Distribution for moderate and large values of D. Consider values of O/D instead of O, thus restricting the independent variable to the interval [0,1]. Then the mean value becomes 1/2. And the spread of the Gaussian curve is determined by the square root of the variance, which now becomes sqrt(D/4) / D = 1/(2 sqrt(D)). We see that the bell shaped curve will converge to a sharp peaked "delta function" in the long run, that is for large values of D. On the other hand, we can see that concergence of the real valued sequence will be guaranteed in the long run if, at a certain moment:
3O/2D.x < x ==> 3O/2D < 1 ==> O.ln(3) - D.ln(2) < 0 ==>
O/D < ln(2)/ln(3) = 0.630929753571457
This is the same as demanding that the starting value of the real valued upper bound sequence should be a number which is greater than 1 :
2D/3O > 1 <==> 3O/2D < 1
When combined with the above, this means that it will be increasingly difficult to find sequences where the ratio O/D of the odd and the total number of transitions differs much from the mean value 1/2. The Convergence Criterion will become more and more satisfied as the size of the sequences grows to infinity. This could be written as:
O/D < ln(2)/ln(3) = 0.630929753571457 >> 0.5
Endless Loop, in the end ?
An escape from this "reality" is remaining, though, because we are not dealing with real but with integer numbers, in the end. While such is highly improbable for a real number (due to round-off errors), an integer number can "find itself" again - quite by coincidence, of course (;-) - exactly as it is. Resulting, finally, in an Endless Loop. Such endless loops are quite common, even with small variations on the problem: (3.x+5) , (3.x+7) , (3.x+11) , (3x+13) , (3x-1) . And we find even more of them by allowing negative numbers with the original (3x+1) sequence. But . . . does not already the original sequence end in an infinite loop, namely: 2 1 2 1 2 1 . . . ? Giving rise to the following Note. Any trivial sequence, with length T :
1 2 1 2 1 2 1 2 1 2 ...
can be used for extending an arbitrary Collatz sequence to one of predetermined length D+T. According to:
3O/2D ==> 3O+T/2/2D+T = 3O/2D . (3/4)T/2 if T is even
==> 3O+(T+1)/2/2D+T = 3O/2D . 2.(3/4)(T+1)/2 if T is odd
Meaning that all sequences are contained in the collection of sequences with large size D, maybe so large that they are approaching infinity. Then for the smaller sequences, it becomes even more certain that O/D is close to the value 0.5 .
http://huizen.dto.tudelft.nl/deBruijn/programs/collatz.htm
Maybe this is all that has to be said about the infamous Conjecture: that it is not very interesting, in the end. Herewith I mean that its contribution to Number Theory may be of NULL value. But Probability Theory is another story. probably ;-) Yes, I think the major hurdle to be taken is the idea: that the Theory of Probability can yet be used as a proper description, of processes which are quite Deterministic in nature ! (Meanwhile claiming that I am Not the first one who says this)
*) Sample of Pure Applicable Mathematics
Modified definition
To begin with, the definition of the problem (by Eric Roosendaal) will be modified slightly, as follows:
For any positive integer N a sequence Si can be defined
by putting
S0 = N
and for all i > 0:
Si = Si-1 / 2 if Si-1 is even
Si = (Si-1 * 3 + 1) / 2 if Si-1 is odd
Division by 2 in the 'odd' case eliminates the fact that any subsequent value in the sequence is necessarily an even number and hence eliminates trivial 'even' steps.
Statistical Approach
Suppose that the number N is completely arbitrary, essentially meaning that it is not known. Now consider an arbitrary large set of subsequent natural numbers, for example the collection:
1 2 3 4 5 6 7 ... 132 133 134 ... 123421412
And suppose the number N is in such a set, called S . If the number of elements in S is T, then there are two possibilities:
If T = even then the number of even integers in S is T/2
and the number of odd integers in S is T/2
If T = odd then the number of even integers in S is (T-1)/2
and the number of odd integers in S is (T+1)/2
Now suppose that the number of elements in S is very large. Then we may define the probability P that an integer N in S will be even or odd:
If T = even then P(even) = (T/2) / T = 1/2
and P(odd) = (T/2) / T = 1/2
If T = odd then P(even) = ((T-1)/2) / T -> 1/2
and P(odd) = ((T+1)/2) / T -> 1/2
In the limiting case, of an infinitely large set S, we find, quite as expected:
P(even) = P(odd) = 1/2
And this property does not change, no matter how large the set S will become. Such an limiting case - an almost infinitely large set S of contiguous natural numbers - could easily be renamed to: THE NATURAL NUMBERS. For who on Earth can possibly explain me what the difference would be with a "truly" infinite set of natural numbers ?
Cantor's Counter-Intuition
The above means that there are "as many" even numbers as there are odd numbers. But it also means that Half of the natural numbers would be Even (and odd for the other half, of course). Quite in agreement with Common Sense.
But "NO", says the Pure Mathematician. The following reasoning has been coined up by Cantor, and has been swallowed quite uncritically ever since, by the entire mathematical community. A one-to-one relationship (bijection) is assumed to exist between all Natural numbers and all Even numbers:
1 2 3 4 5 6 7 8 9 10 11 12 ...
2 4 6 8 10 12 14 16 18 20 22 24 ...
I would say now: Give me more, give me more ! But no, these theorists have already drawn their "inevitable" conclusion: the cardinality of the set of all natural numbers must be equal to the cardinality of the set of all even numbers. In layman's terms: there are as many even numbers as there are natural numbers. And this is Wrong !
Let's re-create earthly circumstances in the first place. Instead of Cantor's Actual Infinity, which can only exist in the Heaven of Mathematics, there is only Potential Infinity, kind of "two times larger every time again". Re-consider now a very large, but nevertheless finite set of contiguous natural numbers. Then it is very clear that the number of even integers in that set is approximately half the total number of integers. And this approximation becomes better as the set becomes larger. This is the common way in which limiting cases are explored, everywhere in mathematics where it has accomplished its great success stories, such as in differential and integral calculus. But when it comes to number theory, all these wise lessons seem to have been forgotten. Thus rendering further fruitful mathematical research virtually impossible ! So please, let us finally speak the Truth and only but the Truth:
There exist precisely Half as many Even numbers as there exist Whole numbers.
But Han, what are you doing ?! Don't you understand that so many great results in Mathematics will no longer be valid, if you dare to take such a position !
My answer is simple: this only proves that sound scientific reasoning gradually has been replaced by intimidation. I have been involved with mathematics for 40 years. And I have never encountered any significant theory which could not have been developed without the Cantor doctrine. But yes, some of the "results" which have been rendered with help of Cantor's methodology certainly will become unavailable. Such as the (in)famous Continuum Hypothesis. As a physicist, I find it utterly incredible that the whole discussion about Transfinite Numbers is not treated on the same footing as the stories about Flying Saucers. But NO ! Is it a coincidence that at least one of the board members of the sceptics organization in Holland is a mathematician ? By creating another smoke screen, it seems, they are effectively preventing the de-mystification of their own profession.
Resuming Statistics
Having said all this, consider the 'even' step in the Collatz algorithm:
Si = Si-1 / 2
This results in:
Si-1 = 2 4 6 8 10 ... 132 134 136 138 ...
Si = 1 2 3 4 5 ... 66 67 68 69 ...
Hence the probability that the result of the division will become even is equal to the probability that it will become odd. Both probabilities are equal to 1/2.
Rewrite the 'odd' step in the Collatz algorithm as follows:
Si = Si-1 + (Si-1+1)/2
This results in:
Si-1+1 = 2 4 6 8 10 ... 132 134 136 138 ...
Si = odd + 1 2 3 4 5 ... 66 67 68 69 ...
Hence the probability that the result of the addition will become even is equal to the probability that it will become odd. Both probabilities are equal again to 1/2.
Summarizing. Given an arbitrary (that is: unknown) positive integer, which is either even or odd with a probability of 50 % , then any step in the Collatz process will generate another positive integer, which is even or odd with the same probability, namely 50 % . Numbers are enlarged by the odd steps, while they are diminished by the even steps.
Infinite Loops
It is not known (yet) whether infinite loops can actually occur with the original Collatz sequence (with exception of the trivial loop (1,2)). But if we modify the procedure a little bit
5 instead of 1), then non-trivial closed loops definitely can occur:S0 = N
and for all i > 0:
Si = Si-1 / 2 if Si-1 is even
Si = (Si-1 * 3 + 5) / 2 if Si-1 is odd
We find, for example:
19 31 49 76 38 19
Which from now on will repeat itself.
Not every modification of the (3x+1) problem necessarily has the property that it will loop somewhere. Let us consider, for example, the sequence:
S0 = N
and for all i > 0:
Si = Si-1 / 2 if Si-1 is even
Si = (Si-1 * 3 + 3) / 2 if Si-1 is odd
It can easily be shown that this "(3x+3)" sequence is, in fact, completely equivalent to the original Collatz problem, where every number in the Collatz sequence corresponds with 3 times this number in the (3x+3) = 3(x+1) problem.
Some Lemmas
Let O = the number of 'odd' iterations and D = the total length of the sequence.
An arbitrary (part of a) Collatz sequence can be written in the form:
SD = PD . S0 + QD
with PD = 3O / 2D
While QD is defined by a (3x+1)-like algorithm:
Q0 = 0
and for all 1 < i ≤ D :
Qi = Qi-1 / 2 if Si-1 is even
Qi = (Qi-1 * 3 + 1) / 2 if Si-1 is odd
The proof of this Lemma is by complete induction to D . The Lemma is certainly true for D = 0, since:
S0 = P.S0 + Q where P = 30 / 20 and Q = 0
Suppose that the Lemma is true for a sequence of length D. Then for D+1 and for odd numbers:
SD+1 = ( 3 ( PD.S0 + QD ) + 1 ) / 2 = 3O+1 / 2D+1 . S0 + (QD.3+1)/2
And for even numbers:
SD+1 = ( PD.S0 + QD ) / 2 = 3O / 2D+1 . S0 + QD/2
Let O = the number of 'odd' iterations, D = the total length of the sequence and N = S0 the number the sequence starts with.
Then, for an arbitrary (part of a) Collatz sequence, the following holds:
SD < 3O/2D ( N + 2D-O )
It is easy to see that Q in the previous Lemma has a maximum value, which occurs in sequences of the form eeeee ... ooooo, where e are even steps and o are odd steps. Experimentally, we find that this maximum value of Q is given by:
Qmax = 3O/2O - 1
It's easy to verify this by complete induction. The Lemma is obviously true for O = 1, since, starting with Q = 0:
Qmax := (3*0+1)/2 = 1/2 = 31/21 - 1
Suppose that the Lemma is true for O, then for O+1 we find:
Qmax = (3*(3O/2O-1)+1)/2 = 3O+1/2O+1-1
Rearranging terms gives for the maximum value of S:
SD = 3O/2D.N + 3O/2O - 1 < 3O/2D ( N + 2D-O )
Real Valued Bound
From the above Lemma, we may conclude that an arbitrary but finite (part of a) Collatz sequence has always another, real valued, sequence as its Upper Bound. For define the other sequence by:
R0 = N + 2D-O
and for all i > 0:
Ri = Ri-1 / 2 if Si-1 is even
Ri = 3 * Ri-1 / 2 if Si-1 is odd
The the outcome after D steps will be:
RD = 3O/2D ( N + 2D-O ) > SD
It's possible to construct a much tighter Upper Bound by traversing the Collatz sequence in reverse order:
y = (3.x + 1)/2 ==> x = (2.y - 1)/3 < 2.y/3
y = x/2 ==> x ≤ 2.y
Resulting in the following starting value for the bounding Real Valued sequence:
R0 = 2D/3O
Any sequence of integer numbers may thus be conveniently bounded by a similar one of real-valued numbers. We have already seen, in addition, that the choices 'odd' and 'even' are in fact random choices, with equal probabilities.
The convergence behaviour of Collatz sequences is thus mimicked by a procedure where random decisions are made, for example by generating random numbers in the interval (0,1) and setting up the following algorithm, for some real and sufficiently large number S:
R := Random;
if R > 0.5 then S := S + S/2;
if R < 0.5 then S := S - S/2;
This can even be generalized to arbitrary 0 < p < 1:
p := Random;
while true do
begin
R := Random;
if R > 0.5 then S := S*(1+p);
if R < 0.5 then S := S*(1-p);
end;
A sloppy argument already reveals that, in the long run, there will be as many even steps as there are odd steps, on the average. Thus the behaviour of S is roughly described by:
S := (1+p)D/2(1-p)D/2.S = (1 - p2)D/2.S
Which converges to zero, given the fact that (1 - p2) < 1.
Binomial Distribution
A definite advantage of the Real number sequences, associated with the integer Collatz sequences, is the fact that their convergence behaviour is solely determined by the factor 3O/2D :
RD = 3O/2D.R0
And we know that the accompanying Collatz sequence is entirely below it. Hence if the Real number sequence converges, then the Collatz sequence must also converge.
Now the convergence of the Real number sequence is only dependent upon the factor 3O/2D, that is: quite independent on the precise layout of the even/odd sequence. Thus we may consider all even/ odd sequences with just the same number of even/odd choices as equivalent. Then we may consider the Probability P that an even/odd sequence of length D contains a number of O odd choices. It is easy to see that this gives rise to a Binimial Distribution:
P(O) = D! / ((D-O)!.O!).(1/2)O.(1-1/2)D-O
= D! / ((D-O)!.O!) / 2D
Mean value and variance of this distribution are given by:
<O> = D.1/2 = D/2 ; <O2> - (<O>)2 = D.1/2.(1-1/2) = D/4
The Binomial Distribution may be approximated well by a Normal Distribution for moderate and large values of D. Consider values of O/D instead of O, thus restricting the independent variable to the interval [0,1]. Then the mean value becomes 1/2. And the spread of the Gaussian curve is determined by the square root of the variance, which now becomes sqrt(D/4) / D = 1/(2 sqrt(D)). We see that the bell shaped curve will converge to a sharp peaked "delta function" in the long run, that is for large values of D. On the other hand, we can see that concergence of the real valued sequence will be guaranteed in the long run if, at a certain moment:
3O/2D.x < x ==> 3O/2D < 1 ==> O.ln(3) - D.ln(2) < 0 ==>
O/D < ln(2)/ln(3) = 0.630929753571457
This is the same as demanding that the starting value of the real valued upper bound sequence should be a number which is greater than 1 :
2D/3O > 1 <==> 3O/2D < 1
When combined with the above, this means that it will be increasingly difficult to find sequences where the ratio O/D of the odd and the total number of transitions differs much from the mean value 1/2. The Convergence Criterion will become more and more satisfied as the size of the sequences grows to infinity. This could be written as:
O/D < ln(2)/ln(3) = 0.630929753571457 >> 0.5
Endless Loop, in the end ?
An escape from this "reality" is remaining, though, because we are not dealing with real but with integer numbers, in the end. While such is highly improbable for a real number (due to round-off errors), an integer number can "find itself" again - quite by coincidence, of course (;-) - exactly as it is. Resulting, finally, in an Endless Loop. Such endless loops are quite common, even with small variations on the problem: (3.x+5) , (3.x+7) , (3.x+11) , (3x+13) , (3x-1) . And we find even more of them by allowing negative numbers with the original (3x+1) sequence. But . . . does not already the original sequence end in an infinite loop, namely: 2 1 2 1 2 1 . . . ? Giving rise to the following Note. Any trivial sequence, with length T :
1 2 1 2 1 2 1 2 1 2 ...
can be used for extending an arbitrary Collatz sequence to one of predetermined length D+T. According to:
3O/2D ==> 3O+T/2/2D+T = 3O/2D . (3/4)T/2 if T is even
==> 3O+(T+1)/2/2D+T = 3O/2D . 2.(3/4)(T+1)/2 if T is odd
Meaning that all sequences are contained in the collection of sequences with large size D, maybe so large that they are approaching infinity. Then for the smaller sequences, it becomes even more certain that O/D is close to the value 0.5 .
http://huizen.dto.tudelft.nl/deBruijn/programs/collatz.htm
SirStefan32
Krycek, Alex Krycek
jenna2891 said:
Nerd!
I can at least understand some of the problems after reading them. Most of them seem to be centered on number theory/discrete math. I didn't mind proofs in HS geometry but didn't have any real interest (or aptitude) in the kind of proofs you have to do to be a math major. My interest in math stopped at calculus and linear algebra.
CardFan67 said:Jenna's brother's keyboard does not capitalize the beginnings of sentences either... It is a family keyboard problem...
I was thinking the same thing! I'm glad I'm not the only one that had something incredibly intelligent to add to this thread!
Linderbee said:I was thinking the same thing! I'm glad I'm not the only one that had something incredibly intelligent to add to this thread!
I wonder if that whole family drives automatic cars.
arthurracoon
The Cardinal Smiles
nm132 said:
i get to take my second semester of discrete math (for CS) sometime in the next year
yipee.
arthurracoon
The Cardinal Smiles
bump
One Down:
http://mathworld.wolfram.com/PoincareConjecture.html
The Poincaré Conjecture has been solved.
http://news.yahoo.com/s/ap/20060822/ap_on_re_eu/spain_math_genius
One Down:
http://mathworld.wolfram.com/PoincareConjecture.html
The Poincaré Conjecture has been solved.
http://news.yahoo.com/s/ap/20060822/ap_on_re_eu/spain_math_genius
- Joined
- May 14, 2002
- Posts
- 87,529
- Reaction score
- 38,776
jenna2891 said:
Your brother and my dad would get along famously!
Last edited:
jenna2891
potential get-away driver: go!
- Joined
- Aug 16, 2005
- Posts
- 9,352
- Reaction score
- 4
Russ Smith said:
i am not brother!
- Joined
- Jun 5, 2003
- Posts
- 26,989
- Reaction score
- 3,984
lol!jenna2891 said:i am not brother!
There was a cartoon awhile ago--can't even remember the name of it, but it went on for a few days about the mom & her "grammar whistle". One of the cartoons the dad was talking to the kid, and he's speaking very slowly, and she's standing over him with the whistle in her mouth ready to blow it in his ear:jenna2891 said:i am not brother!
Dad: "Let's keep that between you and......"
*mom standing with whistle ready*
Dad: "me?" wincing, ready for the whistle..
mom walks away smiling, no whistle blown
Dad: "Whew!"
My kids thought that was hilarious, and whenever my youngest says something incorrectly, and I say, "What???" they'll start yelling, "Twweeeeet" (blowing the imaginary grammar whistle).
Jenna saves me from being the grammar/spelling Nazi. I didn't really want to take BIM's place
- Joined
- May 14, 2002
- Posts
- 87,529
- Reaction score
- 38,776
jenna2891 said:i am not brother!
Doh! Fixed it.
