Properties of [recursive] sequences

Sequence (d) is given by

f[n_] := (n + g[IntegerDigits[n, 2]])/2

g[{1 ..}] = 1; g[{1, 0 ..}] = 0

g[{1, s__}] := 1 + g[IntegerDigits[FromDigits[{s}, 2] + 1, 2]]

The list of elements in the sequence up to value m is given by

Flatten[Table[Table[n, {IntegerExponent[n, 2] + 1}], {n, m}]]

The differences between the first 2 (2^k-1) of these elements is

Nest[Replace[#, {x___}  {x, 1, x, 0}]&, {}, k]

The largest n for which f[n]  m is given by 2m + 1 - DigitCount[m, 2, 1] or IntegerExponent[(2m)!, 2] + 1 (this satisfies h[1] = 2; h[m_] := h[Floor[m/2]] + m).

The form of sequence (c) is similar to that obtained from concatenation numbers on page 913. Hump m in the picture of sequence (c) shown is given by

FoldList[Plus, 0, Flatten[Nest[Delete[NestList[Rest, #, Length[#] - 1], 2]&, Append[Table[1, {m}], 0], m]] - 1/2]

The first 2^m elements in the sequence can also be generated in terms of reordered base 2 digit sequences by

FoldList[Plus, 1, Map[Last[Last[#]]&, Sort[Table[{Length[#], Apply[Plus, #], 1 - #}& [IntegerDigits[i, 2]], {i, 2^m}]]]]

Note that the positive and negative fluctuations in sequence (f) are not completely random: although the probability for individual fluctuations in each direction seems to be the same, the probability for two positive fluctuations in a row is smaller than for two negative fluctuations in a row.

In the sequences discussed here, f[n_] always has the form f[p[n]] + f[q[n]]. The plots below show p[n] and q[n] as a function of n.

The process of evaluating f[n] for a particular n can be thought of as yielding a tree where each node is a particular f[k] which has two successors, f[p[k]] and f[q[k]]. The distinct nodes reached starting from f[12] for sequence (f) are then for example {{12}, {3, 7}, {1, 2, 4}, {1, 2}, {1}}. The total lengths of these chains (corresponding to the depth of the evaluation tree) seem to increase roughly like Log[n] for all the rules on this page. For the Fibonacci sequence, it is instead n - 1. The maximum number of distinct nodes at any level in the tree has large fluctuations but its peaks seem to increase roughly linearly for all the rules on this page (in the Fibonacci case it is Ceiling[n/2]).