Formulas for Euler’s Totient Function

Published on July 6, 2024

I wish to share some intriguing formulas that I have recently discovered for Euler’s totient function, denoted as $\varphi(n)$ .

Formulas

I claim that these formulas are proved, though I omit the details for now. The formulas and their proofs will soon be added to a recent paper of mine: Elementary Formulas for Greatest Common Divisors and Semiprime Factors.

For all $n \in \mathbb{Z}_{>1}$ , we have:

(1) $\begin{align*} \varphi(n) &= \left( 1 - \sum_{k=2}^{n-1} \left(n^{nk-k+1} \bmod((n^n-1)(n^k-1))\right) \right) \bmod n \end{align*}$

(2) $\begin{align*} \varphi(n) &= \left( 1 + \sum_{k=2}^{n-1} \left\lfloor \frac{n^{nk-k+1}}{(n^n-1)(n^k-1)} \right\rfloor \right) \bmod n \end{align*}$

(3) $\begin{align*} \varphi(n) &= \left( 1 + \sum_{k=2}^{n-1} \left(n^{nk-k+1} \bmod(n^{\gcd(n,k)}-1) \right) \right) \bmod n \end{align*}$

Conjectures

I leave the following as conjectures.

Conjecture 1. Let $n \in \mathbb{Z}_{>1}$ such that $n$ is not congruent to $\{ 2,10 \}$ mod $12$ . Then

(4) $\begin{align*} \varphi(n) = 1 + \left\lfloor \sum_{k=1}^{n-1} \frac{n^{nk-k+1}}{(n^n-1)(n^k-1)} \right\rfloor \bmod n , \end{align*}$

(5) $\begin{align*} \varphi(n) = 1 + \left\lfloor (n^n-1)^{-1} \sum_{k=1}^{n-1} \frac{n^{nk-k+1}}{n^k-1} \right\rfloor \bmod n , \end{align*}$

and

(6) $\begin{align*} \varphi(n) = 1 + \left\lfloor (n^n-1)^{-1} \left(n - 2 + \sum_{k=1}^{n-1} \frac{n^{nk+1}}{n^k-1} \right) \right\rfloor \bmod n . \end{align*}$

Otherwise

(7) $\begin{align*} \varphi(n) = \left\lfloor \sum_{k=1}^{n-1} \frac{n^{nk-k+1}}{(n^n-1)(n^k-1)} \right\rfloor \bmod n . \end{align*}$

Conjecture 2. Let $n \in \mathbb{Z}_{>1}$ such that $n$ is not a phi-practical number whose divisors have distinct values of the Euler totient function (See A359417). Then

(8) $\begin{align*} \varphi(n) = \left[ \sum_{k=1}^{n-1} \frac{n^{nk-k+1}}{(n^n-1)(n^k-1)} \right] \bmod n \end{align*}$

and

(9) $\begin{align*} \varphi(n) = \left[ (n^n-1)^{-1} \sum_{k=1}^{n-1} \frac{n^{nk-k+1}}{n^k-1} \right] \bmod n , \end{align*}$

where the term inside of the brackets is rounded to the nearest integer.

Conjecture 3. Let $n \in \mathbb{Z}_{>0}$ . Then

$\begin{align*} \sum_{k=1}^n \varphi(n) = \deg\left( \mathrm{denominator}\left( \sum_{k=1}^{n} \frac{1}{x^k-1} \right) \right) . \end{align*}$

Conjecture 4. Let $n \in \mathbb{Z}_{>3}$ . Then

$\begin{align*} \sum_{k=1}^n \varphi(n) = \log_{\pi^2} \left( \mathrm{denominator}\left( \sum_{k=1}^{n} \frac{1}{\pi^{2k}-1} \right) \right) + O(1) . \end{align*}$

Conjecture 5.
Let $n \in \mathbb{Z}_{>0}$ . Then

$\begin{align*} \sum_{k=1}^n \varphi(n) = \log_{2} \left( \mathrm{denominator}\left( \sum_{k=1}^{n} \frac{1}{2^k-1} \right) \right) + O(\log n) . \end{align*}$

Conjecture 6.

$\begin{align*} \varphi(n) = \left\lfloor \log_{2} \left( \frac{\text{lcm}(2^1-1,2^2-1,\ldots,2^n-1)}{\text{lcm}(2^1-1,2^2-1,\ldots,2^{n-1}-1)} \right) \right\rfloor + \tau(n) , \end{align*}$

where $\tau(n)$ returns $1$ if $n$ is a product of exactly two distinct primes, and $0$ otherwise.

josephshunia

Categories:

discoveries

formulas

Comments are closed.