|
%I #26 Jun 13 2020 07:57:58
%S 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,
%T 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,
%U 108,1,7,29,63,7,78,1,31,7,72,1,123,1,7,31,31
%N Number of distinct sums of distinct proper divisors of n.
%C a(n)=1 if and only if n is prime.
%C a(n)=n-1 if n is a power of 2.
%C a(n)=n if n is an even perfect number (is the converse true?)
%C Note: the count excludes an empty subset of proper divisors that would give 0 as a sum. - _Antti Karttunen_, Mar 07 2018
%H Amiram Eldar, <a href="/A193279/b193279.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..719 from Antti Karttunen)
%p 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
%t 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 *)
%o (PARI)
%o allocatemem(2^31);
%o powerset_without_emptyset(v) = { my(siz=(2^length(v))-1,pv=vector(siz)); for(i=1,siz,pv[i] = choosebybits(v,i)); pv; };
%o 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; };
%o 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
%o (PARI)
%o \\ The following version does not need huge amounts of memory:
%o 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
%Y Cf. A193280.
%Y Cf. A119347 (allows also n to be included in the sums).
%K nonn
%O 1,4
%A _Michael Engling_, Jul 20 2011
|
