A115716 A divide-and-conquer sequence.

1, 1, 3, 1, 3, 1, 11, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 683, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1, 3, 1, 171, 1, 3, 1, 11, 1, 3, 1, 43, 1, 3, 1, 11, 1

Offset: 0

Author

Paul Barry, Jan 29 2006

Keywords

• easy
• nonn

Examples

			G.f. = 1 + x + 3*x^2 + x^3 + 3*x^4 + x^5 + 11*x^6 + x^7 + 3*x^8 + x^9 + ...
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..16381
• R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences , arXiv:math/0307027 [math.CO], 2003.

Crossrefs

Partial sums are A032925.

Row sums of number triangle A115717.

Bisection: A276390.

Cf. A007583, A081294, A091090.

See A276391 for a closely related sequence.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1,
      `if`(n::odd, 1, 4*a(n/2-1)-1))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 07 2016

Mathematica

a[n_] := a[n] = If[n == 0, 1, If[OddQ[n], 1, 4*a[n/2-1]-1]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jan 25 2017, after Alois P. Heinz *)

PARI

{a(n) = if( n<1, n==0, n%2, 1, 4 * a(n/2-1) - 1)}; /* Michael Somos, Sep 07 2016 */

Formula

The g.f. G(x) satisfies G(x)-4*x^2*G(x^2)=(1+2*x)/(1+x). - Argument and offset corrected by Bill Gosper, Sep 07 2016

G.f.: 1/(1-x) + Sum_{k>=0} ((4^k-0^k)/2) *x^(2^(k+1)-2) /(1-x^(2^k)). - corrected by R. J. Mathar, Sep 07 2016

a(n)=A007583(A091090(n+1)-1). - Adapted to new offset by R. J. Mathar, Sep 07 2016

a(0) = 1, a(2*n + 1) = 1 for n>=0. a(2*n + 2) = 4*a(n) - 1 for n>=0. - Michael Somos, Sep 07 2016