18
$\begingroup$

For which positive integers $n$ is the sum $\sum_{k=1}^n 1 / \varphi(k)$ an integer? Here $\varphi$ is the Euler totient function.

The question is a "totient-analog" of the well-known result that $\sum_{k=1}^n 1/k$ is an integer only for $n=1$, which can be proved either using Bertrand's postulate or considering the $2$-adic valuation.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ There should be only finitely many such $n$. Assuming some quantitative version of Dickson's conjecture a version of Bertrand's postulate should hold for primes of the form $2p+1$, where $p$ itself is prime. We can then repeat the argument for harmonic series, noting that $1/\varphi(2p+1)$ would be the only term with $p$ in the denominator. $\endgroup$
    – Wojowu
    Commented Jan 15, 2022 at 11:01
  • 2
    $\begingroup$ For $n$ of the form $3^j \leq n \leq 4 \times 3^{j-1}$ for some $j \geq 2$ the sum is non-integral because $\varphi(k), k \leq n$ is divisible by $3^{j-1}$ only at $k=3^j$ and (possibly) at $k = 2 \times 3^{j-1}+1$ if the latter is prime, and in either case we can write $\sum_{k=1}^n 1/\varphi(k) = \frac{a}{b} + \frac{c}{2 \times 3^{j-1}}$ for some integers $a,b,c$ with $c \in \{1,2\}$ and $b$ not divisible by $3^{j-1}$. However this technique does not seem to extend well to much larger primes than $3$. $\endgroup$
    – Terry Tao
    Commented Jan 16, 2022 at 16:07
  • 3
    $\begingroup$ @Wojowu Not that it is particularly helpful for this question, but primes of the form $2p+1$ where $p$ itself is prime are known as "safe primes". en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes $\endgroup$
    – Terry Tao
    Commented Jan 16, 2022 at 16:10

1 Answer 1

Reset to default
7
$\begingroup$

Here is some computational evidence that $n\in\{1,2,4\}$ are the only $n$ that deliver an integer sum.

For an odd prime $p$, let $a_p < b_p$ denote two smallest even positive integers such that $a_pp+1$ and $b_pp+1$ are prime. Then $n\in \big[a_pp+1,\min\{b_pp+1,p^2\}\big)$ cannot deliver an integer sum as its denominator will necessarily contain $p$. Here are these intervals for primes $p<100$:

3 [7, 9)
5 [11, 25)
7 [29, 43)
11 [23, 67)
13 [53, 79)
17 [103, 137)
19 [191, 229)
23 [47, 139)
29 [59, 233)
31 [311, 373)
37 [149, 223)
41 [83, 739)
43 [173, 431)
47 [283, 659)
53 [107, 743)
59 [709, 827)
61 [367, 733)
67 [269, 1609)
71 [569, 853)
73 [293, 439)
79 [317, 1423)
83 [167, 499)
89 [179, 1069)
97 [389, 971)

As we can see primes 5, 11, 29, 41, 67 alone cover the interval $[11, 1609)$, while others provide extensive backup support. Such a pattern will likely continue to cover all integers above $11$. However I'm not sure whether this observation can be justified theoretically without relying on unproved conjectures.

ADDED. Primes 5, 11, 29, 41, 67, 743, 7823, 165293, 6215171 cover the interval $[11,1131161123)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can confirm that Mathematica finds only the solutions $n=1,2,4$ up to 10,000. $\endgroup$
    – Brian Hopkins
    Commented Jan 15, 2022 at 15:15
  • $\begingroup$ @BrianHopkins: Adding just one more prime 743 into consideration extends the absence of solutions to the interval $[11,19319)$. $\endgroup$
    – Max Alekseyev
    Commented Jan 15, 2022 at 15:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .