A268235 a(n) = Sum_{k=1..n} floor(n/k)*2^(k-1).

1, 4, 9, 20, 37, 76, 141, 280, 541, 1072, 2097, 4192, 8289, 16548, 32953, 65860, 131397, 262764, 524909, 1049736, 2098381, 4196560, 8390865, 16781696, 33558929, 67117460, 134226585, 268452580, 536888037, 1073775900, 2147517725, 4295034280, 8590002605, 17180002736, 34359872001, 68719743792

Offset

1,2

Comments

This is the "floor transform" of the powers of 2.

Links

Matthew House, Table of n, a(n) for n = 1..3305

Formula

a(n) ~ 2^n. - Vaclav Kotesovec, May 28 2021

From Seiichi Manyama, May 29 2021: (Start)

a(n) = Sum_{k=1..n} Sum_{d|k} 2^(d-1).

G.f.: (1/(1 - x)) * Sum_{k>=1} x^k/(1 - 2*x^k).

G.f.: (1/(1 - x)) * Sum_{k>=1} 2^(k-1) * x^k/(1 - x^k). (End)

a(n) = Sum_{k=1..n} (2^floor(n/k) - 1). - Ridouane Oudra, Feb 03 2023

Maple

# floor transform of a sequence
ft:=proc(a) local b, n, j, k; b:=[];
for n from 1 to nops(a) do j:=add(a[k]*floor(n/k), k=1..n); b:=[op(b), j]; od;
b; end:
ft([seq(2^i, i=0..50)]);

Mathematica

Table[Sum[Floor[n/k] 2^(k - 1), {k, n}], {n, 36}] (* Michael De Vlieger, Feb 12 2017 *)

Prog

(PARI) a(n) = sum(k=1, n, (n\k)*2^(k-1)); \\ Michel Marcus, Feb 11 2017
(PARI) a(n) = sum(k=1, n, sumdiv(k, d, 2^(d-1))); \\ Seiichi Manyama, May 29 2021
(PARI) my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, x^k/(1-2*x^k))/(1-x)) \\ Seiichi Manyama, May 29 2021
(PARI) my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, 2^(k-1)*x^k/(1-x^k))/(1-x)) \\ Seiichi Manyama, May 29 2021
(Magma)
A268235:= func< n | (&+[Floor(n/j)*2^(j-1): j in [1..n]]) >;
[A268235(n): n in [1..40]]; // G. C. Greubel, Jun 27 2024
(SageMath)
def A268235(n): return sum((n//j)*2^(j-1) for j in range(1, n+1))
[A268235(n) for n in range(1, 41)] # G. C. Greubel, Jun 27 2024
(Python)
def A268235(n):
    c, j = 0, 1
    while j <= n:
        k = n//j
        m = n//k
        c += k*((1<<m)-(1<<j-1))
        j = m+1
    return c # Chai Wah Wu, May 12 2026

Crossrefs

First differences give A034729.

Cf. A000079.

Sums of the form Sum_{k=1..n} q^(k-1)*floor(n/k): A344820 (q=-n), A344819 (q=-4), A344818 (q=-3), A344817 (q=-2), A059851 (q=-1), A006218 (q=1), this sequence (q=2), A344814 (q=3), A344815 (q=4), A344816 (q=5), A332533 (q=n).

Sequence in context: A009910 A060494 A049748 * A192956 A023607 A117074

Adjacent sequences: A268232 A268233 A268234 * A268236 A268237 A268238

Keyword

nonn

Author

Benoit Cloitre and N. J. A. Sloane, Feb 05 2016

Extensions

Definition corrected by Matthew House, Feb 11 2017

Status

approved