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.

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, 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, 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

Offset: 1

Author

Ivan N. Ianakiev, Jun 10 2019

Keywords

• nonn

Comments

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.

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

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000

Crossrefs

One more than A119347.

Cf. A030057, A030058, A083207 (positions of odd terms), A179527 (parity of terms).

Programs

Maple

A308605 := proc(n)
    # set of the divisors
    dvs := numtheory[divisors](n) ;
    # set of all the subsets of the divisors
    pdivs := combinat[powerset](dvs) ;
    # the set of the sums in subsets of divisors
    dvss := {} ;
    # loop over all subsets of divisors
    for s in pdivs do
        # compute sum over entries of the subset
        sps := add(d,d=s) ;
        # add sum to the realized set of sums
        dvss := dvss union {sps} ;
    end do:
    # count number of distinct entries (distinct sums)
    nops(dvss) ;
end proc:
seq(A308605(n),n=1..20) ; # R. J. Mathar, Dec 20 2022

Mathematica

f[n_]:=Length[Union[Total/@Subsets[Divisors[n]]]]; f/@Range[100]

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

PARI

A308605(n) = { my(p=1); fordiv(n, d, p *= (1 + 'x^d)); sum(i=0,poldegree(p),(0Antti Karttunen, Nov 29 2024

Python

from sympy import divisors
def a308605(n):
    s = set([0])
    for d in divisors(n):
        s = s.union(set(x + d for x in s))
    return len(s) # David Radcliffe, Dec 22 2022

Formula

a(n) = 1 + A119347(n). - Rémy Sigrist, Jun 10 2019

Extensions

Definition clarified and more terms added by Antti Karttunen, Nov 29 2024