|
|
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.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
|
|
FORMULA
|
|
|
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|