A function whose fixed points are the primes

Question

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?

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
@Ramiro de la Vega: Thanks! I delete now my comment to which you reply, since the heuristic part contains a stupid error and also as a general principle it seems a bit invalidated by your example. [For the record: the question I asked was for examples of arbitrarily large preperiod.] — , Nov 20 '12 at 23:10
very nice... I'd like to see a formulation for the inverse operation (which must have a "choice"-option). I did not yet get it myself correctly myself ... — Gottfried Helms, Nov 21 '12 at 00:43
The first primes, which have no leading sequence of composites is $3,7,13,31,37,61,73,79,97,109,127,157,193,199,223,229,241,271,277,283,$ — Gottfried Helms, Nov 21 '12 at 01:07
Another problem of the same flavor (and just as difficult) is $f(n)=\sigma(n)-1$, where $\sigma(n)$ is the sum of the divisors of $n$. — Andreas Weingartner, Nov 21 '12 at 03:06
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
Let's call "functional spectrum" of a set of positive integers $E$ the set $S(E)$ of arithmetical functions whose $E$ exactly is the set of fixed points, and let's further define the group of automorphisms of $S(E)$ as the group of bijective maps from $S(E)$ to itself. Maybe determining the structure of this group could give some information on $E$ or shed a light on your question. — Sylvain JULIEN, Nov 21 '12 at 20:04
Consider integers of the form $n=pm$ with $m$ having no prime factor less than $p$. Then $f(n)=(p+1)m-1$. By Dirichlet's theorem on arithmetic progressions, there are infinitely many $m$ such that $(p+1)m-1$ is prime, and we may choose $m$ with no prime factor less than $p$ by requiring for example $m \equiv 1 \pmod{(p-1)!}$. This shows that there are infinitely many preperiodic composite numbers. What about a lower bound for the density of such numbers? — François Brunault, Nov 21 '12 at 20:44
Is the choice of the largest proper divisor an essential one? That is, suppose we define a relation $R$ such that $a R b$ if $a<b$ and $b-a+1$ is a proper divisor of $a$. Perhaps there's not even an infinite $R$-chain of distinct natural numbers. — James Cranch, Nov 28 '12 at 20:39
@Rodrigo: What is the motivation for the particular choice of the function $f$? - I suppose there are many similar functions involving primes and divisors whose behavior under iteration is hard to describe. So what makes your function of special interest? — Stefan Kohl, Jan 12 '13 at 20:45
Computed for n up to 10000000 : record holder 6730914 with orbit length 226 . — jjcale, May 05 '13 at 07:09
@jjcale: Thanks! Do you have that data available? I only went up to 100,000 many years ago. — Rodrigo A. Pérez, May 06 '13 at 02:08
@Rodrigo: I used PARI/GP : f(n)=n+n/vecmin(factor(n)[,1])-1 g(n)=while(1,my(m);m=f(n);if(n==m,break);print(m);n=m;) g2(n)={my(m);my(i=0);while(1,m=f(n);i++;if(n==m,break);n=m;);[m,i]} g2max(n)={ my(m=[0,0]); for(i=2,n, my(p=g2(i)); if(p[2] > m[2],m=[i,p[2]]); ); m; } — jjcale, May 15 '13 at 18:19

score 4 · Answer 1 · answered May 01 '13 at 15:24

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

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$. — Can I play with Mathness, May 04 '13 at 00:49

A function whose fixed points are the primes

1 Answers1