cp's OEIS Frontend

A308605 Number of distinct subset sums of the subsets of the set of divisors of n. Here 0 (as the sum of an empty subset) is included in the count.

%I A308605 #40 Nov 29 2024 15:07:02
%S A308605 2,4,4,8,4,13,4,16,8,16,4,29,4,16,16,32,4,40,4,43,16,16,4,61,8,16,16,
%T A308605 57,4,73,4,64,16,16,16,92,4,16,16,91,4,97,4,64,56,16,4,125,8,64,16,64,
%U A308605 4,121,16,121,16,16,4,169,4,16,60,128,16,145,4,64,16,143,4,196,4,16,64,64,16,169,4,187,32,16,4,225
%N A308605 Number of distinct subset sums of the subsets of the set of divisors of n. Here 0 (as the sum of an empty subset) is included in the count.
%C A308605 Conjecture: When the terms are sorted and the duplicates deleted a supersequence of A030058 is obtained. Note that A030058 is a result of the same operation applied to A030057.
%C A308605 a(p^k) = 2^(k+1) if p is prime, and a(n) = 2n+1 if n is an even perfect number. - _David Radcliffe_, Dec 22 2022
%H A308605 Antti Karttunen, <a href="/A308605/b308605.txt">Table of n, a(n) for n = 1..10000</a>
%F A308605 a(n) = 1 + A119347(n). - _Rémy Sigrist_, Jun 10 2019
%e A308605 The subsets of the set of divisors of 6 are {{},{1},{2},{3},{6},{1,2},{1,3},{1,6},{2,3},{2,6},{3,6},{1,2,3},{1,2,6},{1,3,6},{2,3,6},{1,2,3,6}}, with the following sums {0,1,2,3,6,3,4,7,5,8,9,6,9,10,11,12}, of which 13 are distinct. Therefore, a(6)=13.
%p A308605 A308605 := proc(n)
%p A308605     # set of the divisors
%p A308605     dvs := numtheory[divisors](n) ;
%p A308605     # set of all the subsets of the divisors
%p A308605     pdivs := combinat[powerset](dvs) ;
%p A308605     # the set of the sums in subsets of divisors
%p A308605     dvss := {} ;
%p A308605     # loop over all subsets of divisors
%p A308605     for s in pdivs do
%p A308605         # compute sum over entries of the subset
%p A308605         sps := add(d,d=s) ;
%p A308605         # add sum to the realized set of sums
%p A308605         dvss := dvss union {sps} ;
%p A308605     end do:
%p A308605     # count number of distinct entries (distinct sums)
%p A308605     nops(dvss) ;
%p A308605 end proc:
%p A308605 seq(A308605(n),n=1..20) ; # _R. J. Mathar_, Dec 20 2022
%t A308605 f[n_]:=Length[Union[Total/@Subsets[Divisors[n]]]]; f/@Range[100]
%o A308605 (Python)
%o A308605 from sympy import divisors
%o A308605 def a308605(n):
%o A308605     s = set([0])
%o A308605     for d in divisors(n):
%o A308605         s = s.union(set(x + d for x in s))
%o A308605     return len(s) # _David Radcliffe_, Dec 22 2022
%o A308605 (PARI) A308605(n) = { my(c=[0]); fordiv(n,d, c = Set(concat(c,vector(#c,i,c[i]+d)))); (#c); }; \\ (after _Chai Wah Wu_'s Python-code in A119347, but see also above) - _Antti Karttunen_, Nov 29 2024
%o A308605 (PARI) A308605(n) = { my(p=1); fordiv(n, d, p *= (1 + 'x^d)); sum(i=0,poldegree(p),(0<polcoeff(p, i))); }; \\ _Antti Karttunen_, Nov 29 2024
%Y A308605 One more than A119347.
%Y A308605 Cf. A030057, A030058, A083207 (positions of odd terms), A179527 (parity of terms).
%K A308605 nonn
%O A308605 1,1
%A A308605 _Ivan N. Ianakiev_, Jun 10 2019
%E A308605 Definition clarified and more terms added by _Antti Karttunen_, Nov 29 2024