cp's OEIS Frontend

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

%I A065205 #31 Jan 11 2020 06:38:58
%S A065205 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,
%T A065205 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,
%U A065205 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
%N A065205 Number of subsets of proper divisors of n that sum to n.
%C A065205 Deficient and weird numbers have a(n) = 0, perfect numbers and others (see A064771) have a(n) = 1.
%C A065205 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
%H A065205 Amiram Eldar, <a href="/A065205/b065205.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%F A065205 a(n) = A033630(n) - 1.
%e A065205 a(20) = 1 because {1, 4, 5, 10} is the only subset of proper divisors of 20 that sum to 20.
%e A065205 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}.
%t A065205 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 *)
%o A065205 (Haskell)
%o A065205 a065205 n = p (a027751_row n) n where
%o A065205    p _      0 = 1
%o A065205    p []     _ = 0
%o A065205    p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
%o A065205 -- _Reinhard Zumkeller_, Jan 21 2013
%o A065205 (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
%Y A065205 Cf. A064771, A005835.
%Y A065205 Cf. A065218 for records.
%Y A065205 Cf. A027751, A210442, A211110, A033630.
%K A065205 nonn
%O A065205 1,12
%A A065205 Jonathan Ayres (jonathan.ayres(AT)btinternet.com), Oct 19 2001
%E A065205 More terms and additional comments from _Jud McCranie_, Oct 21 2001