linguistic:voice_change, structural:summarization
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 n. If, for some given b and k, the inequality

holds for all a, then the first counterexample, if it exists, cannot be b modulo 2. For instance, the first counterexample must be odd because f (2 n) = n, smaller than 2 n; and it must be 3 mod 4 because f (4 n + 1) = 3 n + 1, smaller than 4 n + 1. For each starting value a which is not a counterexample to the Collatz conjecture, there is a 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 k increases, the search only needs to check those residues b that are not eliminated by lower values of k. Only an exponentially small fraction of the residues survive. 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.