A115716 - OEIS

%I #29 Mar 29 2020 18:33:18

%S 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,

%T 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,

%U 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

%N A divide-and-conquer sequence.

%H Alois P. Heinz, <a href="/A115716/b115716.txt">Table of n, a(n) for n = 0..16381</a>

%H R. Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences </a>, arXiv:math/0307027 [math.CO], 2003.

%F 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

%F 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

%F a(n)=A007583(A091090(n+1)-1). - Adapted to new offset by _R. J. Mathar_, Sep 07 2016

%F 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

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

%p a:= proc(n) option remember; `if`(n=0, 1,

%p       `if`(n::odd, 1, 4*a(n/2-1)-1))

%p     end:

%p seq(a(n), n=0..100);  # _Alois P. Heinz_, Sep 07 2016

%t 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_ *)

%o (PARI) {a(n) = if( n<1, n==0, n%2, 1, 4 * a(n/2-1) - 1)}; /* _Michael Somos_, Sep 07 2016 */

%Y Partial sums are A032925.

%Y Row sums of number triangle A115717.

%Y Bisection: A276390.

%Y Cf. A007583, A081294, A091090.

%Y See A276391 for a closely related sequence.

%K easy,nonn

%O 0,3

%A _Paul Barry_, Jan 29 2006