A079954 Partial sums of A030301.

0, 1, 2, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42

Offset

1,3

Links

Kevin Ryde, Table of n, a(n) for n = 1..8192

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. 49-50.

Formula

a(n) = (n - 1 - (2/3)*(4^e_4-1) - (-1)^e_2*(n - 1 - 2*(4^e_4-1)))/2 where e_4 = floor(log_4(n)) and e_2 = floor(log_2(n)) = floor(log_4(n^2)). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 22 2003

a(n) = n - A079947(n). Let k=A000523(n), then a(n) = A000975(k) if k even, or a(n) = n - A000975(k) if k odd. - Kevin Ryde, Jul 23 2019

Mathematica

Accumulate@ Flatten@ Table[1 - Mod[n, 2], {n, 7}, {2^(n - 1)}] (* Michael De Vlieger, Oct 29 2022 *)

Prog

(PARI) a(n) = my(k=logint(n, 2), p=(2<<k)\3); if(bittest(k, 0), n-p, p); /* Kevin Ryde, Jul 23 2019 */
(Magma) [&+[Floor(Log(k)/Log(2)) mod 2:k in [1..n]]:n in [1..75]]; // Marius A. Burtea, Oct 25 2019
(Python)
def A079954(n): return ((1<<k)-2)//3 if (k:=n.bit_length())&1 else n-((1<<k)-1)//3 # Chai Wah Wu, Jan 30 2023

Crossrefs

Cf. A000523, A000975, A030301, A079947.

Sequence in context: A109368 A046774 A029105 * A114968 A079629 A029116

Adjacent sequences: A079951 A079952 A079953 * A079955 A079956 A079957

Keyword

nonn

Author

N. J. A. Sloane, Feb 22 2003

Status

approved