*) Sample of Pure Applicable Mathematics
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 oddDivision 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.
1 2 3 4 5 6 7 ... 132 133 134 ... 123421412And 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)/2Now 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/2In the limiting case, of an infinitely large set S, we find, quite as expected:
P(even) = P(odd) = 1/2And 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 ?
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 !
Si = Si-1 / 2This 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.
Si = Si-1 + (Si-1+1)/2This 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.
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 oddWe find, for example:
19 31 49 76 38 19Which 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
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.
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 oddThe 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 = 0Suppose 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)/2And 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 )
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 oddThe the outcome after D steps will be:
RD = 3O/2D ( N + 2D-O ) > SDIt'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.yResulting in the following starting value for the bounding Real Valued sequence:
R0 = 2D/3OAny 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.
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.SWhich converges to zero, given the fact that (1 - p2) < 1.
RD = 3O/2D.R0And 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.
P(O) = D! / ((D-O)!.O!).(1/2)O.(1-1/2)D-O = D! / ((D-O)!.O!) / 2DMean 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/4The 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 ==>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 :
O/D < ln(2)/ln(3) = 0.630929753571457
2D/3O > 1 <==> 3O/2D < 1When 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
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 oddMeaning 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 .