A306513 The number of unordered pairs of coprime integers q and r such that phi(q) + phi(r) = 2n.

1, 1, 5, 7, 12, 10, 19, 18, 20, 21, 35, 32, 39, 42, 38, 37, 48, 46, 45, 58, 64, 63, 69, 73, 58, 93, 71, 70, 81, 92, 72, 113, 96, 94, 90, 100, 79, 158, 120, 95, 131, 153, 84, 147, 129, 132, 126, 150, 92, 179, 157, 150, 149, 187, 92, 224, 177, 166, 173, 207, 124

Offset: 1

Author

Robert G. Wilson v, Feb 20 2019

Keywords

• nonn

Comments

Paul Erdős and Leo Moser conjectured that, for any even number 2n, there exist integers q and r such that phi(q) + phi(r) = 2n with gcd(q, r) = 1. Adding to this conjecture the requirement that q and r be prime yields the Goldbach Conjecture. The replacement of the requirement that q and r be prime with the relaxed requirement that they be coprime was done in an effort to solve the Goldbach Conjecture.

Examples

			a(1) = 1 with {q, r} = {1,2};
a(2) = 1 with {q, r} = {3,4};
a(3) = 5 because phi(q) + phi(r) = 6 for the pairs {q, r} = {3,5}, {3,8}, {3,10}, {4,5} & {5,6}; etc.
		

References

• George E. Andrews, Number Theory, Chapter 6, Arithmetic Functions, Section 6-1, Combinatorial Study of Phi(n), pp. 75-82, Dover Publishing, NY, 1971.

Links

• Robert G. Wilson v, Table of n, a(n) for n = 1..1150
• Eric W. Weisstein's World of Mathematics, Goldbach Conjecture.
• Wikipedia, Goldbach's conjecture
• Index entries for sequences related to Goldbach conjecture

Crossrefs

Cf. A000010, A005277, A079695, A002375.

Programs

Mathematica

f[n_] := Block[{c = 0, q = 1}, While[q < 12n, epq = EulerPhi[q]; r = 12n + 125; While[r > q, If[ GCD[q, r] == 1 && epq + EulerPhi[r] == 2 n, c++]; r--]; q++]; c]; Array[f, 61]