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,2

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)

Links

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

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

Example

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

Mathematica

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

Prog

(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 */

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.

Sequence in context: A359811 A283063 A359134 * A284143 A283912 A038185

Adjacent sequences: A074851 A074852 A074853 * A074855 A074856 A074857

Keyword

easy,nonn

Author

Miklos Kristof, Sep 11 2002

Extensions

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

Status

approved