Editing Collatz conjecture (section)

==Optimizations==
===Time–space tradeoff===
The section ''[[#As a parity sequence|As a parity sequence]]'' above gives a way to speed up simulation of the sequence. To jump ahead {{mvar|k}} steps on each iteration (using the {{mvar|f}} function from that section), break up the current number into two parts, {{mvar|b}} (the {{mvar|k}} least significant bits, interpreted as an integer), and {{mvar|a}} (the rest of the bits as an integer). The result of jumping ahead {{mvar|k}} is given by
:{{math|''f''{{isup|''k''}}(2<sup>''k''</sup>''a'' + ''b'') {{=}} 3<sup>''c''(''b'', ''k'')</sup>''a'' + ''d''(''b'', ''k'')}}.
The values of {{mvar|c}} (or better {{math|3<sup>''c''</sup>}}) and {{mvar|d}} can be precalculated for all possible {{mvar|k}}-bit numbers {{mvar|b}}, where {{math|''d''(''b'', ''k'')}} is the result of applying the {{mvar|f}} function {{mvar|k}} times to {{mvar|b}}, and {{math|''c''(''b'', ''k'')}} is the number of odd numbers encountered on the way.<ref>{{cite web |last=Scollo |first=Giuseppe |year=2007 |title=Looking for class records in the 3''x'' + 1 problem by means of the COMETA grid infrastructure |work=Grid Open Days at the University of Palermo |url=http://www.dmi.unict.it/~scollo/seminars/gridpa2007/CR3x+1paper.pdf}}</ref> For example, if {{math|''k'' {{=}} 5}}, one can jump ahead 5 steps on each iteration by separating out the 5 least significant bits of a number and using

: {{mvar|c}}(0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 },
: {{mvar|d}}(0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.

This requires {{math|2<sup>''k''</sup>}} [[precomputation]] and storage to speed up the resulting calculation by a factor of {{mvar|k}}, a [[space–time tradeoff]].

===Modular restrictions===
For the special purpose of searching for a counterexample to the Collatz conjecture, this precomputation leads to an even more important acceleration, used by Tomás Oliveira e Silva in his computational confirmations of the Collatz conjecture up to large values of&nbsp;{{mvar|n}}. If, for some given {{mvar|b}} and {{mvar|k}}, the inequality

:{{math|''f''{{isup|''k''}}(2<sup>''k''</sup>''a'' + ''b'') {{=}} 3<sup>''c''(''b'')</sup>''a'' + ''d''(''b'') < 2<sup>''k''</sup>''a'' + ''b''}}

holds for all {{mvar|a}}, then the first counterexample, if it exists, cannot be {{mvar|b}} modulo {{math|2<sup>''k''</sup>}}.<ref name="Garner (1981)"/> For instance, the first counterexample must be odd because {{math|''f''(2''n'') {{=}} ''n''}}, smaller than {{math|2''n''}}; and it must be 3 mod 4 because {{math|''f''{{isup|2}}(4''n'' + 1) {{=}} 3''n'' + 1}}, smaller than {{math|4''n'' + 1}}. For each starting value {{mvar|a}} which is not a counterexample to the Collatz conjecture, there is a {{mvar|k}} for which such an inequality holds, so checking the Collatz conjecture for one starting value is as good as checking an entire congruence class. As {{mvar|k}} increases, the search only needs to check those residues {{mvar|b}} that are not eliminated by lower values of&nbsp;{{mvar|k}}. Only an exponentially small fraction of the residues survive.{{refn|{{named ref|name=Lagarias (1985)}} Theorem D.}} For example, the only surviving residues mod 32 are 7, 15, 27, and 31.

Integers divisible by 3 cannot form a cycle, so these integers do not need to be checked as counter examples.<ref name=Clay>{{cite web |last=Clay |first=Oliver Keatinge|title=The Long Search for Collatz Counterexamples |url=https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=2052&context=jhm|pages=208|access-date=26 July 2024}}</ref>