Editing Collatz conjecture (section)

===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>