A125297 Number of nonempty subsets S of {1,2,3,...,n} such that each member of S divides the sum of all members of S.

1, 2, 4, 5, 6, 9, 10, 12, 15, 17, 18, 24, 25, 27, 31, 34, 35, 42, 43, 59, 62, 63, 64, 82, 83, 84, 88, 97, 98, 146, 147, 153, 156, 157, 158, 185, 186, 187, 189, 314, 315, 337, 338, 343, 430, 431, 432, 491, 492, 495, 497, 500, 501

Offset: 1

Author

John W. Layman, Dec 08 2006

Keywords

• nonn
• more

Comments

a(n) = a(n-1) + the number of subsets of S which meet the criterion that include the element n. - Robert G. Wilson v, Jul 18 2007

From Michael S. Branicky, Jan 12 2022: (Start)

Claim: a(p) = a(p-1) + 1 for p > 3 prime.

Proof: The set {p} meets the criterion. Now, let S be a set containing p and let m be its second largest element. The sum of the elements of S, s <= m*(m+1)/2 + p <= m*p/2 + p <= (m/2+1)*p < m*p for m > 2. For m = 2, s <= p + 3 < 2*p for p > 3. Thus, neither of these s can divide lcm(m, p) = m*p. For m = 1, s = p + 1 and p does not divide it for p >= 2. (End)

Programs

Mathematica

(*first do*) Needs["Combinatorica`"] (*then*) f[n_] := f[n] = Block[{c = 0, k = 0, lmt = 2^(n - 1), lst = Range[n - 1], s = {}}, While[k < lmt + 1, k++; s = NextSubset[lst, s]; t = Join[s, {n}]; If[ Union[ IntegerQ@ # & /@ (Plus @@ t/t)] == {True}, c++ ]]; c]; Do[ Print[{n, f@n}], {n, 28}]; Table[ Sum[ f@i, {i, n}], {n, 28}] (* Robert G. Wilson v, Jul 18 2007 *)

Python

from math import lcm
from sympy import isprime
from functools import cache
@cache
def b(n, s, l): # n, sum, lcm
    if n == 0: return s and s%l == 0
    return b(n-1, s, l) + b(n-1, s + n, lcm(l, n))
def a(n): return b(n, 0, 1)
print([a(n) for n in range(1, 31)]) # Michael S. Branicky, Jan 12 2022

Formula

a(p) = a(p-1) + 1 for prime p > 3 (see proof in Comments). - Michael S. Branicky, Jan 12 2022

Extensions

a(29)-a(41) from Rémy Sigrist, Oct 06 2020

a(42)-a(53) from Michael S. Branicky, Jan 12 2022