Editing Collatz conjecture (section)

==Other formulations of the conjecture==

===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}}).

===As an abstract machine that computes in base two===
Repeated applications of the Collatz function can be represented as an [[abstract machine]] that handles [[string (computer science)|strings]] of [[bit]]s. The machine will perform the following three steps on any odd number until only one {{mono|1}} remains:

# Append {{mono|1}} to the (right) end of the number in binary (giving {{math|2''n'' + 1}});
# Add this to the original number by binary addition (giving {{math|2''n'' + 1 + ''n'' {{=}} 3''n'' + 1}});
# Remove all trailing {{mono|0}}s (that is, repeatedly divide by 2 until the result is odd).

====Example====
The starting number 7 is written in base two as {{mono|111}}. The resulting Collatz sequence is:

<div style="font-family:monospace">
          111
         <u>111'''1'''</u>
        1011<s>0</s>
       <u>1011'''1'''</u>
      10001<s>0</s>
     <u>10001'''1'''</u>
     1101<s>00</s>
    <u>1101'''1'''</u>
   101<s>000</s>
  <u>101'''1'''</u>
 1<s>0000</s>
</div>

===As a parity sequence===
For this section, consider the shortcut form of the Collatz function
<math display="block"> f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \\ \frac{3n + 1}{2} & \text{if } n \equiv 1 \end{cases} \pmod{2}.</math>

If {{math|P(...)}} is the parity of a number, that is {{math|P(2''n'') {{=}} 0}} and {{math|P(2''n'' + 1) {{=}} 1}}, then we can define the Collatz parity sequence (or parity vector) for a number {{mvar|n}} as {{math|''p<sub>i</sub>'' {{=}} P(''a<sub>i</sub>'')}}, where {{math|''a''<sub>0</sub> {{=}} ''n''}}, and {{math|''a''<sub>''i''+1</sub> {{=}} ''f''(''a''<sub>''i''</sub>)}}.

Which operation is performed, {{math|{{sfrac|3''n'' + 1|2}}}} or {{math|{{sfrac|''n''|2}}}}, depends on the parity. The parity sequence is the same as the sequence of operations.

Using this form for {{math|''f''(''n'')}}, it can be shown that the parity sequences for two numbers {{mvar|m}} and {{mvar|n}} will agree in the first {{mvar|k}} terms if and only if {{mvar|m}} and {{mvar|n}} are equivalent modulo {{math|2<sup>''k''</sup>}}. This implies that every number is uniquely identified by its parity sequence, and moreover that if there are multiple Hailstone cycles, then their corresponding parity cycles must be different.<ref name="Lagarias (1985)"/><ref name="Terras (1976)"/>

Applying the {{mvar|f}} function {{mvar|k}} times to the number {{math|''n'' {{=}} 2<sup>''k''</sup>''a'' + ''b''}} will give the result {{math|3<sup>''c''</sup>''a'' + ''d''}}, where {{mvar|d}} is the result of applying the {{mvar|f}} function {{mvar|k}} times to {{mvar|b}}, and {{mvar|c}} is how many increases were encountered during that sequence. For example, for {{math|2<sup>5</sup>''a'' + 1}} there are 3 increases as 1 iterates to 2, 1, 2, 1, and finally to 2 so the result is {{math|3<sup>3</sup>''a'' + 2}}; for {{math|2<sup>2</sup>''a'' + 1}} there is only 1 increase as 1 rises to 2 and falls to 1 so the result is {{math|3''a'' + 1}}. When {{mvar|b}} is {{math|2<sup>''k''</sup> − 1}} then there will be {{mvar|k}} rises and the result will be {{math|3<sup>''k''</sup>''a'' + 3<sup>''k''</sup> − 1}}. The power of 3 multiplying {{mvar|a}} is independent of the value of {{mvar|a}}; it depends only on the behavior of {{mvar|b}}. This allows one to predict that certain forms of numbers will always lead to a smaller number after a certain number of iterations: for example, {{math|4''a'' + 1}} becomes {{math|3''a'' + 1}} after two applications of {{mvar|f}} and {{math|16''a'' + 3}} becomes {{math|9''a'' + 2}} after four applications of {{mvar|f}}. Whether those smaller numbers continue to 1, however, depends on the value of {{mvar|a}}.

===As a tag system===
For the Collatz function in the shortcut form

<math> f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \\ \frac{3n+1}{2} & \text{if } n \equiv 1. \end{cases} \pmod{2}</math>

Hailstone sequences can be computed by the [[Tag system#Example: Computation of Collatz sequences|2-tag system]] with production rules

:{{math|''a'' → ''bc''}}, {{math|''b'' → ''a''}}, {{math|''c'' → ''aaa''}}.

In this system, the positive integer {{mvar|n}} is represented by a string of {{mvar|n}} copies of {{mvar|a}}, and iteration of the tag operation halts on any word of length less than&nbsp;2. (Adapted from De Mol.)

The Collatz conjecture equivalently states that this tag system, with an arbitrary finite string of {{mvar|a}} as the initial word, eventually halts (see ''[[Tag system#Example: Computation of Collatz sequences|Tag system]]'' for a worked example).