A193279 Number of distinct sums of distinct proper divisors of n.

0, 1, 1, 3, 1, 6, 1, 7, 3, 7, 1, 16, 1, 7, 7, 15, 1, 21, 1, 22, 7, 7, 1, 36, 3, 7, 7, 28, 1, 42, 1, 31, 7, 7, 7, 55, 1, 7, 7, 50, 1, 54, 1, 31, 27, 7, 1, 76, 3, 31, 7, 31, 1, 66, 7, 64, 7, 7, 1, 108, 1, 7, 29, 63, 7, 78, 1, 31, 7, 72, 1, 123, 1, 7, 31, 31

Offset

1,4

Comments

a(n)=1 if and only if n is prime.

a(n)=n-1 if n is a power of 2.

a(n)=n if n is an even perfect number (is the converse true?)

Note: the count excludes an empty subset of proper divisors that would give 0 as a sum. - Antti Karttunen, Mar 07 2018

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..719 from Antti Karttunen)

Maple

with(linalg): a:=proc(n) local dl, t: dl:=convert(numtheory[divisors](n) minus {n}, list): t:=nops(dl): return nops({seq(innerprod(dl, convert(2^t+i, base, 2)[1..t]), i=1..2^t-1)}): end: seq(a(n), n=1..76); # Nathaniel Johnston, Jul 23 2011

Mathematica

a[n_] := Module[{d = Most @ Divisors[n], x}, Count[CoefficientList[Product[1 + x^i, {i, d}], x], _?(# > 0 &)] - 1]; Array[a, 100] (* Amiram Eldar, Jun 13 2020 *)

Prog

(PARI)
allocatemem(2^31);
powerset_without_emptyset(v) = { my(siz=(2^length(v))-1, pv=vector(siz)); for(i=1, siz, pv[i] = 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; };
A193279(n) = if(1==n, 0, my(pds = (divisors(n)[1..(numdiv(n)-1)]), subs = powerset_without_emptyset(pds)); length(vecsort(vector(#subs, i, vecsum(subs[i])) , , 8))); \\ Antti Karttunen, Mar 07 2018
(PARI)
\\ The following version does not need huge amounts of memory:
A193279(n) = if(1==n, 0, my(pds = (divisors(n)[1..(numdiv(n)-1)]), maxsum = vecsum(pds), sums = vector(maxsum), psetsiz = (2^length(pds))-1, k = 0, s); for(i=1, psetsiz, s = vecsum(choosebybits(pds, i)); if(!sums[s], k++; sums[s]++)); (k)); \\ Antti Karttunen, Mar 07 2018

Crossrefs

Cf. A193280.

Cf. A119347 (allows also n to be included in the sums).

Sequence in context: A066446 A069625 A111614 * A076889 A134689 A248029

Adjacent sequences: A193276 A193277 A193278 * A193280 A193281 A193282

Keyword

nonn

Author

Michael Engling, Jul 20 2011

Status

approved