A325807 -id:A325807 - cp's OEIS frontend

A324213 Number of k with 0 <= k <= sigma(n) such that n-k and 2n-sigma(n) are relatively prime.

2, 4, 3, 8, 4, 2, 4, 16, 12, 9, 6, 14, 6, 12, 8, 32, 10, 26, 8, 21, 14, 18, 12, 20, 30, 16, 18, 2, 14, 24, 10, 64, 16, 24, 22, 88, 14, 30, 26, 36, 18, 32, 14, 42, 26, 28, 24, 54, 56, 80, 20, 32, 26, 40, 36, 60, 38, 42, 30, 56, 18, 42, 48, 128, 42, 48, 22, 50, 28, 72, 26, 122, 26, 54, 58, 46, 48, 56, 26, 86, 120, 60, 42, 96, 54

Offset: 1

Antti Karttunen and David A. Corneth, May 26 2019, with better name from Charlie Neder, Jun 02 2019

nonn

Number of ways to form the sum sigma(n) = x+y so that n-x and n-y are coprime, with x and y in range 0..sigma(n).
From Antti Karttunen, May 28 - Jun 08 2019: (Start)
Empirically, it seems that a(n) >= A034444(n) and also that a(n) >= A034444(A000203(n)) unless n is in A000396.
Specifically, if it could be proved that a(n) >= A034444(n)/2 for n >= 2, which in turn would imply that a(n) >= A001221(n) for all n, then we would know that no odd perfect numbers could exist. Note that a(n) must be 2 on all perfect numbers, whether even or odd. See also A325819.
(End)

			For n=1, sigma(1) = 1, both gcd(1-0, 1-(1-0)) = gcd(1,0) = 1 and gcd(1-1, 1-(1-1)) = gcd(0,1) = 1, thus a(1) = 2.
--
For n=3, sigma(3) = 4, we have 5 cases to consider:
  gcd(3-0, 3-(4-0)) = 1 = gcd(3-4, 3-(4-4)),
  gcd(3-1, 3-(4-1)) = 2 = gcd(3-3, 3-(4-3)),
  gcd(3-2, 3-(4-2)) = 1,
of which three cases give 1 as a result, thus a(3) = 3.
--
For n=6, sigma(6) = 12, we have 13 cases to consider:
  gcd(6-0, 6-(12-0)) = 6 = gcd(6-12, 6-(12-12)),
  gcd(6-1, 6-(12-1)) = 5 = gcd(6-11, 6-(12-11)),
  gcd(6-2, 6-(12-2)) = 4 = gcd(6-10, 6-(12-10)),
  gcd(6-3, 6-(12-3)) = 3 = gcd(6-9, 6-(12-9)),
  gcd(6-4, 6-(12-4)) = 2 = gcd(6-8, 6-(12-8))
  gcd(6-5, 6-(12-5)) = 1 = gcd(6-7, 6-(12-7)),
  gcd(6-6, 6-(12-6)) = 0,
of which only two give 1 as a result, thus a(6) = 2.
--
For n=10, sigma(10) = 18, we have 19 cases to consider:
  gcd(10-0, 10-(18-0)) = 2 = gcd(10-18, 10-(18-18)),
  gcd(10-1, 10-(18-1)) = 1 = gcd(10-17, 10-(18-17)),
  gcd(10-2, 10-(18-2)) = 2 = gcd(10-16, 10-(18-16)),
  gcd(10-3, 10-(18-3)) = 1 = gcd(10-15, 10-(18-15)),
  gcd(10-4, 10-(18-4)) = 2 = gcd(10-14, 10-(18-14)),
  gcd(10-5, 10-(18-5)) = 1 = gcd(10-13, 10-(18-13)),
  gcd(10-6, 10-(18-6)) = 2 = gcd(10-12, 10-(18-12)),
  gcd(10-7, 10-(18-7)) = 1 = gcd(10-11, 10-(18-11)),
  gcd(10-8, 10-(18-8)) = 2 = gcd(10-10, 10-(18-10)),
  gcd(10-9, 10-(18-9)) = 1,
of which 9 cases give 1 as a result, thus a(10) = 9.
--
For n=15, sigma(15) = 24, we have 25 cases to consider:
  gcd(15-0, 15-(24-0)) = 3 = gcd(15-24, 15-(24-24)),
  gcd(15-1, 15-(24-1)) = 2 = gcd(15-23, 15-(24-23)),
  gcd(15-2, 15-(24-2)) = 1 = gcd(15-22, 15-(24-22)),
  gcd(15-3, 15-(24-3)) = 6 = gcd(15-21, 15-(24-21)),
  gcd(15-4, 15-(24-4)) = 1 = gcd(15-20, 15-(24-20)),
  gcd(15-5, 15-(24-5)) = 2 = gcd(15-19, 15-(24-19)),
  gcd(15-6, 15-(24-6)) = 3 = gcd(15-18, 15-(24-18)),
  gcd(15-7, 15-(24-7)) = 2 = gcd(15-17, 15-(24-17)),
  gcd(15-8, 15-(24-8)) = 1 = gcd(15-16, 15-(24-16)),
  gcd(15-9, 15-(24-9)) = 6 = gcd(15-15, 15-(24-15)),
  gcd(15-10, 15-(24-10)) = 1 = gcd(15-14, 15-(24-14)),
  gcd(15-11, 15-(24-11)) = 2 = gcd(15-13, 15-(24-13)),
  gcd(15-12, 15-(24-12)) = 3,
of which 2*4 = 8 cases give 1 as a result, thus a(15) = 8.

Antti Karttunen, Table of n, a(n) for n = 1..20000
Index entries for sequences related to sigma(n)

Cf. A000010, A000203, A000396, A001221, A014567, A034444, A058062, A062401, A228058, A325807, A325815, A325816, A325817, A325818, A325819, A325960, A325961, A325962, A325965, A325966, A325967, A325968, A325970, A325971, A325972.

Array[Sum[Boole[1 == GCD[#1 - i, #1 - (#2 - i)]], {i, 0, #2}] & @@ {#, DivisorSigma[1, #]} &, 85] (* Michael De Vlieger, Jun 09 2019 *)

A324213(n) = { my(s=sigma(n)); sum(i=0,s,(1==gcd(n-i,n-(s-i)))); };

a(n) = Sum_{i=0..sigma(n)} [1 == gcd(n-i,n-(sigma(n)-i))], where [ ] is the Iverson bracket and sigma(n) is A000203(n).
a(A000396(n)) = 2.
a(n) = A325815(n) + A034444(n).
a(n) = 1+A000203(n) - A325816(n).
a(A228058(n)) = A325819(n).

A325967 a(n) is the minimum sum of all such subsets of divisors of n for which n-s and (sigma(n)-s)-n are relatively prime, where s is the sum of the subset.

Original entry on oeis.org

0, 0, 0, 0, 0, 5, 0, 0, 0, 1, 0, 1, 0, 1, 4, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 3, 0, 27, 0, 1, 0, 0, 4, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 4, 3, 0, 1, 0, 0, 4, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 4, 1, 0, 1, 0, 1, 0, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 3, 4, 1, 0, 1, 8, 1, 0, 1, 6, 5, 0, 0, 4, 0, 0, 1, 0, 1, 4

Offset: 1

Antti Karttunen, May 29 2019

nonn

Partition the divisors of n in all possible ways into such complementary subsets x and y for which gcd(n-Sum(x), n-Sum(y)) = 1. a(n) is the minimal value of min(Sum(x), Sum(y)) attained over all such pairs of subsets x and y.
Records 0, 5, 27, 495, 8127, 8289, 10359, 11049, 13809, 15189, 15879, ... occur at 1, 6, 28, 496, 8128, 33148, 41428, 44188, 55228, 60748, 63508, ...
Equivalently, the least k expressible as a sum of distinct divisors of n such that gcd(n-k,A033879(n)) = 1, with the convention that gcd(k,0) = k. - Charlie Neder, Jun 09 2019

			For n=15, its divisors are [1, 3, 5, 15]. If we take an empty set [] and its complement [1, 3, 5, 15], their sums are 0 and 24, but gcd(15-0, 24-15) = gcd(15, 9) = 3 > 1. If we take subsets [1] and [3, 5, 15], then their sums are 1 and 23, but gcd(15-1, 23-15) = gcd(14,8) = 2 > 1. If we take subsets [3] and [1, 5, 15], their sums are 3 and 21, but gcd(15-3, 21-15) = gcd(12, 6) = 6 > 1. Only when we take the subset with a next larger sum, [1, 3] and its complement [5, 15], we get such sums 4 and 20 for which gcd(15-4, 20-15) = gcd(11, 5) = 1. Thus a(15) = 4, the size of the subset with lesser sum.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to sigma(n)

Cf. A000203, A000396, A009194, A014567 (positions of zeros), A325807, A325817, A325968, A325969.

\\ Probably not the most optimal algorithm, but at least faster than the implementation using sumbybits (below):
A325967aux(n, ds, s, ms, divs, from=1) = if(1==gcd((s-ds)-n,n-ds), return(ds), for(i=from, #divs, if(ds+divs[i] >= ms, return(ms), ms = min(ms,A325967aux(n, ds+divs[i], s, ms, divs, i+1)))); (ms));
A325967(n) = if(1==gcd(n, sigma(n)), 0, my(divs = List(divisors(n)), s=sigma(n), ms=2*s); fordiv(n,d, if(d>=ms, return(ms), listpop(divs,1); ms = min(ms,A325967aux(n, d, s, ms, divs)))); (ms));

A325967(n) = { my(divs=divisors(n), s=sigma(n),r,ms=-1); for(b=0,(2^(length(divs)))-1,r=sumbybits(divs,b);if(1==gcd(n-(s-r),n-r),if(ms<0||r0,s += (b%2)*v[i]; i++; b >>= 1); (s); };

a(n) = A000203(n) - A325968(n) = A001065(n) - A325969(n).
For all n, a(A000396(n)) = A000396(n)-1.
For all n, a(n) >= A325817(n).

A325968 a(n) is the sum k of such a subset of divisors of n with the largest sum and for which n-k and n-(sigma(n)-k) are relatively prime.

Original entry on oeis.org

1, 3, 4, 7, 6, 7, 8, 15, 13, 17, 12, 27, 14, 23, 20, 31, 18, 38, 20, 41, 32, 35, 24, 59, 31, 39, 40, 29, 30, 71, 32, 63, 44, 53, 48, 91, 38, 59, 56, 89, 42, 95, 44, 83, 74, 69, 48, 123, 57, 93, 68, 95, 54, 119, 72, 119, 80, 89, 60, 167, 62, 95, 104, 127, 84, 143, 68, 125, 92, 143, 72, 194, 74, 113, 124, 137, 96, 167, 80, 185, 121, 125

Offset: 1

Antti Karttunen, May 29 2019

nonn

			For n=15, its divisors are [1, 3, 5, 15]. If we take the full set [1, 3, 5, 15] and its complement [], their sums are 24 and 0, but gcd(15-0, 24-15) = gcd(15, 9) = 3 > 1. If we take subsets [1] and [3, 5, 15], then their sums are 1 and 23, but gcd(15-1, 23-15) = gcd(14,8) = 2 > 1. If we take subsets [3] and [1, 5, 15], their sums are 3 and 21, but gcd(15-3, 21-15) = gcd(12, 6) = 6 > 1. Only when we take the subset with the four smallest sum, [1, 3] and its complement [5, 15], we get such sums 4 and 20 for which gcd(15-4, 20-15) = gcd(11, 5) = 1. Thus a(15) = 20, the size of the subset with larger sum.

Antti Karttunen, Table of n, a(n) for n = 1..25000
Index entries for sequences related to sigma(n)

Cf. A000040, A000203, A000396, A009194, A325807, A325818, A325967, A325969.

A325968(n) = { my(divs=divisors(n), s=sigma(n),r,ms=0); for(b=0,(2^(length(divs)))-1,r=sumbybits(divs,b);if(1==gcd(n-(s-r),n-r),ms=max(r,ms))); (ms); };
sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };

a(n) = A000203(n) - A325967(n).
a(n) = n + A325969(n).
For all n:
a(A000040(n)) = A000040(n)+1.
a(A000396(n)) = A000396(n)+1.
a(n) <= A325818(n).

A325969 a(n) = A325968(n) - n.

Original entry on oeis.org

0, 1, 1, 3, 1, 1, 1, 7, 4, 7, 1, 15, 1, 9, 5, 15, 1, 20, 1, 21, 11, 13, 1, 35, 6, 13, 13, 1, 1, 41, 1, 31, 11, 19, 13, 55, 1, 21, 17, 49, 1, 53, 1, 39, 29, 23, 1, 75, 8, 43, 17, 43, 1, 65, 17, 63, 23, 31, 1, 107, 1, 33, 41, 63, 19, 77, 1, 57, 23, 73, 1, 122, 1, 39, 49, 61, 19, 89, 1, 105, 40, 43, 1, 139, 23, 43, 29, 91, 1, 143, 13, 75, 35, 49

Offset: 1

Antti Karttunen, May 29 2019

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to sigma(n)

Cf. A000203, A009194, A033879, A325807, A325826, A325959, A325967, A325968.

A325967aux(n, ds, s, ms, divs, from=1) = if(1==gcd((s-ds)-n,n-ds), return(ds), for(i=from, #divs, if(ds+divs[i] >= ms, return(ms), ms = min(ms,A325967aux(n, ds+divs[i], s, ms, divs, i+1)))); (ms));
A325967(n) = if(1==gcd(n, sigma(n)), 0, my(divs = List(divisors(n)), s=sigma(n), ms=2*s); fordiv(n,d, if(d>=ms, return(ms), listpop(divs,1); ms = min(ms,A325967aux(n, d, s, ms, divs)))); (ms));
A325969(n) = ((sigma(n)-n)-A325967(n));

A325968(n) = { my(divs=divisors(n), s=sigma(n),r,ms=0); for(b=0,(2^(length(divs)))-1,r=sumbybits(divs,b);if(1==gcd(n-(s-r),n-r),ms=max(r,ms))); (ms); };
sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };
A325969(n) = (A325968(n)-n);

a(n) = A325968(n) - n = A001065(n) - A325967(n).
a(n) = A325959(n) - A033879(n).
a(A000040(n)) = a(A000396(n)) = 1.
For all n, a(n) <= A325826(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.)

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

A325809 Let k = A228058(n). a(n) is the number of ways to partition the divisors of k into complementary subsets x and y so that the (k-Sum(x)) and (k-Sum(y)) are coprime.

Original entry on oeis.org

8, 12, 8, 16, 8, 15, 16, 8, 113, 16, 8, 15, 16, 7, 14, 8, 8, 13, 16, 15, 8, 15, 14, 8, 15, 254, 8, 16, 8, 128, 16, 16, 16, 15, 8, 15, 16, 15, 8, 16, 13, 15, 7, 13, 16, 8, 16, 43008, 8, 8, 126, 8, 15, 15, 15, 8, 16, 8, 14, 8, 15, 16, 8, 16, 60672, 15, 256, 13, 16, 7, 103, 16, 16, 8, 16, 16, 16, 8, 2015, 16, 8, 15, 16, 39093, 16

Offset: 1

Antti Karttunen, May 25 2019

nonn

The smallest value known so far occurs as a(449) = 6. A228058(449) = 23837 = 11^2 * 197.

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

Cf. A228058, A325807, A325819.

up_to = 25000;
isA228058(n) = if(!(n%2)||(omega(n)<2),0,my(f=factor(n),y=0); for(i=1,#f~,if(1==(f[i,2]%4), if((1==y)||(1!=(f[i,1]%4)),return(0),y=1), if(f[i,2]%2, return(0)))); (y));
A228058list(up_to) = { my(v=vector(up_to), k=0, n=0); while(kA228058(n), k++; v[k] = n)); (v); };
v228058 = A228058list(up_to);
A228058(n) = v228058[n];
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); };
A325809(n) = A325807(A228058(n));

a(n) = A325807(A228058(n)).

cp's OEIS Frontend

A324213 Number of k with 0 <= k <= sigma(n) such that n-k and 2n-sigma(n) are relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A325967 a(n) is the minimum sum of all such subsets of divisors of n for which n-s and (sigma(n)-s)-n are relatively prime, where s is the sum of the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A325968 a(n) is the sum k of such a subset of divisors of n with the largest sum and for which n-k and n-(sigma(n)-k) are relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A325969 a(n) = A325968(n) - n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

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

A325809 Let k = A228058(n). a(n) is the number of ways to partition the divisors of k into complementary subsets x and y so that the (k-Sum(x)) and (k-Sum(y)) are coprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula