cp's OEIS Frontend

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.

%I A125297 #28 Jan 12 2022 20:57:57
%S A125297 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,
%T A125297 84,88,97,98,146,147,153,156,157,158,185,186,187,189,314,315,337,338,
%U A125297 343,430,431,432,491,492,495,497,500,501
%N 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.
%C A125297 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
%C A125297 From _Michael S. Branicky_, Jan 12 2022: (Start)
%C A125297 Claim: a(p) = a(p-1) + 1 for p > 3 prime.
%C A125297 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)
%F A125297 a(p) = a(p-1) + 1 for prime p > 3 (see proof in Comments). - _Michael S. Branicky_, Jan 12 2022
%t A125297 (*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 *)
%o A125297 (Python)
%o A125297 from math import lcm
%o A125297 from sympy import isprime
%o A125297 from functools import cache
%o A125297 @cache
%o A125297 def b(n, s, l): # n, sum, lcm
%o A125297     if n == 0: return s and s%l == 0
%o A125297     return b(n-1, s, l) + b(n-1, s + n, lcm(l, n))
%o A125297 def a(n): return b(n, 0, 1)
%o A125297 print([a(n) for n in range(1, 31)]) # _Michael S. Branicky_, Jan 12 2022
%K A125297 nonn,more
%O A125297 1,2
%A A125297 _John W. Layman_, Dec 08 2006
%E A125297 a(29)-a(41) from _Rémy Sigrist_, Oct 06 2020
%E A125297 a(42)-a(53) from _Michael S. Branicky_, Jan 12 2022