OFFSET
1,6
COMMENTS
These count the "starter sets" employed by a simple backtracking algorithm that computes A317624. See the PARI program dated Sep 08-10 2018 under that entry.
LINKS
EXAMPLE
For n = 45, there exists the following subsets of its divisors larger than one (3, 5, 9, 15, 45) that satisfy the condition that the least common multiple of the members is 45, and the sum does not exceed 45: (45), (3, 9, 15), (3, 5, 9, 15), (3, 5, 9), (5, 9), (9, 15) and (5, 9, 15), altogether seven subsets, thus a(45) = 7.
PROG
(PARI)
A318670(n) = if(1==n, 1, my(ds=(divisors(n)[2..numdiv(n)]), subsets = select(v -> ((vecsum(v)<=n)&&(n==lcm(v))), powerset(ds))); length(subsets)); \\ A memory-hog implementation.
powerset(v) = { my(siz=2^length(v), pv=vector(siz)); for(i=0, siz-1, pv[i+1] = choosebybits(v, i)); pv; };
choosebybits(v, m) = { my(s=vector(hammingweight(m)), i=j=1); while(m>0, if(m%2, s[j] = v[i]; j++); i++; m >>= 1); s; }; \\ Antti Karttunen, Sep 08 2018
(PARI)
\\ A better program:
strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);
A318670aux(orgn, n, parts, from=1, ss=List([])) = { my(k = #parts, s=0, newss); if(lcm(Vec(ss))==orgn, s++); for(i=from, k, if(parts[i]<=n, newss = List(ss); listput(newss, parts[i]); s += A318670aux(orgn, n-parts[i], parts, i+1, newss))); (s) };
A318670(n) = if(1==n, n, A318670aux(n, n, strong_divisors_reversed(n))); \\ Antti Karttunen, Sep 08 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen and David A. Corneth, Sep 08 2018
STATUS
approved