A325807 Number of ways to partition the divisors of n into complementary subsets x and y for which gcd(n-Sum(x), n-Sum(y)) = 1. (Here only distinct unordered pairs of such subsets are counted.)
1, 2, 1, 4, 1, 1, 1, 8, 3, 4, 1, 16, 1, 4, 2, 16, 1, 16, 1, 16, 4, 4, 1, 40, 3, 3, 4, 1, 1, 40, 1, 32, 2, 4, 4, 244, 1, 4, 4, 48, 1, 40, 1, 16, 8, 3, 1, 220, 3, 27, 2, 10, 1, 32, 4, 64, 4, 4, 1, 672, 1, 4, 14, 64, 4, 40, 1, 13, 2, 64, 1, 1205, 1, 4, 16, 10, 4, 40, 1, 236, 15, 4, 1, 864, 4, 3, 2, 64, 1, 640, 2, 16, 4, 4, 2, 537, 1, 26, 8, 241, 1, 40, 1, 64, 40
Offset: 1
Keywords
Examples
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(1-0,1-1) = gcd(1,0) = 1, thus this partitioning is included, and a(1) = 1. For n = 3, its divisor set [1, 3] can be partitioned as [] and [1,3] (sums 0 and 4, thus gcd(3-0,3-4) = 1), [1] and [3] (sums 1 and 3, thus gcd(3-1,3-3) = 2), thus a(3) = 1, and similarly a(p) = 1 for any other odd prime p as well. For n = 6, its divisor set [1, 2, 3, 6] can be partitioned in eight ways as: [] and [1, 2, 3, 6] (sums 0 and 12, gcd(6-0, 6-12) = 6), [1, 2] and [3, 6] (sums 3 and 9, gcd(6-3, 6-9) = 3), [1, 3] and [2, 6] (sums 4 and 8, gcd(6-4, 6-8) = 2), [2] and [1, 3, 6] (sums 2 and 10, gcd(6-2, 6-10) = 4), [3] and [1, 2, 6] (sums 3 and 9, gcd(6-3, 6-9) = 3), [6] and [1, 2, 3] (sums 6 and 6, gcd(6-6, 6-6) = 0), [1] and [2, 3, 6] (sums 1 and 11, gcd(6-1, 6-11) = 5), [1, 6] and [2, 3] (sums 7 and 5, gcd(6-7, 6-5) = 1), with only the last partitioning satisfying the required condition, thus a(6) = 1. For n = 10, its divisor set [1, 2, 5, 10] can be partitioned in eight ways as: [] and [1, 2, 5, 10] (sums 0 and 18, gcd(10-0, 10-18) = 2), [1, 2] and [5, 10] (sums 3 and 15, gcd(10-3, 10-15) = 1), [1, 5] and [2, 10] (sums 6 and 12, gcd(10-6, 10-12) = 2), [2] and [1, 5, 10] (sums 2 and 16, gcd(10-2, 10-16) = 2), [5] and [1, 2, 10] (sums 5 and 13, gcd(10-5, 10-13) = 1), [10] and [1, 2, 5] (sums 10 and 8, gcd(10-10, 10-8) = 2), [1] and [2, 5, 10] (sums 1 and 17, gcd(10-1, 10-17) = 1), [1, 10] and [2, 5] (sums 11 and 7, gcd(10-11, 10-7) = 1), of which four satisfy the required condition, thus a(10) = 4.
Links
- Antti Karttunen, Table of n, a(n) for n = 1..1079
Programs
-
Mathematica
Table[Function[d, Count[DeleteDuplicates[Sort /@ Map[{#, Complement[d, #]} &, Subsets@ d]], ?(CoprimeQ @@ (n - Total /@ #) &)]]@ Divisors@ n, {n, 105}] (* _Michael De Vlieger, May 27 2019 *) -
PARI
A325807(n) = { my(divs=divisors(n), s=sigma(n),r); sum(b=0,(2^(-1+length(divs)))-1,r=sumbybits(divs,2*b);(1==gcd(n-(s-r),n-r))); }; sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };