How to prove or disprove this number theory proposition?

129 Views Asked by At

Problem

Define a function $f(\prod_{i=1}^{n}p _i^{k_i})=\prod_{i=1}^{n}p_i$ where the elements of a sequence $p$ are distinct primes and $k_i \ge 1$. Define the function $$ g(x)= \begin{cases} f(x)+1 & \text{if f(x)=x}\\ f(x) & \text{otherwise} \end{cases} $$ and define the function $$ g(x,y)= \begin{cases} g(x) & \text{if y=1}\\ g(g(x,y-1)) & \text{otherwise} \end{cases} $$ My conjecture is that for any positive integer $x \ge 2$, there is at least one positive integer $y$ such that $g(x,y)=2$. In fact, the number of $y$ s can only be $0$ or $\infty$.

How to prove or disprove this number theory proposition?

Maybe I need explain my function $f$. Here is the value of $f(x)$ at $2 \le x \le 20$ (abscissa is $x$, ordinate is $f(x)$)

Here is the value of <span class=$f(x)$ at $2 \le x \le 20$" />

My attempt

If $x$ does not satisfy the proposition, then there can be no multiple of $n^2$ between $x$ and $nx$, where $n$ is a positive integer greater than $1$. (But I'm not quite sure)

1

There are 1 best solutions below

0
On BEST ANSWER

the problem can be reformulated as following: Given a number $x$ there exists an $y \in \mathbb{N}$ such that $g^{y}(x)=2$ where $g^{y}$ is the composition of $g$ with itself $y$ times.

If $x$ is not a squarefree integer $g(x)=f(x)$ is a squarefree integer, by the definition of $f(x)$.

Given $4$ consecutive integers one of them has to be divisible by $4$, so there are at most $3$ consecutive squarefree integers.

If $x$ is a squarefree integer $g(x)=x+1$, so at least one between $g(x),g^{2}(x),g^{3}(x)$ or $g^{4}(x)$ is not a squarefree integer.

If $x$ is not a squarefree integer we have $f(x)=g(x) \le \frac{x}{2}$ as $x$ has to be divisible for $p^2$ with $p>2$ prime.

If $x=1,2,4$ $g(x)=2$, if $x=3$ $g^2(x)=2$. So let $x >4$ and define the sequence $\{g_i:=g^{i}(x)\}_{i \ge 1}$ and $g_0=x$. Let $k_0=0$. There exists $k_1 \in \{1,2,3,4,5\}$ such that $2 \le g_{k_1} \le \frac{x}{2}+\frac{k_1-1}{2} < g_{k_0}$ (because $g_{k_0}=x>4$) .

By iteration if $g_{k_{n-1}}>2$ there exists $k_n >k_{n-1}$ such that $$ g_{k_n} <g_{k_{n-1}} $$ (if $g_{k_{n-1}}=3$ we can choose $k_n=k_{n-1}+2$, if $g_{k_{n-1}}=4$ we can choose $k_n=k_{n-1}+1$. If $g_{k_{n-1}}>4$ we can choose $k_n$ by the same procedure as we have chosen $k_1$)

So the subsequence $\{g_{k_n}\}_{n \in \mathbb{N}}$ is a decreasing sequence and its infimum is $2$.

By the monotone convergence theorem we have $$ \lim_{n} g_{k_n}=\lim_n g^{k_n}(x)=2 $$ So there exists $N$ such that for any $n \ge N$ $$ |g^{k_n}(x)-2| < 1 $$ As $g^{k_n}(x)$ is an integer this implies that $g^{k_n}(x)=2$.