A240951 Maximum number of dividing subsets of a set of n natural numbers.

1, 2, 5, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592

Offset

1,2

Comments

Let A be a set of positive integers and B a subset of A. B is said to divide A if the sum of elements in B divides the sum of elements in A.

Links

Table of n, a(n) for n=1..34.

Index entries for linear recurrences with constant coefficients, signature (2).

Formula

a(n) = 2^(n-1) = A000079(n-1) if n>4.

From Stefano Spezia, May 03 2023: (Start)

O.g.f.: x*(1 + x^2 - 2*x^3)/(1 - 2*x).

E.g.f.: (x^3 + 3*exp(2*x) - 3)/6. (End)

Example

n = 3: only A={k,2k,3k}, where k is a natural number, has 5 dividing subsets.
n = 4: {1, 2, 3, 6} has 8 dividing subsets: {1}, {2}, {3}, {6}, {1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 6}. (Corrected by Stan Wagon, Nov 07 2015)

Mathematica

Join[{1, 2, 5}, NestList[2#&, 8, 40]] (* Harvey P. Dale, Sep 19 2021 *)

Prog

(PARI) a(n)=if(n==3, 5, 2^(n-1)) \\ Charles R Greathouse IV, Nov 06 2015

Crossrefs

Cf. A000079.

Sequence in context: A048139 A357239 A071085 * A280373 A324612 A243189

Adjacent sequences: A240948 A240949 A240950 * A240952 A240953 A240954

Keyword

nonn,easy

Author

Sebastian Raba, Aug 04 2014

Status

approved