login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A318670
Number of subsets of divisors of n whose least common multiple is n and the sum does not exceed n. For n > 1, 1 is excluded from the set of divisors.
4
1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 5, 1, 2, 2, 1, 1, 6, 1, 6, 2, 2, 1, 17, 1, 2, 1, 7, 1, 34, 1, 1, 2, 2, 2, 44, 1, 2, 2, 23, 1, 36, 1, 7, 7, 2, 1, 65, 1, 7, 2, 7, 1, 21, 2, 25, 2, 2, 1, 471, 1, 2, 7, 1, 2, 39, 1, 7, 2, 44, 1, 355, 1, 2, 7, 7, 2, 39, 1, 89, 1, 2, 1, 531, 2, 2, 2, 27, 1, 559, 2, 7, 2, 2, 2, 257, 1, 7, 7, 61, 1, 39, 1, 28, 46
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.
FORMULA
a(n) <= A069626(n).
For all n >= 1:
a(A000961(n)) = 1.
a(A006881(n)) = 2.
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
Sequence in context: A351945 A351943 A114717 * A323409 A080388 A330742
KEYWORD
nonn
AUTHOR
STATUS
approved