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

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

Links

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

Formula

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

Example

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.

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]

Prog

(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
(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), (0<polcoeff(p, i))); }; \\ Antti Karttunen, Nov 29 2024

Crossrefs

One more than A119347.

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

Sequence in context: A347191 A337256 A140434 * A107748 A338506 A353190

Adjacent sequences: A308602 A308603 A308604 * A308606 A308607 A308608

Keyword

nonn

Author

Ivan N. Ianakiev, Jun 10 2019

Extensions

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

Status

approved