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

Author

Sebastian Raba, Aug 04 2014

Keywords

• nonn
• easy

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.

Examples

			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)
		

Links

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

Crossrefs

Cf. A000079.

Programs

Mathematica

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

PARI

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

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)