login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

a(n) is the least integer q > 0 such that for some integer r, phi(q) + phi(r) = 2*n; where phi(n) is Euler's totient function (A000010).
2

%I #19 Apr 09 2020 20:46:12

%S 1,3,3,3,3,3,3,5,3,3,3,3,3,5,3,3,3,5,3,5,3,3,3,3,3,5,3,3,3,3,3,5,3,3,

%T 5,3,3,5,7,3,3,3,3,5,3,5,3,5,3,5,3,3,3,3,3,3,3,5,3,5,3,5,7,3,3,3,3,5,

%U 3,3,3,5,3,5,3,3,5,7,3,5,3,3,3,3,3,5,3,5,3,3,3,5,3,5,7,3,3,5,3,3,3,5,3,5,3

%N a(n) is the least integer q > 0 such that for some integer r, phi(q) + phi(r) = 2*n; where phi(n) is Euler's totient function (A000010).

%C Paul Erdös and Leo Moser conjectured that, for any even numbers 2*n, there exist integers q and r such that phi(q) + phi(r) = 2*n.

%C The only time phi is odd, it equals 1. Therefore, the only time that phi(q) + phi(r) = 2*n-1 (for n>0) has no solution is when 2*n-2 is a member of A005277 = 2*A079695.

%C The first occurrence of 2*k-1, or 0 if not possible, is k=1,2,3,...: 1, 2, 8, 39, 0, 124, 204, 208, 2024, 3473, 0, 2983, 2023, ..., .

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

%D Daniel Zwillinger, Editor-in-Chief, CRC Standard Mathematical Tables and Formulae, 31st Edition, 2.4.15 Euler Totient pages 128-130, Chapman & Hall/CRC, Boca Raton, 2003.

%H Eric W. Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GoldbachConjecture.html">Goldbach's Conjecture.</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture">Goldbach's conjecture</a>

%H <a href="/index/Go#Goldbach">Index entries for sequences related to Goldbach conjecture</a>

%t mbr = Union@ Array[ EulerPhi@# &, 500]; a[n_] := Block[{q = 1}, While[ !MemberQ[mbr, 2n - EulerPhi@ q], q++]; q]; Array[a, 105]

%Y Cf. A000010, A306513, A333820.

%K nonn

%O 1,2

%A _Robert G. Wilson v_, Apr 06 2020