information:extraction
Time–space tradeoff

The section As a parity sequence above gives a way to speed up simulation of the sequence. To jump ahead k steps on each iteration (using the f function from that section), break up the current number into two parts, b (the k least significant bits, interpreted as an integer), and a (the rest of the bits as an integer). The result of jumping ahead k is given by

The values of c (or better 3) and d can be precalculated for all possible k -bit numbers b, where d (b, k) is the result of applying the f function k times to b, and c (b, k) is the number of odd numbers encountered on the way. For example, if k = 5, one can jump ahead 5 steps on each iteration by separating out the 5 least significant bits of a number and using

This requires 2 precomputation and storage to speed up the resulting calculation by a factor of k, a space–time tradeoff.