A004065 Define predecessors of n, P(n), to consist of numbers whose binary representation is obtained from that of n by replacing 10 with 01 or changing a final 1 to a 0; then a(0)=1, a(n) = Sum a(P(n)), n>0.

1, 1, 1, 1, 1, 2, 2, 2, 1, 3, 5, 7, 5, 12, 12, 12, 1, 4, 9, 16, 14, 42, 54, 66, 14, 56, 110, 176, 110, 286, 286, 286, 1, 5, 14, 30, 28, 100, 154, 220, 42, 198, 462, 858, 572, 1716, 2002, 2288, 42, 240, 702, 1560, 1274, 4550, 6552, 8840, 1274, 5824, 12376

Offset: 0

Author

David W. Wilson, Jan 29 2000

Keywords

• nonn
• base

Examples

			E.g. 201 = 11001001, so P(201) = {169, 197, 200}, a(201) = a(169) + a(197) + a(200).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..8191

Crossrefs

Cf. A003121.

Programs

Maple

P:= proc(n) local h, i, m, s, t;
      t:= irem(n, 2, 'm');
      s:= `if`(t=1, {n-1}, {});
      for i from 0 while m>0 do h:= irem(m, 2, 'm');
        if h=1 and t=0 then s:= s union {n- 2^i} fi; t:=h
      od; s
    end:
a:= proc(n) a(n):= `if`(n=0, 1, add(a(k), k=P(n))) end:
seq (a(n), n=0..80);  # Alois P. Heinz, Jul 06 2012

Mathematica

P[n_] := Module[{h, i, m, s, t}, {m, t} = QuotientRemainder[n, 2]; s = If[t == 1, {n-1}, {}]; For[i = 0, m>0, i++, {m, h} = QuotientRemainder[m, 2]; If[h == 1 && t == 0, s = s ~Union~ {n-2^i}]; t = h]; s]; a[n_] := a[n] = If[n == 0, 1, Sum[a[k], {k, P[n]}]]; Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jun 11 2015, after Alois P. Heinz *)

Formula

a(2^n-1) = A003121(n).

Extensions

Entry revised by N. J. A. Sloane, Jun 14 2012