cp's OEIS Frontend

A325806 Number of ways to partition the divisors of n into two complementary sets whose sums are relatively prime. (Here only distinct unordered pairs of such subsets are counted.)

%I A325806 #26 May 28 2019 19:33:31
%S A325806 1,1,1,3,1,2,1,4,3,3,1,13,1,2,2,15,1,15,1,9,4,3,1,33,3,2,4,12,1,40,1,
%T A325806 18,2,3,4,201,1,2,4,33,1,40,1,9,7,3,1,245,3,20,2,15,1,25,4,34,4,3,1,
%U A325806 577,1,2,15,63,4,40,1,9,2,44,1,951,1,2,15,10,4,34,1,164,15,3,1,864,4,2,2,34,1,592,2,9,4,3,2,577,1,21,7,210,1,40,1,29,40
%N A325806 Number of ways to partition the divisors of n into two complementary sets whose sums are relatively prime. (Here only distinct unordered pairs of such subsets are counted.)
%C A325806 a(n) is the number of such subsets of divisors of n that include {1} and have sum that is coprime to the sum of their complement.
%C A325806 Records 1, 3, 4, 13, 15, 33, 40, 201, 245, 577, 951, 8672, 14595, 33904, 168904, 253694, 2057413, 2395584, 2396158, 2571028, 159504796, 572644864, ... occur at positions 1, 4, 8, 12, 16, 24, 30, 36, 48, 60, 72, 120, 144, 180, 240, 336, 360, 420, 480, 630, 720, 840, ...
%H A325806 Antti Karttunen, <a href="/A325806/b325806.txt">Table of n, a(n) for n = 1..1079</a>
%F A325806 a(n) <= A100577(n).
%e A325806 For n = 1, its divisor set [1] can be partitioned only to an empty set [] and set [1], with sums 0 and 1 respectively, and gcd(0,1) = 1, thus this partitioning is included, and a(1) = 1.
%e A325806 For n = 3, its divisor set [1, 3] can be partitioned as [] and [1,3] (sums 0 and 4), [1] and [3] (sums 1 and 3), and only in latter case the sums are coprime as gcd(1,3) = 1, thus a(3) = 1, and similarly a(p) = 1 for any other prime p as well.
%e A325806 For n = 6, its divisor set [1, 2, 3, 6] can be partitioned as [] and [1, 2, 3, 6] (sums 0 and 12), [1, 2] and [3, 6] (sums 3 and 9), [1, 3] and [2, 6] (sums 4 and 8), [2] and [1, 3, 6] (sums 2 and 10), [3] and [1, 2, 6] (sums 3 and 9), [6] and [1, 2, 3] (sums 6 and 6), and also as [1] and [2, 3, 6] (sums 1 and 11), and [1, 6] and [2, 3] (sums 7 and 5) and only in latter two cases their sums are coprime, thus a(6) = 2.
%e A325806 For n = 12, its divisor set [1, 2, 3, 4, 6, 12] can be partitioned altogether in 2^(6-1) = 32 ways, but of which only the following thirteen partitions have coprime sums:
%e A325806   [1] and [2, 3, 4, 6, 12],
%e A325806   [1, 2] and [3, 4, 6, 12],
%e A325806   [1, 4] and [2, 3, 6, 12],
%e A325806   [1, 2, 6] and [3, 4, 12],
%e A325806   [1, 4, 6] and [2, 3, 12],
%e A325806   [1, 2, 4, 6] and [3, 12],
%e A325806   [1, 12] and [2, 3, 4, 6],
%e A325806   [1, 2, 12] and [3, 4, 6],
%e A325806   [1, 4, 12] and [2, 3, 6],
%e A325806   [1, 2, 4, 12] and [3, 6],
%e A325806   [1, 6, 12] and [2, 3, 4],
%e A325806   [1, 4, 6, 12] and [2, 3],
%e A325806   [1, 2, 4, 6, 12] and [3],
%e A325806 thus a(12) = 13.
%t A325806 Array[Function[d, Count[DeleteDuplicates[Sort /@ Map[{#, Complement[d, #]} &, Subsets@ d]], _?(CoprimeQ @@ (Total /@ #) &)]]@ Divisors@ # &, 105] (* _Michael De Vlieger_, May 27 2019 *)
%o A325806 (PARI)
%o A325806 A325806(n) = { my(divs=divisors(n), s=sigma(n)); sum(b=0,(2^(-1+length(divs)))-1,(1==gcd(s,sumbybits(divs,2*b)))); };
%o A325806 sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };
%Y A325806 Cf. A000005, A000203, A100577, A325807.
%Y A325806 Cf. A083206, A083207, A083209, A083210.
%K A325806 nonn
%O A325806 1,4
%A A325806 _Antti Karttunen_, May 24 2019