A214126 a(2n)=a(n-1)+a(n) and a(2n+1)=a(n+1) for n>=1, with a(0)=a(1)=1.

1, 1, 2, 2, 3, 2, 4, 3, 5, 2, 5, 4, 6, 3, 7, 5, 8, 2, 7, 5, 7, 4, 9, 6, 10, 3, 9, 7, 10, 5, 12, 8, 13, 2, 10, 7, 9, 5, 12, 7, 12, 4, 11, 9, 13, 6, 15, 10, 16, 3, 13, 9, 12, 7, 16, 10, 17, 5, 15, 12, 17, 8, 20, 13, 21, 2, 15, 10, 12, 7, 17, 9, 16, 5, 14, 12

Offset: 0

Author

Alex Ratushnyak, Jul 04 2012

Keywords

• nonn
• easy

Comments

a(2^n) = A000045(n+2), a(2^n-1) = A000045(n+1). - Alois P. Heinz, Jul 06 2012

Examples

			a(2^n+1) = 2 because a(2) = 2 and a(2*n+1) = a(n+1).
		

Links

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

Crossrefs

Cf. A120562: same formula, seed {0,1}, first term removed.

Cf. A082498: same formula, seed {1,0}, first term removed.

Cf. A214127: same formula, seed {1,2}.

Cf. A000045.

Programs

Maple

a:= proc(n) local r;
      a(n):= `if`(n<2, 1, `if`(irem(n, 2, 'r')=0, a(r-1)+a(r), a(r+1)))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jul 06 2012

Mathematica

a[0] = a[1] = 1;
a[n_] := a[n] = If[EvenQ[n], a[n/2-1] + a[n/2], a[(n-1)/2+1]];
Array[a, 100, 0] (* Jean-François Alcover, May 31 2019 *)

Python

a = [1]*(77*2)
for n in range(1,77):
    a[2*n  ]=a[n-1]+a[n]
    a[2*n+1]=a[n+1]
    print(str(a[n-1]),end=',')

Formula

a(0) = a(1) = 1, for n>=1: a(2*n) = a(n-1)+a(n) and a(2*n+1) = a(n+1).