login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.) 2
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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.

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

LINKS

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

FORMULA

a(n) <= A100577(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(0,1) = 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), [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.

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.

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:

  [1] and [2, 3, 4, 6, 12],

  [1, 2] and [3, 4, 6, 12],

  [1, 4] and [2, 3, 6, 12],

  [1, 2, 6] and [3, 4, 12],

  [1, 4, 6] and [2, 3, 12],

  [1, 2, 4, 6] and [3, 12],

  [1, 12] and [2, 3, 4, 6],

  [1, 2, 12] and [3, 4, 6],

  [1, 4, 12] and [2, 3, 6],

  [1, 2, 4, 12] and [3, 6],

  [1, 6, 12] and [2, 3, 4],

  [1, 4, 6, 12] and [2, 3],

  [1, 2, 4, 6, 12] and [3],

thus a(12) = 13.

MATHEMATICA

Array[Function[d, Count[DeleteDuplicates[Sort /@ Map[{#, Complement[d, #]} &, Subsets@ d]], _?(CoprimeQ @@ (Total /@ #) &)]]@ Divisors@ # &, 105] (* Michael De Vlieger, May 27 2019 *)

PROG

(PARI)

A325806(n) = { my(divs=divisors(n), s=sigma(n)); sum(b=0, (2^(-1+length(divs)))-1, (1==gcd(s, sumbybits(divs, 2*b)))); };

sumbybits(v, b) = { my(s=0, i=1); while(b>0, s += (b%2)*v[i]; i++; b >>= 1); (s); };

CROSSREFS

Cf. A000005, A000203, A100577, A325807.

Cf. A083206, A083207, A083209, A083210.

Sequence in context: A284639 A320887 A295923 * A016470 A059807 A214208

Adjacent sequences:  A325803 A325804 A325805 * A325807 A325808 A325809

KEYWORD

nonn

AUTHOR

Antti Karttunen, May 24 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 11 01:53 EDT 2020. Contains 336418 sequences. (Running on oeis4.)