MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $a(n) = (\text{largest proper divisor of } n)$, let $f:\mathbb{N} \setminus \{ 0,1\} \to \mathbb{N}$ be defined by $f(n) = n+a(n)-1$. For instance, $f(100)=100+50-1=149$. Clearly the fixed points of $f$ are the primes.

Is every number preperiodic? In other words, is $f(f(\ldots(f(n)\ldots))$ eventually prime?

share|cite|improve this question
Primes are also all the periodic points of $f$. So, to answer in the affirmative it would be sufficient to show that all orbits are bounded --which seems a difficult task, however. – Pietro Majer Nov 20 '12 at 17:24
Numerically, it seems to settle down quite rapidly! Also, because $n \neq m$, we can easily have $f(n)=f(m)$, makes it trickier.... – Suvrit Nov 20 '12 at 18:34
@quid: It takes $k+1$ iterates for $2(2^k+1)$ to become odd. – Ramiro de la Vega Nov 20 '12 at 19:50
Just computed for n up to 100,000; always preperiodic with orbit length at most 77. (Current record holder for orbit length is n=93040.) – Xander Faber Nov 20 '12 at 20:37
Here are some heuristics suggesting the question could have a positive answer. The probability that $f^m(n)$ is prime is roughly $1/\log f^m(n)$. We have $f^m(n) \leq (3/2)^m n$ so the probability that all $f^m(n)$ are composite is less than $\prod_m 1-\frac{1}{\alpha m}$ with $\alpha = \log(3/2) >1$, and this infinite product tends to 0. Of course there are some biases, for example $n$ is odd already implies that $f(n)$ is odd, so the events "$f^m(n)$ prime" are not independent with respect to $m$. – François Brunault Nov 21 '12 at 14:59

The problem may have connections with 3x+1 problem. To an integer, I can associate $(p_0,p_1,\cdots)$ the sequence of the least prime divisor of the term of the sequence $u_{n+1}=f(u_n)$ which may have same properties as the parity function in the 3x+1 problem. For instance : the asymptotic periodicity of $(p_n)$ is equivalent to periodicity of $u_n$ (thus convergence). I would like to prove that for all composite integer,there exists a prime that appear infinitly many times in the sequence $(p_n)$. Using some asymptotic estimations, it's not difficult to prove: $\forall N>0,\exists p | card \lbrace n \in \mathbb N | p_n=p\geq N\rbrace $. It makes no use of the fact that $p_n$ is the least divisor of $u_n$.

It would be interesting to have two other theorems "3x+1"-like : The sequence $(p_n)$ determines $u_0$ and $\sum_{n=0}^{\infty}\prod_{k\leq n} \frac{p_k}{p_k +1}=u_0$ The sum converges since we have the inequality $\sum_{n=0}^{\infty} \prod_{k\leq n} \frac{p_k}{p_k +1}\leq u_0$.

I would be very interested by the links between the choice of a sequence $(p_n)$ and the convergence in an appropriate space of the prime sum. In the "3x+1"-equivalent would be $\sum \frac{2^{a_k}}{3^k}$, where $a_k=$ number of even terms before the $k^{th}$ odd term, which converges in $\mathbb{Z}_2$. In the 3x+1 problem generalized to $\mathbb{Z}_2$, the sum establish a bijection between parity functions and initial conditions in $\mathbb{Z}_2$.

Furthermore is it true that for any k-uplet of prime number $(l_0,\cdots,l_N)$ there exists an initial condition such that $p_i=l_i, i\leq N $.

share|cite|improve this answer
update : -$u_0 \mapsto (p_n)n∈\mathbb{N}$ is injective. -The rest of the sum is $o(1/n)$. -If the sum converges toward $u_0$ and the set of $p_k$ if finite then $u_0$ is preperiodic. -There are obstructions to the existence of a $u_0$ with given behaviour $(p_0,p_1,\cdots,p_n)$. For instance $p_{i+1}$ cannot divide $p_i$. – Illustre inconnu May 4 '13 at 0:49
*For instance $p_{i+1}$ cannot divide $p_i+1$ – Illustre inconnu May 4 '13 at 0:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.