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

1, 3, 5, 11, 17, 39, 65, 139, 261, 531, 1025, 2095, 4097, 8259, 16405, 32907, 65537, 131367, 262145, 524827, 1048645, 2098179, 4194305, 8390831, 16777233, 33558531, 67109125, 134225995, 268435457, 536887863, 1073741825, 2147516555, 4294968325, 8590000131

Offset: 1

Author

Erich Friedman

Keywords

• nonn

Comments

Dirichlet convolution of b_n=1 with c_n = 2^(n-1).

Equals row sums of triangle A143425, & inverse Möbius transform (A051731) of [1, 2, 4, 8, ...]. - Gary W. Adamson, Aug 14 2008

Number of constant multiset partitions of normal multisets of size n, where a multiset is normal if it spans an initial interval of positive integers. - Gus Wiseman, Sep 16 2018

Examples

			From _Gus Wiseman_, Sep 16 2018: (Start)
The a(4) = 11 constant multiset partitions:
  (1)(1)(1)(1)
    (11)(11)
    (12)(12)
     (1111)
     (1222)
     (1122)
     (1112)
     (1233)
     (1223)
     (1123)
     (1234)
(End)
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000005, A002033, A003238, A008480, A018783, A047968, A051731.

Cf. A052409, A055895, A078392, A143425, A215366, A245282, A248906.

Cf. A289508.

Sums of the form Sum_{d|n} q^(d-1): this sequence (q=2), A034730 (q=3), A113999 (q=10), A339684 (q=4), A339685 (q=5), A339686 (q=6), A339687 (q=7), A339688 (q=8), A339689 (q=9).

Programs

Magma

A034729:= func< n | (&+[2^(d-1): d in Divisors(n)]) >;
[A034729(n): n in [1..40]]; // G. C. Greubel, Jun 26 2024

Maple

seq(add(2^(k-1),k=numtheory:-divisors(n)), n = 1 .. 100); # Robert Israel, Aug 22 2014

Mathematica

Rest[CoefficientList[Series[Sum[x^k/(1-2*x^k),{k,1,30}],{x,0,30}],x]] (* Vaclav Kotesovec, Sep 08 2014 *)

PARI

A034729(n) = sumdiv(n,k,2^(k-1)) \\ Michael B. Porter, Mar 11 2010

PARI

{a(n)=polcoeff(sum(m=1,n,2^(m-1)*x^m/(1-x^m +x*O(x^n))),n)}
for(n=1,40,print1(a(n),", ")) \\ Paul D. Hanna, Aug 21 2014

PARI

{a(n)=local(A=x+x^2);A=sum(m=1,n,x^m*sumdiv(m,d,1/(1 - x^(m/d) +x*O(x^n))^d) );polcoeff(A,n)}
for(n=1,40,print1(a(n),", ")) \\ Paul D. Hanna, Aug 21 2014

Python

from sympy import divisors
def A034729(n): return sum(1<<(d-1) for d in divisors(n,generator=True)) # Chai Wah Wu, Jul 15 2022

SageMath

def A034729(n): return sum(2^(k-1) for k in (1..n) if (k).divides(n))
[A034729(n) for n in range(1,41)] # G. C. Greubel, Jun 26 2024

Formula

G.f.: Sum_{n>0} x^n/(1-2*x^n). - Vladeta Jovovic, Nov 14 2002

a(n) = 1/2 * A055895(n). - Joerg Arndt, Aug 14 2012

G.f.: Sum_{n>=1} 2^(n-1) * x^n / (1 - x^n). - Paul D. Hanna, Aug 21 2014

G.f.: Sum_{n>=1} x^n * Sum_{d|n} 1/(1 - x^d)^(n/d). - Paul D. Hanna, Aug 21 2014

a(n) ~ 2^(n-1). - Vaclav Kotesovec, Sep 09 2014

a(n) = Sum_{k in row n of A215366} A008480(k) * A000005(A289508(k)). - Gus Wiseman, Sep 16 2018

a(n) = Sum_{c is a composition of n} A000005(gcd(c)). - Gus Wiseman, Sep 16 2018