cp's OEIS Frontend

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.

%I A318670 #19 Sep 12 2018 10:49:03
%S A318670 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,
%T A318670 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,
%U A318670 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
%N 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.
%C A318670 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.
%H A318670 Antti Karttunen, <a href="/A318670/b318670.txt">Table of n, a(n) for n = 1..1259</a>
%H A318670 <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>
%F A318670 a(n) <= A069626(n).
%F A318670 For all n >= 1:
%F A318670 a(A000961(n)) = 1.
%F A318670 a(A006881(n)) = 2.
%e A318670 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.
%o A318670 (PARI)
%o A318670 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.
%o A318670 powerset(v) = { my(siz=2^length(v),pv=vector(siz)); for(i=0,siz-1,pv[i+1] = choosebybits(v,i)); pv; };
%o A318670 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
%o A318670 (PARI)
%o A318670 \\ A better program:
%o A318670 strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);
%o A318670 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) };
%o A318670 A318670(n) = if(1==n,n,A318670aux(n,n,strong_divisors_reversed(n))); \\ _Antti Karttunen_, Sep 08 2018
%Y A318670 Cf. A069626, A317624.
%K A318670 nonn
%O A318670 1,6
%A A318670 _Antti Karttunen_ and _David A. Corneth_, Sep 08 2018