OFFSET
1,3
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.
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
EXAMPLE
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.
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]
CROSSREFS
KEYWORD
nonn
AUTHOR
Robert G. Wilson v, Feb 20 2019
STATUS
approved