Erdős problem 409 ("How many iterations of$n↦\phi(n)+1$ are needed before a prime is reached? Can infinitely many$n$ reach the same prime? What is the density of$n$ which reach any fixed prime?") has been extended to$\mathbb{N}^2$ inthis post, by the nonlinear recurrence$$x_n=1+\frac{\phi(x_{n-1})+\phi(x_{n-2})}2,\;\;\;x_0,x_1\gt2$$where$\phi$ is Euler's totient function.

This extension:

• $(1)$ preserves primes as fixed points of the function;
• $(2)$ ensures that the image of the function is contained in$\mathbb{N}$;
• $(3)$ ensures that the function is indeed a contraction.

I ask if it is possible to do the same in$\mathbb{N}^3$.

A quite natural choice would be$$x_n=1+\frac{\phi(x_{n-1})+2\phi(x_{n-2})+3\phi(x_{n-3})}6$$but, unfortunately, it does not satisfy the second constraint everywhere.

Many thanks.

• $\begingroup$Not sure what you are after. Of course, you can always add a floor or ceiling function to force the result to be an integer.$\endgroup$

  lulu

  – lulu

  2025-11-10 18:08:35 +00:00

  CommentedNov 10 at 18:08

0

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.