login
A115716
A divide-and-conquer sequence.
5
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,3
LINKS
R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences , arXiv:math/0307027 [math.CO], 2003.
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
EXAMPLE
G.f. = 1 + x + 3*x^2 + x^3 + 3*x^4 + x^5 + 11*x^6 + x^7 + 3*x^8 + x^9 + ...
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 *)
PROG
(PARI) {a(n) = if( n<1, n==0, n%2, 1, 4 * a(n/2-1) - 1)}; /* Michael Somos, Sep 07 2016 */
CROSSREFS
Partial sums are A032925.
Row sums of number triangle A115717.
Bisection: A276390.
See A276391 for a closely related sequence.
Sequence in context: A363533 A146431 A212183 * A079412 A356655 A306861
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Jan 29 2006
STATUS
approved