The Collatz Conjecture, also known as the 3x+1 problem, is a fascinating mathematical puzzle that has been named after the German mathematician Lothar Collatz. This conjecture arises from an iterative process where you start with any positive integer and alternate between two simple rules:
if the number is even, you divide it by 2,
and if it's odd, you multiply it by 3 and add 1.
For example, take the number 3. It's odd, so we multiply by 3 and add 1. We get 10. Now that's even, so we can divide it by 2, to get 5. Back to odd, so let's multiply that by 3 and add 1. We are now at 16, which is very even. So much so that we can keep on dividing by 2 until we reach 1.
The question is, can you predict what the number will be after a certain number of iterations?
The conjecture is that no matter what starting number you choose, regardless of its size, you will always reach the number 1.
However, despite being relatively simple to understand and easy to test for small numbers, it has so far proven difficult to prove definitively for all cases. This conjecture is an unsolved problem in mathematics that continues to intrigue both mathematicians and enthusiasts alike.
Calculate the collatz sequence of a number using the absolute shortcut formulation: g(n) = (3n + 1) / 2^k if odd where k is the highest power that divides 3n+1 and g(n) = n / 2 if even
NetworkLayout: Used to compute the layout of the graphs.
ImageIO: Used to faciliate the handling of images.
ImageShow: Enhances the displaying of the images in the interactive visualization and the gallery.
mimetext/htmlrootassigneelast_run_timestampAڅpersist_js_state·has_pluto_hook_features§cell_id$13f52ec2-16b9-41a5-9560-177ca827a72edepends_on_disabled_cells§runtime !gCpublished_object_keysdepends_on_skipped_cells§errored$b4a31304-34a3-4ecc-8c6e-e67714bc5d52queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ
:persist_js_state·has_pluto_hook_features§cell_id$b4a31304-34a3-4ecc-8c6e-e67714bc5d52depends_on_disabled_cells§runtime 6published_object_keysdepends_on_skipped_cells§errored$7dac4da8-0877-4d07-b4d2-2164faeccfdequeued¤logsrunning¦outputbody7format_sliderParameter (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڅްpersist_js_state·has_pluto_hook_features§cell_id$7dac4da8-0877-4d07-b4d2-2164faeccfdedepends_on_disabled_cells§runtime9published_object_keysdepends_on_skipped_cells§errored$7dbfb4dc-c9d0-464d-83b2-18db90d76878queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ persist_js_state·has_pluto_hook_features§cell_id$7dbfb4dc-c9d0-464d-83b2-18db90d76878depends_on_disabled_cells§runtimej[published_object_keysdepends_on_skipped_cells§errored$d0672735-8007-4a69-9fa5-0f40ac0685eaqueued¤logsrunning¦outputbody^
This function is used to explore the tree return by tree_graph from Collatz.jl and modify the graph g given as input.
Args
g::SimpleGraph: The graph to modify
record::Array{Tuple{Number,Number}}: An array that keeps track of each of the encountered values. Each value is stored as (depth, value) in order to keep track of what depth the value was encountered
tree::Dict: The tree graph returned by tree_graph
previous::Number: The number passed by the previous call to the function
A generalization of the collatz function is the following:
$g(n) = n/P \ \ \ \ \ \ \ \text{when}\ \ \ n \ \text{mod}\ P = 0$
$g(n) = an+b \ \ \ \text{otherwise}$
This formulation makes sure that we always deal with integers.
mimetext/htmlrootassigneelast_run_timestampAڅ|ʰpersist_js_state·has_pluto_hook_features§cell_id$b9277abb-7a14-4479-8bcb-6a50df27182bdepends_on_disabled_cells§runtime ͵published_object_keysdepends_on_skipped_cells§errored$fb2dd0e1-5198-4c0a-b62b-50649ac21f32queued¤logsrunning¦outputbody*get_notes (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڅ rpersist_js_state·has_pluto_hook_features§cell_id$fb2dd0e1-5198-4c0a-b62b-50649ac21f32depends_on_disabled_cells§runtimeJpublished_object_keysdepends_on_skipped_cells§errored$43c4fd8d-bb44-43cd-91dd-d221629d1fd9queued¤logsrunning¦outputbody-%
mimetext/htmlrootassigneelast_run_timestampAڅ̓persist_js_state·has_pluto_hook_features§cell_id$90dc6dd4-c4f3-4e4d-8e91-0fecafd258e1depends_on_disabled_cells§runtime \յpublished_object_keysdepends_on_skipped_cells§errored$2d98aed3-9a51-4225-b914-a20b19f43908queued¤logsrunning¦outputbody3format_colorPicker (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڅ =}kpersist_js_state·has_pluto_hook_features§cell_id$2d98aed3-9a51-4225-b914-a20b19f43908depends_on_disabled_cells§runtime Cpublished_object_keysdepends_on_skipped_cells§errored$45ca6e2a-6a58-475e-9c02-4925e71625bdqueued¤logsrunning¦outputbody M
mimeimage/svg+xmlrootassigneelast_run_timestampAڅ ﮰpersist_js_state·has_pluto_hook_features§cell_id$45ca6e2a-6a58-475e-9c02-4925e71625bddepends_on_disabled_cells§runtimeέ4>\published_object_keysdepends_on_skipped_cells§errored$b7b80bd8-7a16-4483-9b8f-b6a8da531b0aqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ}2]persist_js_state·has_pluto_hook_features§cell_id$b7b80bd8-7a16-4483-9b8f-b6a8da531b0adepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$1c3f1bea-f1ba-4d64-90ad-584391c01da5queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅzpersist_js_state·has_pluto_hook_features§cell_id$1c3f1bea-f1ba-4d64-90ad-584391c01da5depends_on_disabled_cells§runtime~{published_object_keysdepends_on_skipped_cells§errored$f02affaa-534b-4c72-81ae-c42ca3b455fdqueued¤logsrunning¦outputbody:
mimetext/htmlrootassigneelast_run_timestampAڅy.persist_js_state·has_pluto_hook_features§cell_id$75b9294e-43a4-48c4-b493-5d40027f3cd6depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$4dd44fbd-f26a-4b72-a580-842209b44f27queued¤logsrunning¦outputbody8format_sliderParameter (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampAڅҰpersist_js_state·has_pluto_hook_features§cell_id$4dd44fbd-f26a-4b72-a580-842209b44f27depends_on_disabled_cells§runtime upublished_object_keysdepends_on_skipped_cells§errored$5683080b-7d4b-4e34-aa75-b3c68dc60314queued¤logsrunning¦outputbody
This function is used to draw the trajectory of the hailstone sequence of a number. Using a Turtle, the function loops over each number in the sequence. For the sequence, a curve is drawn where for each step in the sequence, it will curves one way if the number is odd, and the other way if the number is even.
At first it might seem that the fact that it always reaches 1 could appear strange, as some numbers get caught in a repeating pattern of multiplying by 3 and adding one, when dividing by 2, give a another odd number. Since:
$\begin{aligned} x < \frac{3x + 1}{2} \end{aligned}$
Thus, it's possible (and quite frequent) that we end going up in numbers, and looks like we are getting further away from the pit of doom that is the number 1.
However, this is unfortunately not the case, but we quantify this by calculating how long it takes for a number to reach a another number that is lower than the starting point: the stopping time.
Here is a plot to show the total stopping times of the numbers for up to 1000.
This function is used to explore the tree return by tree_graph from Collatz.jl and modify the graph g given as input.
Args
g::SimpleGraph: The graph to modify
record::Array{Tuple{Number,Number}}: An array that keeps track of each of the encountered values. Each value is stored as (depth, value) in order to keep track of what depth the value was encountered
tree::Dict: The tree graph returned by tree_graph
previous::Number: The number passed by the previous call to the function
mimetext/htmlrootassigneelast_run_timestampAڅ}uupersist_js_state·has_pluto_hook_features§cell_id$546a2cf6-f54a-4482-9da5-af9d966b22ebdepends_on_disabled_cells§runtime 'Ƶpublished_object_keysdepends_on_skipped_cells§errored$b7161895-ba79-4b99-b2f1-eda7484708daqueued¤logslinemsgBCustom style is applied, running with default collatz parameters..text/plaincell_id$b7161895-ba79-4b99-b2f1-eda7484708dakwargsidMain_workspace#4_5b2c1c73filei/home/runner/work/featured/featured/src/math/CollatzConjecture.jl#==#d6cc6642-018d-4a7f-b82a-dd50bff8e2fcgroupCollatzConjecturelevelInforunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ
opersist_js_state·has_pluto_hook_features§cell_id$b7161895-ba79-4b99-b2f1-eda7484708dadepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$01cc5e4f-d94b-4211-b268-9ce0640cd23fqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ Vbpersist_js_state·has_pluto_hook_features§cell_id$01cc5e4f-d94b-4211-b268-9ce0640cd23fdepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$8a64e9e3-477e-4a7e-97f7-61cf5e428731queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ lpersist_js_state·has_pluto_hook_features§cell_id$8a64e9e3-477e-4a7e-97f7-61cf5e428731depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$b3c9453e-3198-4697-966f-ade21f2255cequeued¤logsrunning¦outputbody
The sequence of values that you go through when iterating a number is often called the hailstone sequence, as the numbers go up and down through the sequence.
mimetext/htmlrootassigneelast_run_timestampAڅx߰persist_js_state·has_pluto_hook_features§cell_id$b3c9453e-3198-4697-966f-ade21f2255cedepends_on_disabled_cells§runtime xpublished_object_keysdepends_on_skipped_cells§errored$af0c36ee-0534-4143-b59b-4ee041ef0f04queued¤logsrunning¦outputbodymimetext/htmlrootassigneelast_run_timestampAڅpersist_js_state·has_pluto_hook_features§cell_id$af0c36ee-0534-4143-b59b-4ee041ef0f04depends_on_disabled_cells§runtime
jpublished_object_keysdepends_on_skipped_cells§errored$f680e7ea-8e3a-41ac-ab92-a27c05103864queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampAڅ -persist_js_state·has_pluto_hook_features§cell_id$f680e7ea-8e3a-41ac-ab92-a27c05103864depends_on_disabled_cells§runtime
0published_object_keysdepends_on_skipped_cells§errored$a7885279-3f73-4c5d-aeef-061dea1ce930queued¤logsrunning¦outputbody9format_checkBoxParameter (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampAڅ persist_js_state·has_pluto_hook_features§cell_id$a7885279-3f73-4c5d-aeef-061dea1ce930depends_on_disabled_cells§runtime FZpublished_object_keysdepends_on_skipped_cells§errored$1255f4cc-7448-40f6-83ba-0cca1637d1cfqueued¤logsrunning¦outputbodyColorParametermimetext/plainrootassigneelast_run_timestampAڅhpersist_js_state·has_pluto_hook_features§cell_id$1255f4cc-7448-40f6-83ba-0cca1637d1cfdepends_on_disabled_cells§runtime7Spublished_object_keysdepends_on_skipped_cells§errored$e4a76493-9aea-4379-9a56-6a9b9e8d6b54queued¤logsrunning¦outputbody
Notebook Packages
PlutoUI: Extension for Pluto to handle interactivity, provides the Sliders, Checkboxes and Color Picker.
While playing around with the viusalization, I stumbled into some nice patterns that I wanted to share with you! I added the parameters in case you want to recreate them. Enjoy :)
(Note that the parameters are highly dependent on the size of the canvas so it might not be trivial to reproduced)
mimetext/htmlrootassigneelast_run_timestampAڅpersist_js_state·has_pluto_hook_features§cell_id$66fe673a-7679-4c55-bf59-146a8dd1241cdepends_on_disabled_cells§runtime >gQpublished_object_keysdepends_on_skipped_cells§errored$f47eb656-67ec-4760-8906-713fa480cb47queued¤logsrunning¦outputbody\