The values of the Euler phi function $\phi(n)$ are tabulated at OEIS A$000010$.
Each of these values is even except for $\phi(1) = \phi(2) = 1$ . However, not every even number arises in this way. Those that don't $( 14, 26, 34, 38, ... )$ are listed at OEIS A$005277$ .

A little experimentation suggests that every even number can be written as $$2n = \phi(a) + \phi(b)$$
If we invoke Goldbach's conjecture, then this can be shown as follows. Writing $2n + 2 = p + q$ for primes $p$ and $q$ yields $2n = \phi(p) + \phi(q)$ . [For odd numbers we could rewrite this using three summands as $2n +1 = \phi(p) + \phi(q) + \phi(1)$ . ]

Question: There are many more phi values than (shifted) primes indicating that this problem might be accessible even though Goldbach currently is not. Is it possible to give an unconditional proof that $2n = \phi(a) + \phi(b)$ always has a solution?


  • $\begingroup$ It is interesting (at least to me) to note that this could potentially be tackled by knowing something about the maximum length of a string of consecutive even numbers in the sequence of nontotients. For example, if it were true that the maximum length of such a string were $7$, then we would know that, whenever $m$ is a nontotient, then one of $m-2, m-4, \ldots m-12$ is not a nontotient, and the numbers $2,4,\ldots,12$ are not nontotients, hence we will get such a representation. More generally, if we had an explicit upper bound for the maximum length, then we could get somewhere... $\endgroup$ – Sam Streeter Oct 30 '18 at 21:35
  • $\begingroup$ ...however, I suspect that figuring anything out about the lengths of these strings is no easier! Just a thought. Love this question, will be watching it closely. $\endgroup$ – Sam Streeter Oct 30 '18 at 21:36
  • $\begingroup$ It would also help to know whether the asymptotic density of totients is greater than $1/4$, and some error bound. $\endgroup$ – Servaes Oct 30 '18 at 22:52
  • 1
    $\begingroup$ @rogerl I found it surprisingly hard to find anything on the asymptotic density of totients, but I did find a remark at the end of section 3.2.7 on page 206 of Handbook of Number Theory II, Volume 2. by J. Sándor, D. Mitronović and B. Crstici, see here. $\endgroup$ – Servaes Oct 31 '18 at 8:50
  • 1
    $\begingroup$ @rogerl The remark references section 11.3 of An Introduction to the Theory of Numbers, (thid edition) by I. Niven and H.S. Zuckerman. To be precise, it is Theorem 11.9 on page 246 there. $\endgroup$ – Servaes Oct 31 '18 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.