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,2

Links

Antti Karttunen, Table of n, a(n) for n = 1..1079

Formula

For all n >= 1:

a(n) <= A100577(n).

a(A065091(n)) = 1, a(A000396(n)) = 1.

a(A228058(n)) = A325809(n).

Example

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.

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 *)

Prog

(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); };

Crossrefs

Cf. A000203, A000396, A065091, A100577, A324213, A325806, A325809.

Sequence in context: A070674 A070668 A318407 * A072341 A011130 A291854

Adjacent sequences: A325804 A325805 A325806 * A325808 A325809 A325810

Keyword

nonn

Author

Antti Karttunen, May 24 2019

Status

approved