1
$\begingroup$

While studying the quantity

$$ f(n) = \frac{\varphi(n) + \varphi(\varphi(n)) + \varphi(\varphi(\varphi(n))) + \cdots + 2 + 1}{n} $$

where $\varphi(n)$ is the Euler totient function, I saw that the smallest value of $n$ for which $f(n)$ is greater than any previous values of $f$ occur at $n = 5,11,17,83,137,257,2879, 46049$ and $65537$. Of these, $5,17,257$ and $65537$ are Fermat primes while the remaining numbers are regular primes. But because the Fermat and the regular primes come out as points at which the maximal value of $f$ occur, hence there must be something connecting the two types. Sure enough, there is such a connection.

Define the recurrence relationship $\varphi_k(1) = 0, \varphi_1(n) = \varphi(n)$ and $\varphi_{k+1}(n) = \varphi(\varphi_k(n))$.

The numbers $5, 11, 17, 83, 137, 257, 2879, 46049$ and $65537$ are primes $p$ such that for all $k$ if $\varphi_k(p) > 1$ then, $\varphi_k(p) = 2^a q$ for some integer $a \ge 0$ and prime $q$. Thus Fermat primes are a special case of primes having this property which we shall for the sake of convenience call Generalized Fermat primes.

Example for Fermat Primes. $$\varphi_1(17) = \varphi(17) = 16 = 2^3 2$$

$$\varphi_2(17) = \varphi(16) = 8 = 2^2 2$$

$$\varphi_3(17) = \varphi(8) = 4 = 2^1 2$$

$$\varphi_4(17) = \varphi(4) = 2 = 2^0 2 $$

Example for non-Fermat Primes.

$$\varphi_1(83) = \varphi(83) = 82 = 2^1 41$$

$$\varphi_2(83) = \varphi(82) = 40 = 2^3 5$$

$$\varphi_3(83) = \varphi(40) = 16 = 2^3 2$$

$$\text{and so on ...}$$

Question: Although it is not proven, there are heuristic arguments to show that the number of Fermat primes is finite. I am looking for a heuristic arguments for generalized Fermat primes.

Update: Apart from the above $9$ generalized Fermat primes, I haven't found any other till $5 \times 10^8$.

$\endgroup$
  • 1
    $\begingroup$ "Generalized Fermat primes" is a cute name. On OEIS they are called "totient superabundant numbers": oeis.org/A286268 Out of curiosity, have you already proven that all of these values must be prime or found some source that proves it? $\endgroup$ – CosmoVibe Oct 9 at 18:29
  • $\begingroup$ @CosmoVibe Lol I had no idea it was already there :). Yes I can prove that the maximal values of $f(n)$ must occur at GFPs. $\endgroup$ – Nilotpal Kanti Sinha Oct 9 at 18:31
  • 1
    $\begingroup$ @NilotpalKantiSinha "generalized fermat primes" is usually the name for primes of the form $$a^{2^n}+1$$ hence the choice of the name is unlucky. $\endgroup$ – Peter Oct 11 at 9:33

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.