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

Author

Roger L. Bagula, Mar 15 2006

Keywords

• nonn

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

Crossrefs

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

Programs

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}]

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

Extensions

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