4
$\begingroup$

Define a function $F$ on the natural numbers $\geq 2$ as follows: Start with $a \geq 2$ and let $b$ be the smallest prime divisor of $a$ and $c:=a+b$ and let $d$ denote the largest prime divisor of $c$. Define $F(a):=c-d$. Define the period $p(a)$ of a natural number as $p(a):= \inf \{ i | F^{i}(a)=F^{i-1}(a) \}.$

Here an example:

Let a=832 with smallest prime divisor 2.

Then b=2 and c=834 with largest prime divisor d=139. Then $F(a)$=834-139=695.

Now $a_2=695$ has smallest prime divisor 5 and $c_2=700$ has largest prime divisor 7 and thus $F^2(a)=700-7=693$.

Now $a_3=693$ has smallest prime divisor 3 and $c_3=696$ has largest prime divisor 29 and thus $F^3(a)=696-29=667$.

Now $a_4=667$ has smallest prime divisor 23 and $c_4=690$ has largest prime divisor 23 and thus $F^4(a)=667=F^3(a)$.

Question: Is there an explicit formula for $p(a)$ or a good bound? Has it been considered before?

For integers smaller than or equal to 50000 the largest period was 16 reached at the three numbers 21404, 25515, 25516.

It might also be intersting to look at variations of the function $F$. For example one might take first the largest prime divisor and then the smallest (when starting with a non-prime).

$\endgroup$

2 Answers 2

3
$\begingroup$

As defined, $d \geq b$ , so iterating $F$ will lead to a fixed point $qr$, a product of a prime $q$ which is no larger than any prime factor of $r$ and such that $(r+1)$ is $q$-smooth. Most of the time, $F(a)$ will be odd, and often will be smaller than $a$ by an amount at least as large as $\sqrt{a}$. This suggests the period of $a$ is $O(\sqrt{a})$, and probably the period is much smaller.

As $a$ decreases by even numbers, I expect $b$ to be small with a frequency about as expected, meaning that about 7/15 of the values of $b$ will be 3 or 5. A nice quantity to know is $\mid \{ a \leq n: F(a)=a\}\mid/n$, the density of fixed points. This will likely be near 1/average length of period, but that is another guess. They will be at least as dense as somewhat smooth numbers: for numbers $c$ whose largest prime factor is $q$ and have many small prime factors, $c-q$ will often be a fixed point for $F$.

Guy's book Unsolved Problems In Number Theory has problems involving iterated number theoretic functions. It would be a good starting point for a literature search on this kind of problem.

Gerhard "Still Studying Dynamics Of Primes" Paseman, 2018.06.18.

$\endgroup$
1
  • $\begingroup$ Another interesting statistic to consider is the density of those numbers r whose least prime factor q is greater than p, the greatest prime factor of r+1. Then for any prime s in [p,q], sr will be a fixed point of F. It may end up relating to jumping primes. Gerhard "For More See Question 243490" Paseman, 2018.06.18. $\endgroup$ Jun 18, 2018 at 23:04
2
$\begingroup$

I decided to run a program to verify the values for F and compute numbers with champion periods. The 3 champions for 16 were verified, and 9178001 (and 005 and 006, sorry Mr. Bond) was computed to have a period of 41, the largest below 10^7. These three depended upon 9123377 having period 40.

I also computed the number of composite fixed points below 10^7 (all primes are fixed points and thus have period 1), and found 420263, which is less than the number of primes below 10^7, and less than I had supposed. (I actually stopped the loop at the next prime above 10^7, so the reported number may be off by 1 or 2 from reality.) Even though the maximal period seems to grow logarithmically, it has many silent places (large intervals with no report, e.g. (277730,912949) all have period less than 26). I also recorded the number F(m) for each champion m and most of the time 0.9m is less than F(m), which suggests the fixed point for a champion m is not much smaller than m (perhaps greater than m/3?)

The behaviour of maximal period growth reminds me of growth of similar statistics of the one complexity (integer complexity) of integers. For recent work on integer complexity, see Harry Altman's ArXiv submissions.

Gerhard "Primes Often Feel Complexly Random" Paseman, 218.07.11.

$\endgroup$

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.