Editing Collatz conjecture (section)

===In reverse===
[[File:Collatz-tree, depth=20.svg|thumb|upright=2|The first 21 levels of the ''Collatz [[Graph (discrete mathematics)|graph]]'' generated in bottom-up fashion. The graph includes all numbers with an orbit length of 21 or less.]]
There is another approach to prove the conjecture, which considers the bottom-up
method of growing the so-called ''Collatz graph''. The ''Collatz graph'' is a [[Graph (discrete mathematics)|graph]] defined by the inverse [[relation (mathematics)|relation]]
<math display="block"> R(n) = \begin{cases} \{2n\} & \text{if } n\equiv 0,1,2,3,5 \\ \left\{2n,\frac{n-1}{3}\right\} & \text{if } n\equiv 4 \end{cases} \pmod 6. </math>

So, instead of proving that all positive integers eventually lead to 1, we can try to prove that 1 leads backwards to all positive integers. For any integer {{mvar|n}}, {{math|''n'' ≡ 1 (mod 2)}} [[if and only if]] {{math|3''n'' + 1 ≡ 4 (mod 6)}}. Equivalently, {{math|{{sfrac|''n'' − 1|3}} ≡ 1 (mod 2)}} if and only if {{math|''n'' ≡ 4 (mod 6)}}. Conjecturally, this inverse relation forms a [[tree (graph theory)|tree]] except for the 1–2–4 loop (the inverse of the 4–2–1 loop of the unaltered function {{mvar|f}} defined in the [[#Statement of the problem|Statement of the problem]] section of this article).

When the relation {{math|3''n'' + 1}} of the function {{mvar|f}} is replaced by the common substitute "shortcut" relation {{math|{{sfrac|3''n'' + 1|2}}}}, the Collatz graph is defined by the inverse relation,
<math display="block"> R(n) = \begin{cases} \{2n\} & \text{if } n\equiv 0,1 \\ \left\{2n,\frac{2n-1}{3}\right\} & \text{if } n\equiv 2 \end{cases} \pmod 3. </math>

For any integer {{mvar|n}}, {{math|''n'' ≡ 1 (mod 2)}} if and only if {{math|{{sfrac|3''n'' + 1|2}} ≡ 2 (mod 3)}}. Equivalently, {{math|{{sfrac|2''n'' − 1|3}} ≡ 1 (mod 2)}} if and only if {{math|''n'' ≡ 2 (mod 3)}}. Conjecturally, this inverse relation forms a tree except for a 1–2 loop (the inverse of the 1–2 loop of the function f(n) revised as indicated above).

Alternatively, replace the {{math|3''n'' + 1}} with {{math|{{sfrac|''n''{{prime}}|''H''(''n''{{prime}})}}}} where {{math|''n''{{prime}} {{=}} 3''n'' + 1}} and {{math|''H''(''n''{{prime}})}} is the highest [[power of 2]] that divides {{math|''n''{{prime}}}} (with no [[remainder]]). The resulting function {{mvar|f}} maps from [[odd number]]s to odd numbers. Now suppose that for some odd number {{mvar|n}}, applying this operation {{mvar|k}} times yields the number 1 (that is, {{math|''f''{{isup|''k''}}(''n'') {{=}} 1}}). Then in [[Binary number|binary]], the number {{mvar|n}} can be written as the concatenation of [[String (computer science)|strings]] {{math|''w''<sub>''k''</sub> ''w''<sub>''k''−1</sub> ... ''w''<sub>1</sub>}} where each {{math|''w''<sub>''h''</sub>}} is a finite and contiguous extract from the representation of {{math|{{sfrac|1|3<sup>''h''</sup>}}}}.<ref name="Colussi2011">{{cite journal |last=Colussi |first=Livio |date=9 September 2011 |title=The convergence classes of Collatz function |journal=Theoretical Computer Science |doi=10.1016/j.tcs.2011.05.056 |volume=412 |issue=39 |pages=5409–5419|doi-access=free }}</ref> The representation of {{mvar|n}} therefore holds the [[Repeating decimal|repetends]] of {{math|{{sfrac|1|3<sup>''h''</sup>}}}}, where each repetend is optionally rotated and then replicated up to a finite number of bits. It is only in binary that this occurs.<ref name="Hew2016">{{cite journal |last=Hew |first=Patrick Chisan |date=7 March 2016 |title=Working in binary protects the repetends of 1/3<sup>''h''</sup>: Comment on Colussi's 'The convergence classes of Collatz function' |journal=Theoretical Computer Science |doi=10.1016/j.tcs.2015.12.033 |volume=618 |pages=135–141|doi-access=free }}</ref> Conjecturally, every binary string {{mvar|s}} that ends with a '1' can be reached by a representation of this form (where we may add or delete leading '0's to&nbsp;{{mvar|s}}).