A100577 -id:A100577 - cp's OEIS frontend

A229335 Sum of sums of elements of subsets of divisors of n.

1, 6, 8, 28, 12, 96, 16, 120, 52, 144, 24, 896, 28, 192, 192, 496, 36, 1248, 40, 1344, 256, 288, 48, 7680, 124, 336, 320, 1792, 60, 9216, 64, 2016, 384, 432, 384, 23296, 76, 480, 448, 11520, 84, 12288, 88, 2688, 2496, 576, 96, 63488, 228, 2976, 576, 3136, 108

Offset: 1

Jaroslav Krizek, Sep 20 2013

nonn

Number of nonempty subsets of divisors of n = A100587(n).

			For n = 2^2 = 4; divisors of 4: {1, 2, 4}; nonempty subsets of divisors of n: {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}; sum of sums of elements of subsets = 1 + 2 + 4 + 3 + 5 + 6 + 7 = 28 = (2^3-1) * 2^2 = 7 * 4.

Jaroslav Krizek, Table of n, a(n) for n = 1..1000

Cf. A229336 (product of sums of elements of subsets of divisors of n).
Cf. A229337 (sum of products of elements of subsets of divisors of n).
Cf. A229338 (product of products of elements of subsets of divisors of n).

A229335 := proc(n)
    numtheory[sigma](n)*A100577(n) ;
end proc:
seq(A229335(n),n=1..100) ; # R. J. Mathar, Nov 10 2017

Table[Total[Flatten[Subsets[Divisors[n]]]], {n, 100}] (* T. D. Noe, Sep 21 2013 *)

a(n) = A000203(n) * A100577(n) = A000203(n) * (A100587(n) + 1) / 2 = A000203(n) * 2^(A000005(n) - 1) = sigma(n) * 2^(tau(n) - 1).

a(2^n) = (2^(n+1) - 1) * 2^n.

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

Original entry on oeis.org

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

Antti Karttunen, May 24 2019

nonn

			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.

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

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

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

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

For all n >= 1:
a(n) <= A100577(n).
a(A065091(n)) = 1, a(A000396(n)) = 1.
a(A228058(n)) = A325809(n).

A069626 Number of sets of integers larger than one whose least common multiple is n.

Original entry on oeis.org

1, 1, 1, 2, 1, 5, 1, 4, 2, 5, 1, 22, 1, 5, 5, 8, 1, 22, 1, 22, 5, 5, 1, 92, 2, 5, 4, 22, 1, 109, 1, 16, 5, 5, 5, 200, 1, 5, 5, 92, 1, 109, 1, 22, 22, 5, 1, 376, 2, 22, 5, 22, 1, 92, 5, 92, 5, 5, 1, 1874, 1, 5, 22, 32, 5, 109, 1, 22, 5, 109, 1, 1696, 1, 5, 22, 22, 5, 109, 1, 376, 8, 5, 1, 1874, 5, 5, 5, 92, 1, 1874, 5, 22

Offset: 1

Amarnath Murthy, Mar 27 2002

a(p) = 1, a(p*q) = 5, a(p^2*q) = 13, a(p^3) = 4, a(p^4) = 8 etc. where p and q are primes. It can be shown that a(p^k) = 2^(k-1). Problem: find an expression for a(N) when N = p^a*q^b*r^c*..., p,q,r are primes.

			a(6) = 5 as there are five such sets of natural numbers larger than one whose least common multiple is six: {6}, {2, 6}, {3, 6}, {2, 3} and {2, 3, 6}.
a(12) = 22 from {12}, {4,3}, {2,4,3}, {4,6}, {2,4,6}, {4,3,6}, {2,4,3,6}, {2,12}, {4,12}, {2,4,12}, {3,12}, {2,3,12}, {4,3,12}, {2,4,3,12}, {6,12}, {2,6,12}, {4,6,12}, {2,4,6,12}, {3,6,12}, {2,3,6,12}, {4,3,6,12}, {2,4,3,6,12}.
From _Antti Karttunen_, Feb 18 2024: (Start)
a(1) = 1 as there is only one set that satisfies the criteria, namely, an empty set {}, whose lcm is 1.
a(2) = 1 as the only set that satisfies the criteria is a singleton set {2}.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Index entries for sequences computed from exponents in factorization of n
Index entries for sequences related to lcm's

A000005, A008683, A286518, A318670.
Möbius transform of A100577.
Cf. also A045778 (number of sets of integers > 1 whose product is n).
Cf. A076078.

-- following Vladeta Jovovic's formula.
a069626 n = sum $
   map (\d -> (a008683 (n `div` d)) * 2 ^ (a000005 d - 1)) $ a027750_row n
-- Reinhard Zumkeller, Jun 12 2015, Feb 07 2011
(APL, Dyalog dialect)
divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð,(⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
A069626 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{∧/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (quite taxing on memory) - Antti Karttunen, Feb 18 2024

with(numtheory): seq(add(mobius(n/d)*2^(tau(d)-1), d in divisors(n)), n=1..80); # Ridouane Oudra, Mar 12 2024

a[n_] := Sum[ MoebiusMu[n/d] * 2^(DivisorSigma[0, d] - 1), {d, Divisors[n]}]; Table[a[n], {n, 1, 92}](* Jean-François Alcover, Nov 30 2011, after Vladeta Jovovic *)

A069626(n) = sumdiv(n,d,moebius(n/d)*2^(numdiv(d)-1)); \\ Antti Karttunen, Feb 18 2024

a(n) = Sum_{ d divides n } mu(n/d)*2^(tau(d)-1). - Vladeta Jovovic, Jul 07 2003
a(n) >= A286518, a(n) >= A318670. - Antti Karttunen, Feb 17 2024
a(n) = A076078(n)/2, for n > 1. - Ridouane Oudra, Mar 12 2024

Corrected and extended by Naohiro Nomoto, Apr 25 2002

Definition and examples clarified by Antti Karttunen, Feb 18 2024

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

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 24 2019

nonn

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

			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.

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

Cf. A000005, A000203, A100577, A325807.

Cf. A083206, A083207, A083209, A083210.

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

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

a(n) <= A100577(n).

cp's OEIS Frontend

A229335 Sum of sums of elements of subsets of divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A069626 Number of sets of integers larger than one whose least common multiple is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula