cp's OEIS Frontend

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

%I A306513 #31 Feb 16 2025 08:33:55
%S A306513 1,1,5,7,12,10,19,18,20,21,35,32,39,42,38,37,48,46,45,58,64,63,69,73,
%T A306513 58,93,71,70,81,92,72,113,96,94,90,100,79,158,120,95,131,153,84,147,
%U A306513 129,132,126,150,92,179,157,150,149,187,92,224,177,166,173,207,124
%N A306513 The number of unordered pairs of coprime integers q and r such that phi(q) + phi(r) = 2n.
%C A306513 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.
%D A306513 George E. Andrews, Number Theory, Chapter 6, Arithmetic Functions, Section 6-1, Combinatorial Study of Phi(n), pp. 75-82, Dover Publishing, NY, 1971.
%H A306513 Robert G. Wilson v, <a href="/A306513/b306513.txt">Table of n, a(n) for n = 1..1150</a>
%H A306513 Eric W. Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GoldbachConjecture.html">Goldbach Conjecture</a>.
%H A306513 Wikipedia, <a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture">Goldbach's conjecture</a>
%H A306513 <a href="/index/Go#Goldbach">Index entries for sequences related to Goldbach conjecture</a>
%e A306513 a(1) = 1 with {q, r} = {1,2};
%e A306513 a(2) = 1 with {q, r} = {3,4};
%e A306513 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.
%t A306513 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]
%Y A306513 Cf. A000010, A005277, A079695, A002375.
%K A306513 nonn
%O A306513 1,3
%A A306513 _Robert G. Wilson v_, Feb 20 2019