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