Editing Collatz conjecture (section)

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