A065205 Number of subsets of proper divisors of n that sum to n.

0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 5, 0, 0, 0, 1, 0, 3, 0, 0, 0, 0, 0, 7, 0, 0, 0, 3, 0, 2, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 3, 0, 2, 0, 0, 0, 34, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 1, 0, 6, 0, 0, 0, 25, 0, 0, 0, 1, 0, 23, 0, 0, 0, 0, 0, 21, 0, 0, 0, 2

Offset: 1

Author

Jonathan Ayres (jonathan.ayres(AT)btinternet.com), Oct 19 2001

Keywords

• nonn

Comments

Deficient and weird numbers have a(n) = 0, perfect numbers and others (see A064771) have a(n) = 1.

Number of partitions of n into distinct proper divisors of n; a(A136447(n)) = 0; a(A005835(n)) > 0; a(A064771(n)) = 1. - Reinhard Zumkeller, Jan 21 2013

Examples

			a(20) = 1 because {1, 4, 5, 10} is the only subset of proper divisors of 20 that sum to 20.
a(24) = 5 because there are five different subsets we can use to sum up to 24: {1, 2, 3, 4, 6, 8}, {1, 2, 3, 6, 12}, {1, 3, 8, 12}, {2, 4, 6, 12}, {4, 8, 12}.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Crossrefs

Cf. A064771, A005835.

Cf. A065218 for records.

Cf. A027751, A210442, A211110, A033630.

Programs

Haskell

a065205 n = p (a027751_row n) n where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jan 21 2013

Mathematica

a[n_] := (dd = Most[ Divisors[n] ]; cc = Array[c, Length[dd]]; Length[ {ToRules[ Reduce[ And @@ (0 <= # <= 1 &) /@ cc && dd . cc == n, cc, Integers]]}]); Table[ a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 23 2012 *)

PARI

a(n,s,d)={s || (s=sigma(n)-n) || return; d||d=vecextract(divisors(n),"^-1"); while(d[#d]>n, s-=d[#d]; d=d[1..-2]); s<=n && return(s==n); if( n>d[#d], a(n-d[#d],s-d[#d],d[1..-2]), 1)+a(n,s-d[#d],d[1..-2])} \\ M. F. Hasler, May 11 2015

Formula

a(n) = A033630(n) - 1.

Extensions

More terms and additional comments from Jud McCranie, Oct 21 2001