47
$\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .