- \n
- If the integer is even, divide it by 2<\/li>\n
- If the integer is odd, multiply it by 3 and then add 1><\/li>\n<\/ul>\n<\/div>\n
There it is.\u00a0 It is so simple that it can be implemented in a few lines in just about any language; probably even in COBOL.\u00a0 And yet, proving that this conjecture is actually so hard that the famous mathematician Paul Erd\u00f6s is credited with saying<\/p>\n
Mathematics may not be ready for such problems.<\/p>\n\u2013 Paul Erd\u00f6s on the Collatz Conjecture<\/div>\n<\/div>\nObviously this column is not going to present a proof but it is going to explore some of the properties of the conjecture \u2013 including a few that may not have been seen in the literature.\u00a0 There are two reasons for doing so.<\/p>\n
The first reason is the sheer joy and delight that arises from seeing inexplicable complexity arise out of such simple rules.\u00a0 Amazingly rich plots results simply by looking at the data from numerical experiments in a variety of different ways.\u00a0 What, at first, may look like randomness resolves itself in patterns later on as the number of integers examined is increased.<\/p>\n
The second reason is less about mathematics and far more about human reason.\u00a0 Why a proof is hard to find is a topic in epistemology worth exploring all on its own.\u00a0 Consider that the Collatz conjecture is a system that is far easier to encode in a computer than say the solution to an orbital mechanics problem or the motion of a fluid over a fixed object like an airplane wing.\u00a0 No calculus or linear algebra is required.\u00a0 Nowhere does one need real or complex numbers.\u00a0 All the machinery that is needed is learned in elementary school and yet the proof is much harder than those associated with the \u2018more advanced\u2019 topics.\u00a0 Surely there is a Socratic lesson buried in all of this. But before we explore that topic, let\u2019s look at the Collatz conjecture in detail.<\/p>\n
Pick an integer, say $n = 3$, and apply the HTPO process to it. \u00a0Since 3 is odd, the resulting value is 10.\u00a0 Now use 10 and the next value and again apply the HTPO process.\u00a0 Since 10 is even, the resulting value is 5.\u00a0 Starting from here and applying in succession leads to the following \u2018trajectory\u2019.<\/p>\n
![\"htpo_process_for_3\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/HTPO_process_for_3.jpg\")
<\/a><\/p>\nNote how the sequence of numbers rises and falls getting up as high as 16 and falling as low as 1.\u00a0 This is called a hailstone sequence since it is reminiscent of the multiple rises and falls of a hailstone during a thunderstorm.\u00a0 Also note that once the number 1 is reached the sequence is now trapped in the infinitely-repeating \u20184-2-1\u2019 loop.\u00a0 It is customary to stop the iterations when 1 is reached for the first time and to declare that the sequence has stopped.\u00a0 By convention, the number of integers in the sequence (including the starting value) is declared as the stopping time.\u00a0 Thus the stopping time for a starting value of 3 is 8, the number of unique circles in the figure.<\/p>\n
The Collatz Conjecture is then the statement that the number 1 is always reached no matter what the initial value may be.\u00a0 While the proof of this assertion has not be obtained, huge numbers have been tested (260<\/sup> = 1,152,921,504,606,846,976 ) and none have failed to reach 1 and settle into the \u20184-2-1\u2019 loop.<\/p>\n
Investigators, looking for a proof, have employed a number of tools in an attempt to better understand what makes this conjecture so shy in being characterized with a logical proof.\u00a0 Many of these tools are visualizations of the stopping times as a function of initial value.<\/p>\n
The following figure is one such plot showing the stopping times for the first 100 integers.<\/p>\n
![\"collatz_stopping_n100\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_stopping_n100.png\")
<\/a><\/p>\nIt is remarkable that there is no smooth pattern in the results.\u00a0 Adjacent integers, such as 26 and 27, can have wildly different stopping lengths, 10 versus 111, respectively, while adjacent pairs can have identical stopping lengths.\u00a0 Particularly noteworthy is the fact that the integers 28, 29, and 30 all have a stopping length of 18 despite their rather different trajectories:<\/p>\n
![\"collatz_stopping_n28_n29_n30\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_stopping_n28_n29_n30.jpg\")
<\/a><\/p>\nThe jerky or random character of the stopping length plot for the first 100 integers transitions into something more akin to patterns within patterns when the number of integers surveyed increases to\u00a02000.<\/p>\n
![\"collatz_stopping_n2000\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_stopping_n2000.jpg\")
<\/a><\/p>\nThere seem to be overlapping curves asymptotically rising and falling, layered one on top of the other with large regions where they interleave.<\/p>\n
Different visualizations reveal different structures.\u00a0 For example, the stopping times for the first 10000 integers, plotted on a semilog plot<\/p>\n
![\"collatz_stopping_n10000_semilogx\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_stopping_n10000_semilogx.jpg\")
<\/a><\/p>\nreveal a general triangular shape, whereas the same data shown on a full log-log plot shows<\/p>\n
![\"collatz_stopping_n10000_loglog\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_stopping_n10000_loglog.jpg\")
<\/a><\/p>\nthat the values are tending to cluster rather that moving in a unbounded fashion.<\/p>\n
This latter observation opened another line of inquiry centered on just how high does the hailstone trajectory go rather than how long does it take for it to land.\u00a0 A little bit of additional coding to capture the full trajectory for the first 2000 integers reveals that one value, 9232, tends to be hit more often than all the others.<\/p>\n
![\"collatz_maximum_n2000\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_maximum_n2000.jpg\")
<\/a><\/p>\nThere is a strong line visible just under 104<\/sup> on the plot and some simple statistics show that 9232 forms 16% of all the highest values in the first 100 integers and about 33.8% for the first 2000.\u00a0 As the integer range increases to 20000, additional horizontal attractors (to coin a term in relation to the Collatz Conjecture) come in, although it is difficult to pick out just how prominent they are due to the business of the plot.<\/p>\n
![\"collatz_maximum_n20000\"](\"http:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2016\/09\/Collatz_maximum_n20000.jpg\")
<\/a><\/p>\nIt is interesting to see just how low these horizontal attractors extend.<\/p>\n
As this column closes, it is worth repeating that all of this structure comes from a repeated application of the HTPO process for a finite number of times.\u00a0 The fact that mathematics can\u2019t say whether the process will stop for arbitrary integers is astonishing and speaks to many of the basic complexities that arise in proof and logic when the repeated operations are involved.\u00a0 It seems that if Socrates were alive and playing with the Collatz Conjecture he might be inclined to point out that the only wisdom is knowing that we don\u2019t know very much.<\/p>\n","protected":false},"excerpt":{"rendered":"
Big things come in small packages.\u00a0 From tiny acorns grow mighty oaks.\u00a0 Never judge a book by its cover.\u00a0 These familiar euphemisms try to capture, in a pithy way, the… Read more ><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-569","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/569","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=569"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/569\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=569"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=569"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=569"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}