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

Author

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

Keywords

• nonn

Comments

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)

Examples

			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.
		

Links

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

Crossrefs

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.

Programs

Mathematica

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

PARI

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

Formula

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