BotXXX?

quote:

---

Op woensdag 09 januari 2002 21:16 schreef TARAraboemdijee het volgende:
die ondertitel van je he?
Wat moet ik daarvan denken

---

Ohh onder titel?? Tja weet niet? Wat wil je er van denken, of juist niet???

On the 3x+1 problem

By Eric Roosendaal.

SUMMARY: The so-called 3x+1 problem is to prove that all 3x+1 sequences eventually converge. The sequences themselves however and their lengths display some interesting properties and raise unanswered questions. These pages supply numerical data and propose some conjectures on this innocent looking problem.
This document contains the following sections:

In part 1 an introduction is given and the problem is defined
In part 2 the Glide is defined and investigated
In part 3 the Delay and Residue are introduced
In part 4 the Completeness and Gamma are defined
In part 5 we'll discuss Class Records
In part 6 Strength and Levels are introduced
In part 7 Path Records are investigated
In part 8 there are references to related pages
The current status of the problem is given
Join the distributed search for new class records!
Watch the progress of the distributed search project
This page was last modified on January 7, 2002

Part 1: Introduction and definitions
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 if Si-1 is odd

This latter formula usually gives the sequence its name, the 3x + 1 problem, sometimes also referred to as the Collatz problem, the Syracuse problem or some other name. Thus for N = 13 we find

S0 = 13, S1 = 40, S2 = 20, S3 = 10, S4 = 5
S5 = 16, S6 = 8, S7 = 4, S8 = 2, S9 = 1, S10 = 4
and from now on the sequence will repeat itself.

Note : although the sequence is equally well defined when the process is applied to negative integers this page deals with positive integers only, also known as the Natural Numbers. Therefore all results on this page shall always be understood to refer to natural numbers only.

We now define
Mx(N)
Mx(N) = lim k → ∞ Max(S0, S1, ..., Sk)
Mn(N)
Mn(N) = lim k → ∞ Min(S0, S1, ..., Sk)
Thus we will call any positive integer
Convergent
if Mn(N) = 1
Divergent
if Mx(N) does not exist
Cyclic
otherwise
No positive integer N is known which may possibly be divergent, and we therefore reach the widely believed yet still unproven:

Conjecture 1a : (weak 3x+1 conjecture)
No integer N is divergent.
Serious indications exist however that no other cycle but the simple 4-2-1 cycle exists. In fact it is already known that any other cycle must contain at least 275,000 elements. It is therefore not unreasonable to state

Conjecture 1b : (strong 3x+1 conjecture)
All positive integers N are convergent.
This conjecture remains unproven. However Terras proved an important though weaker theorem:
Theorem (Terras) :
Almost all positive integers N are convergent.
For an informal proof of this theorem look at the Terras theorem page
While most authors on the subject have concerned themselves mainly with proving conjecture 1b, on these pages we will from here on assume that conjecture 1b holds and look into a number of other properties of the 3x+1 sequences.
=5>

Part 2: The Glide
Glide
for any positive integer N > 1 let k be the lowest index for which Sk < N.
We shall call k the Glide of N and write this as G(N).

Calculating the Glide for any positive integer is tantamount to showing it is convergent, as long as all smaller numbers are known to be convergent as well.
Thus we may restate conjecture 1b as follows:

Conjecture 1b : (strong 3x+1 conjecture, restated)
All positive integers N > 1 have a finite Glide
It may not be immediately obvious from the definition of the sequence that arbritrarily high Glides must exist. But observe that any number of the form N = 2p - 1 with p > 1 will have S2 = 3 * 2p-1 - 1 and, since S2 is odd : S4 = 3 * 3 * 2p-2 - 1 and eventually S2p = 3p - 1.
Hence Si will not be below N for at least 2p steps, and therefore G(N) > 2p.

Although Glides are thus unbounded it is a far different proposition to find the smallest number for which G(N) > k for any given k.
Glide Record
a positive integer N is called a Glide Record
if M < N implies G(M) < G(N)

Skipping the trivial numbers 1 and 2 the first Glide Records are
N = 3 G(N) = 6
N = 7 G(N) = 11
N = 27 G(N) = 96
N = 703 G(N) = 132

and so on. The author calculated Glides over a substantial interval, and the Glide Records found so far are given in the Glide Records Table.

Note : see below for the current status on Glide records.

Part 3: Delay and Residue
Delay
for any positive integer N let k be the lowest index for which Sk = 1.
We shall call k the Delay of N and write this as D(N).
Delay Record
A positive integer N is called a Delay Record if
M < N implies D(M) < D(N).
Lengthy calculations have been made in trying to find Delay Records.
All currently known Delay Records are given in the Delay Records Table.

Note : see below for the current status on Delay records.

Residue
for any positive integer N let E(N) and O(N) denote the number of elements from S0 to SD(N)-1 which are even or odd, respectively. Obviously O(N) + E(N) = D(N).
Now due to the construction of the sequence we may write

2E(N) = 3O(N) * N * Res(N)
where Res(N) is a factor equal to the product of
(1 + 1 / ( 3 * Si ) ) taken over the odd elements Si for 0 <= i < D(N).
We will call Res(N) the Residue of N.
It turns out that Res(N) is usually small and typically lies between 1.10 and 1.25. Therefore it appears reasonable to propose

Conjecture 2a : (weak residue conjecture)
A number Resmax exists such that for every positive integer
Res(N) < Resmax.
There are serious indications though that a much more explicit conjecture can be made:

Conjecture 2b : (strong residue conjecture)
For all N Res(N) <= Res(993).
For the evidence to support this conjecture look at the residues page.
Whether conjecture 2b is true or not, we will from now on assume that at least conjecture 2a holds, and besides that Resmax << 6.

Part 4: Completeness
Completeness
for all integers N > 1 the Completeness of N, C(N), is defined by C(N) = O(N) / E(N).
Theorem 1 :
For all N > 1: C(N) < ln(2)/ln(3) = 0.63092975...
Proof :
From the previous paragraph we had, by definition
2E(N) = 3O(N) * N * Res(N)
Taking the logarithm and regrouping yields
O(N) / E(N) = ln(2) / ln(3) - (ln(N) + ln(Res(N))) / E(N)ln(3)
The final term is often small, but always > 0.
This leads to the rather more complex question of how close C(N) can get to its theoretical limit. If the final term could get infinitesimally close to zero then the completeness would get infinitesimally close to this limit. For large N the final term simplifies to ln(N) / E(N). The reciprocal of this quantity is usually defined as Gamma.
Gamma
for all integers N > 1 Gamma(N) is defined by E(N) / ln(N).
There is ample evidence to suggest that Gamma(N) will not reach arbitrary large values, and so we reach

Conjecture 3 :
A number Cmax exists such that for all N > 1 : C(N) < Cmax.
with Cmax < ln(2) / ln(3).
Or, in simpler terms: C(N) will not get infinitesimally close to its theoretical limit. For the evidence to support this conjecture look at the completeness page.

Completeness Record
A number N > 1 is called a Completeness Record if
M < N implies C(M) < C(N).
Similarly we have

Gamma Record
A number N > 1 is called a Gamma Record if
M < N implies Gamma(M) < Gamma(N).
From the similarity of their definitions tt should come as no surprise that the tables of known Completeness Records and Gamma records are virtually the same.

All Completeness and Gamma Records currently known are given in the Completeness and Gamma Records Table.

Note : see below for the current status on Completeness and Gamma records.

Part 5: Class Records

Assuming Conjecture 1b holds we can partition the positive integers into Delay Classes DCk (k=0,1,2,3...) where an integer N is said to belong to class D(N). We note that no class is empty as for N = 2k we have D(N) = k.
Class Record
The lowest element of a Delay Class DCk, is called its Class Record, indicated by Rk.

Class Records of consecutive classes are often 'related', the lower one occurring in the sequence of the higher one. Assuming Conjecture 2a holds, with Resmax < 6 we have:
Theorem 2 :
Let Rk and Rk+1 be the records of Delay Classes k and k + 1, respectively.
Then O(Rk) <= O(Rk+1) and E(Rk) <= E(Rk+1).
Proof :
Let Rk and Rk+1 be the records of classes k and k+1 respectively.
Assume O(Rk) - O(Rk+1) = x, x > 0. Then Rk+1 / Rk is equal to 2x+1 * 3x * Res(Rk) / Res(Rk+1) which for positive x is definitely >> 2.
Since N = 2 * Rk has a delay of k + 1 and is smaller than Rk+1, this would imply that Rk+1 would be no class record.
Therefore O(Rk) <= O(Rk+1).

Assume that E(Rk) - E(Rk+1) = x, x > 0. Then Rk / Rk+1 is equal to 2x * 3x+1 * Res(Rk+1) / Res(Rk) which for positive x is definitely >> 3.
Since either N = 3 * Rk+1 + 1 or N = Rk+1 / 2 has delay k, and both are smaller than Rk this would imply that Rk would be no class record.
Therefore E(Rk) <= E(Rk+1).
From the above result we may easily derive
Theorem 3 :
Let N be any Completeness Record.
Then N is a Class Record as well.
Proof :
Assume a number M < N exists with D(M) = D(N).

If O(M) = O(N), and thus E(M) = E(N), then C(M) = C(N) and thus N would be no Completeness Record.
If O(M) > O(N) then C(M) > C(N) and again N would be no Completeness Record.

Finally if O(M) < O(N) then, still assuming conjecture 2a holds, M would not be < N.
Therefore such an M does not exist and N is therefore a Class Record.

Theoretically a Completeness Record does not necessarily have to be a Delay Record as well, since a lower number with a higher Delay but lower Completeness might exist. All currently known Completeness Records are Delay Records as well though.

The 2000 problem, a different way

A challenge to the reader: in trying to find a likely candidate for R2000
eventually the number N = 67457,283406,188652 emerged.
Can anyone improve on this result?

All Class Records currently known are given in the Class Records Table.

Note : see below for the current status on Class Records.

Part 6: Strength and Levels

If Conjecture 2a holds, with Rmax << 6, this also implies that the elements of a Delay Class occur at discrete levels, which roughly lie a factor 6 apart. The elements of class 13 for example are 34, 35, 192, 208, 212, 213, 226, 227, 1280, 1344, 1360, 1364, 1365 and 8192. The grouping into four different "subclasses" is obvious.
In order to work with levels we first define a more basic parameter called the Strength:
Strength
For all positive integers N with D(N) = k the Strength S(N) is defined by
S(N) = 5 * O(N) - 3 * E(N).
The Strength of most numbers is well below zero, and positive Strengths are quite rare. It would appear though that arbitrarily high Strengths should exist.
Strength Record
A positive integer N is called a Strength Record if
M < N implies S(M) < S(N).
Strength records are extremely rare. Below 253 only four non-trivial records are known. They can be found on the Strength page together with a few numbers that are currently the best known candidates for the next records.
Based on the Strength it is easy to define the Level. Note that for all numbers N with D(N) = k we have necessarily S(N) &#8801; 5k (mod 8)

Level
For all positive integers N with D(N) = k the Level L(N) is defined by
L(N) = - [S(N) / 8 ]
(where [x] is meant to be the largest integer &#8804; x)
Thus S(34) = 5 * 3 - 3 * 10 = -15. Therefore L(34) = -[-15/8] = 2. Similarly L(192) = 3, L(1280) = 4 and L(8192) = 5. For any delay k the highest possible level occurs at N = 2k, as this is the highest number with this delay. Level 0 can be seen as the highest level for which C(N) >= 0.60.
With lower numbers the 'limited availability' of numbers makes statistics a risky approach, but with higher numbers we may say that the level yields information about the relative 'exclusiveness' of the record. From a statistical point of view with levels 'close to 0' we find that the lower the level, the less numbers are found at that level. Although numbers with negative levels do exist they are quite rare. The only number below 10,000,000,000 for which L(N) < 0 is the number already mentioned above, N = 63,728,127, for which L(N) = -1.

The next ones are L(12,235,060,455) = -1 (D(N) = 1184) and L(13,371,194,527) = -1 (D(N) = 1210). Up to 21,000,000,000 three more level -1 numbers exist, but then surprisingly the next one does not appear until R1408 = 1,444,338,092,271, a number almost 70 times bigger than its predecessor. Only 9 numbers of level -1 can be found before the first number of level -2 occurs: R1549 = 3,743,559,068,799. This number shows a surprisingly high delay, surpassing the previous Delay Record by no less than over one hundred.

Up to 100,000,000,000,000 (1014) one finds approximately 100 numbers of level -1 and just a single one of level -2, which gives a fair indication of their rarity. Thus it is rather unexpected that one finds the first number of level -3 just outside this interval at N = 100,759,293,214,567. With a Delay of 1820 this number is not only a Delay Record, surpassing the previous record with no fewer than 158 steps, but a Completeness Record as well. Remarkably a further level -3 number pops up almost immediately as R1789 is found at N = 104,797,092,792,063. A total of 15 level -3 numbers exist between 100 * 1012 and 531 * 1012 but no others appear quickly thereafter. It is in fact currently not known which is the next smallest one - at present the most likely candidate is a number over 12,000 * 1012.

Still lower levels are ever harder to come by. As the numbers start becoming bigger, searches become slower and search intervals get wider. The current candidate for lowest level -4 number stands at 18 digits, with -7 the smallest one found so far has 22 digits and the lowest number encountered of level -10 has no less than 38 digits. Reactions from anybody who might have found stronger candidates are very welcome!

Part 7: Path records and Expansion

Any positive integer N can be completely defined by the delay, the level and the residue, i.e. from these three data N can be calculated exactly. Neither of these however give any information about the path of the sequence Si. In particular no information is available of Mx(N), the highest number occurring in the 3x+1-sequence. This number is of practical importance as well, since it indicates the minimum number of bits needed for a computer algorithm to calculate a particular sequence without overflows occurring.
Path Record
a positive integer N is called a Path Record if
M < N implies Mx(M) < Mx(N)
The first Path Records are
N = 2 Mx(N) = 2
N = 3 Mx(N) = 16
N = 7 Mx(N) = 52
N = 15 Mx(N) = 160
N = 27 Mx(N) = 9232

and so on. Path records can be conveniently numbered in the order in which they occur. Thus P1 = 2, P2 = 3, etc.
A curious observation about the values of Mx(N) is

Theorem 4 :
Let N be any odd number > 2. If Mx(N) > 3N + 1 then Mx(N) &#8801; 16 (mod 36).
Proof :
Let x be Mx(N), where x &#8801; a (mod 36). We note that a can not be odd, since x must be even. We also note that we can not have a &#8801; 2 (mod 4) or else x/2 would be odd which would yield a higher number than x. Therefore a &#8801; 0 (mod 4).
Since x must be produced by a 3x+1 iteration we have a &#8801; 1 (mod 3). This leaves just 4, 16 and 28 as possible values for a.
Assume a = 4. Then let x = 36n+4. The predecessor of x was then 12n+1. Then its predecessor was 24n+2. Since this number is not &#8801; 1 (mod 3) it must have had 48n+4 as its predecessor. But this number is greater than x.
Similarly when a = 28 we find predecessors 12n+9, 24n+18 and 48n+36, which again contradicts the assumption that x is Mx(N).
Therefore a can only be equal to 16, and therefore Mx(N) &#8801; 16 (mod 36) (and its predecessors are 12n+5, 24n+10 and 8n+3).
For all Path Records Pi &#8805; 3 we indeed have Mx(Pi ) > 3.Pi + 1, therefore for i &#8805; 2 all Mx(Pi ) &#8801; 16 (mod 36).

A list of all currently known Path Records can be found in the Path Records Table.

Note : see below for the current status on Path records.

Expansion
The Expansion with respect to Q, XQ of N is defined as
XQ(N) = Mx(N) / NQ
It is easily seen that X1(N) is unbounded, since if N = 2p - 1 then, as we saw earlier, S2p = 3p - 1 and Mx(N) / N is at least approximately equal to 3p / 2p.

A more interesting question arises when we ask for which p Xp might stay bounded. The following result is well known:
Theorem 5 :
XQ is unbounded for Q < ln(3) / ln(2)
Proof :
We saw earlier that for N = 2p - 1 Mx(N) will be at least 3p - 1.
Thus for p towards infinity ln(XQ(N)) = ln(Mx(N)) - Q * ln(N) >= p * ( ln(3) - Q * ln(2) )
So for Q < ln(3) / ln(2) the limit does not exist.
When 2log(Mx(Pi)) is depicted graphically against 2log(Pi) the curve shows a tendency to become linear with an approximate slope of 2. It is not currently known whether or not this tendency is likely to persist. If it does it implies that XQ(N) is bounded for Q > 2.

Open Question 1 :
Does a number C exist for which X2(N) < C for all N ?
And if it does, what is the value of C ?
Currently the highest X2(N) occurs at N = P62. A more practical and much easier question to settle should therefore be
Open Question 2 :
Does an N exist for which X2(N) > X2(P62)
where P62 = 3,716,509,988,199 ?
The author would like to conjecture: 'Yes'. This could obviously be proven by simply calculating the next one. Anybody hoping to settle this issue overnight should first take note of the following though:
A peculiar result is that the function X2(N) reaches a temporary maximum of 12.66 at N = 27, which holds until P43 = 319,804,831 is reached, a number over 10,000,000 times larger. Again, the value of 13.83 reached by P43 is not surpassed until P62, which scores 15.05. P62 (see above) is over 10,000 times larger than P43. If successive gaps between ever higher values of the function X2(N) continue to be of this magnitude it may take some serious calculation efforts to settle Open Question 2!

Part 8: References to other pages on this topic
In August 1999 the first conference on the 3x+1 problem took place in Eichstätt.
&#8226; Here's a nice picture of the Eichstätt conference participants.
In June 2001 there was going to be a second conference on the Collatz problem in Strasbourg.
&#8226; Unfortunately this event had to be canceled when the organizer became seriously ill.
Lagarias overview of the 3x+1 problem.
Super-Index of the 3x+1 Problem and its generalizations.
Gary T. Leavens and Mike Vermeulen : 3x+1 search programs
Computers Math. Applic. Vol. 24, No 11, pp. 79-99 (1992)
The most extensive search on Path and Glide Records was done by Tomás Oliveira e Silva.
Colin Campbell's pages on the 3x+1 problem contain quite a few references and links as well.
Ken Conrow's 3n+1 problem structure page.
This excellent online 3x+1 calculator by Alfred Wassermann can handle really big numbers as well.

Current status

All numbers up to 76,561 * 1012 ( 68 . 250 ) have been (double) checked for convergence.
All numbers up to 9020 * 1012 have been checked for class records. (View progress)

Glide Records found : 30
Highest Glide : 1445 at N = 1008,932249,296231
Highest Residue : 1.253142 at N = 993
Class Records found : 1898
Delay Records found : 124
Highest Delay : 1958 at N = 7579,309213,675935
Completeness Records : 14
Highest Completeness : 0.604938 at N = 100,759293,214567
Gamma Records : 13
Highest Gamma : 35.169600 at N = 100,759293,214567
Path Records found : 77
Highest Path Record : 603.5 E+30 at N = 49163,256101,584231
Highest Expansion (Q=2): 15.054 at N = 3,716509,988199

To find out more on the programming techniques used to obtain these results please consult this page on technical details.

Join the 3x + 1 search!
Whenever (computer) time is available the quest for new records still continues!
But with numbers getting ever bigger, more and more CPU time is needed to make any progress.
Now that a recent version of the program can run unattended, anyone with lots of idle time on a (fast) PC can join the 3x+1 search! Just look at the 3x+1 search page to see how to join, or take a look at the Class Record progress map.

Special thanks to Luigi Morelli from Italy who was first to join and to Kevin Hebb from Canada for the time and effort he took (and still takes!) to make two entire classrooms of PC's work virtually day and night on the problem.

Please mail any offers for additional help to the author of these pages.

Page statistics:

Staat toch alleen Tara en verderz niks.

Maar IK houd van Tara

_{is dan wel een andere Tara dan jouw persoontje}

quote:

---

Op zaterdag 12 januari 2002 21:42 schreef morpheus_at_work het volgende:
bladiebla

---