A116526 a(0)=1, a(1)=1, a(n) = 9*a(n/2) for even n >= 2, and a(n) = 8*a((n-1)/2) + a((n+1)/2) for odd n >= 3.

0, 1, 9, 17, 81, 89, 153, 217, 729, 737, 801, 865, 1377, 1441, 1953, 2465, 6561, 6569, 6633, 6697, 7209, 7273, 7785, 8297, 12393, 12457, 12969, 13481, 17577, 18089, 22185, 26281, 59049, 59057, 59121, 59185, 59697, 59761, 60273, 60785, 64881, 64945, 65457, 65969

Offset

0,3

Comments

A 9-divide version of A084230.

The interest this one has is in the prime form of even odd 2^n+1, 2^n.

From Gary W. Adamson, Aug 30 2016: (Start)

Let M =

1, 0, 0, 0, 0, ...

9, 0, 0, 0, 0, ...

8, 1, 0, 0, 0, ...

0, 9, 0, 0, 0, ...

0, 8, 1, 0, 0, ...

0, 0, 9, 0, 0, ...

0, 0, 8, 1, 0, ...

...

Then M^k converges to a single nonzero column giving the sequence.

The sequence divided by its aerated variant is (1, 9, 8, 0, 0, 0, ...). (End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..16383 (first 2501 terms from G. C. Greubel)

H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62, 19-22, 1977.

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 33.

Eric Weisstein's World of Mathematics, Stolarsky-Harborth Constant

Formula

a(n) = Sum_{k=0..n-1} 8^wt(k), where wt = A000120. - Mike Warburton, Mar 14 2019

a(n) = Sum_{k=0..floor(log_2(n))} 8^k*A360189(n-1,k). - Alois P. Heinz, Mar 06 2023

Maple

a:=proc(n) if n=0 then 0 elif n=1 then 1 elif n mod 2 = 0 then 9*a(n/2) else 8*a((n-1)/2)+a((n+1)/2) fi end: seq(a(n), n=0..45);

Mathematica

b[0] := 0; b[1] := 1; b[n_?EvenQ] := b[n] = 9*b[n/2]; b[n_?OddQ] := b[n] = 8*b[(n - 1)/2] + b[(n + 1)/2]; a = Table[b[n], {n, 1, 25}]

Crossrefs

Cf. A000120, A006046, A077465, A130665, A116520, A130667, A116522, A161342, A116525, A360189.

Sequence in context: A118527 A193663 A166705 * A197396 A015443 A253212

Adjacent sequences: A116523 A116524 A116525 * A116527 A116528 A116529

Keyword

nonn

Author

Roger L. Bagula, Mar 15 2006

Extensions

Edited by N. J. A. Sloane, Apr 16 2006

Status

approved