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

1, 3, 5, 13, 17, 57, 65, 209, 321, 801, 1025, 3905, 4097, 12417, 21505, 53505, 65537, 233985, 262145, 885761, 1327105, 3147777, 4194305, 16060417, 17825793, 50339841, 84148225, 220217345, 268435457, 990937089, 1073741825, 3506503681

Offset: 1

Author

Miklos Kristof, Sep 11 2002

Keywords

• easy
• nonn

Comments

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

A055895 = 2*A034729.

If p is a prime, then a(p) = A034729(p) = 2^(p-1)+1.

From Gus Wiseman, Jul 14 2020: (Start)

Number of ways to tile a rectangle of size n using horizontal strips. Also the number of ways to choose a composition of each part of a constant partition of n. The a(0) = 1 through a(5) = 17 splittings are:

() (1) (2) (3) (4) (5)

(1,1) (1,2) (1,3) (1,4)

(1),(1) (2,1) (2,2) (2,3)

(1,1,1) (3,1) (3,2)

(1),(1),(1) (1,1,2) (4,1)

(1,2,1) (1,1,3)

(2,1,1) (1,2,2)

(2),(2) (1,3,1)

(1,1,1,1) (2,1,2)

(1,1),(2) (2,2,1)

(2),(1,1) (3,1,1)

(1,1),(1,1) (1,1,1,2)

(1),(1),(1),(1) (1,1,2,1)

(1,2,1,1)

(2,1,1,1)

(1,1,1,1,1)

(1),(1),(1),(1),(1)

(End)

Examples

			Divisors of 6 = 1,2,3,6 and 6-1 = 5, 6-2 = 4, 6-3 = 3, 6-6 = 0. a(6) = 2^5 + 2^4 + 2^3 + 2^0 = 32 + 16 + 8 + 1 = 57.
G.f. = x + 3*x^2 + 5*x^3 + 13*x^4 + 17*x^5 + 57*x^6 + 65*x^7 + ...
a(14) = 1 + 2^7 + 2^12 + 2^13 = 12417. - _Gus Wiseman_, Jun 20 2018
		

Links

• Gus Wiseman, Table of n, a(n) for n = 1..32

Crossrefs

Cf. A055895, A034729.

Cf. A080267.

Cf. A051731.

The version looking at lengths instead of sums is A101509.

The strictly increasing (or strictly decreasing) version is A304961.

Starting with a partition gives A317715.

Starting with a strict partition gives A318683.

Requiring distinct instead of equal sums gives A336127.

Starting with a strict composition gives A336130.

Partitions of partitions are A001970.

Splittings of compositions are A133494.

Splittings of partitions are A323583.

Cf. A006951, A063834, A075900, A279787, A305551, A316245, A323433, A336128.

Programs

Mathematica

a[ n_] := If[ n < 1, 0, Sum[ 2^(n - d), {d, Divisors[n]}]] (* Michael Somos, Mar 28 2013 *)

PARI

a(n)=if(n<1,0,2^n*polcoeff(sum(k=1,n,2/(2-x^k),x*O(x^n)),n))

PARI

a(n) = sumdiv(n,d, 2^(n-d) ); /* Joerg Arndt, Mar 28 2013 */

Formula

G.f.: 2^n times coefficient of x^n in Sum_{k>=1} x^k/(2-x^k). - Benoit Cloitre, Apr 21 2003; corrected by Joerg Arndt, Mar 28 2013

G.f.: Sum_{k>0} 2^(k-1)*x^k/(1-2^(k-1)*x^k). - Vladeta Jovovic, Jun 24 2003

G.f.: Sum_{n>=1} a*z^n/(1-a*z^n) (generalized Lambert series) where z=2*x and a=1/2. - Joerg Arndt, Jan 30 2011

Triangle A051731 mod 2 converted to decimal. - Philippe Deléham, Oct 04 2003

G.f.: Sum_{k>0} 1 / (2 / (2*x)^k - 1). - Michael Somos, Mar 28 2013

Extensions

a(14) corrected from 9407 to 12417 by Gus Wiseman, Jun 20 2018