48
$\begingroup$

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?

Improve this question
$\endgroup$
16
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pietro Majer
    Nov 20, 2012 at 17:24
  • 1
    $\begingroup$ Numerically, it seems to settle down quite rapidly! Also, because $n \neq m$, we can easily have $f(n)=f(m)$, makes it trickier.... $\endgroup$
    – Suvrit
    Nov 20, 2012 at 18:34
  • 4
    $\begingroup$ @quid: It takes $k+1$ iterates for $2(2^k+1)$ to become odd. $\endgroup$
    – Ramiro de la Vega
    Nov 20, 2012 at 19:50
  • 4
    $\begingroup$ 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.) $\endgroup$
    – Xander Faber
    Nov 20, 2012 at 20:37
  • 4
    $\begingroup$ 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$. $\endgroup$
    – François Brunault
    Nov 21, 2012 at 14:59

1 Answer 1

Reset to default
4
$\begingroup$

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 $.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Can I play with Mathness
    May 4, 2013 at 0:49
  • $\begingroup$ *For instance $p_{i+1}$ cannot divide $p_i+1$ $\endgroup$
    – Can I play with Mathness
    May 4, 2013 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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