A049929 a(n) = a(1) + a(2) + ... + a(n-1) - a(m) for n >= 4, where m = 2^(p+1) + 2 - n and p is the unique integer such that 2^p < n-1 <= 2^(p+1), starting with a(1) = 1, a(2) = 3, and a(3) = 4.

1, 3, 4, 5, 12, 20, 41, 83, 168, 254, 550, 1121, 2250, 4507, 9015, 18031, 36064, 54098, 117212, 238932, 480121, 961371, 1923313, 3846922, 7693930, 15387945, 30775932, 61551885, 123103778, 246207563, 492415127, 984830255, 1969660512

Offset

1,2

Comments

Empirical: Lim_{n->infinity} a(n+1)/a(n) = 2. - Iain Fox, Dec 05 2017

Links

Iain Fox, Table of n, a(n) for n = 1..3325

Iain Fox, Table of n, a(n) for n = 1..8000

Formula

a(n) = (Sum_{i=1..n-1} a(i)) - a(2^ceiling(log_2(n-1)) + 2 - n) for n > 3. - Iain Fox, Dec 06 2017

For n > 3, a(n) is the sum of all previous terms except a(A080079(n-2)). - Iain Fox, Dec 13 2017

Example

For n = 4, 2^p < 3 <= 2^(p+1), so p = 1, m = 2^2 + 2 - 4 = 2, and a(n) = a(1) + a(2) + a(3) - a(2) = 1 + 3 + 4 - 3 = 5.
For n = 6, 2^p < 5 <= 2^(p+1), so p = 2, m = 2^3 + 2 - 6 = 4, and a(n) = a(1) + a(2) + a(3) + a(4) + a(5) - a(4) = 1 + 3 + 4 + 5 + 12 - 5 = 20.

Mathematica

Fold[Append[#1, Total@ #1 - #1[[2^Ceiling@ Log2@ #2 + 1 - #2]] ] &, {1, 3, 4}, Range[3, 32]] (* Michael De Vlieger, Dec 06 2017 *)

Prog

(PARI) first(n)= my(res = vector(n), s = 8); res[1]=1; res[2]=3; res[3]=4; for(x=4, n, res[x] = s - res[2*2^logint(x-2, 2)+2-x]; s += res[x]); res; \\ Iain Fox, Dec 05 2017

Crossrefs

Cf. A080079, A049933, A049937, A049945.

Sequence in context: A236244 A141290 A010752 * A262192 A280308 A289121

Adjacent sequences: A049926 A049927 A049928 * A049930 A049931 A049932

Keyword

nonn

Author

Clark Kimberling

Extensions

Name edited by Petros Hadjicostas, Nov 06 2019

Status

approved