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.
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
Keywords
Examples
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.
Links
Programs
-
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
Comments