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

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)

Links

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

Formula

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

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 *)

Prog

(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

Crossrefs

Sequence in context: A132791 A352320 A352508 * A194469 A143072 A089648

Adjacent sequences: A125294 A125295 A125296 * A125298 A125299 A125300

Keyword

nonn,more

Author

John W. Layman, Dec 08 2006

Extensions

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

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

Status

approved