Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T21:21:42.318Z Has data issue: false hasContentIssue false

AN IMPROVEMENT TO A THEOREM OF LEONETTI AND LUCA

Published online by Cambridge University Press:  01 September 2023

TRAN NGUYEN THANH DANH
Affiliation:
VNU-HCM High School for the Gifted Students, Ho Chi Minh City, Vietnam e-mail: [email protected]
HOANG TUAN DUNG
Affiliation:
Hanoi National University of Education High School for the Gifted Students, Hanoi, Vietnam e-mail: [email protected]
PHAM VIET HUNG
Affiliation:
HUS High School for Gifted Students, Hanoi, Vietnam e-mail: [email protected]
NGUYEN DINH KIEN
Affiliation:
Tran Phu High School for the Gifted Students, Haiphong, Vietnam e-mail: [email protected]
NGUYEN AN THINH
Affiliation:
Tran Phu High School for the Gifted Students, Haiphong, Vietnam e-mail: [email protected]
KHUC DINH TOAN
Affiliation:
Bac Ninh High School for the Gifted Students, Báˇc Ninh, Vietnam e-mail: [email protected]
NGUYEN XUAN THO*
Affiliation:
School of Applied Mathematics and Informatics, Hanoi University of Science and Technology, Hanoi, Vietnam
Rights & Permissions [Opens in a new window]

Abstract

Leonetti and Luca [‘On the iterates of the shifted Euler’s function’, Bull. Aust. Math. Soc., to appear] have shown that the integer sequence $(x_n)_{n\geq 1}$ defined by $x_{n+2}=\phi (x_{n+1})+\phi (x_{n})+k$, where $x_1,x_2\geq 1$, $k\geq 0$ and $2 \mid k$, is bounded by $4^{X^{3^{k+1}}}$, where $X=(3x_1+5x_2+7k)/2$. We improve this result by showing that the sequence $(x_n)$ is bounded by $2^{2X^2+X-3}$, where $X=x_1+x_2+2k$.

Type
Research Article
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

1 Introduction

In a recent study of integer sequences generated by Euler’s totient function, Leonetti and Luca [Reference Leonetti and Luca3] proved the following theorem.

Theorem 1.1. Fix an even integer $k\geq 0$ . The integer sequence $(x_n)_{n\geq 1}$ defined by $x_{n+2}=\phi (x_{n+1})+\phi (x_{n})+k$ , where ${x_1,x_2\geq 1}$ , is bounded by $4^{X^{3^{k+1}}}$ , where ${X=(3x_1+5x_2+7k)/2}$ .

It is natural to ask whether the size of the upper bound for the sequence $(x_n)$ in Theorem 1.1 could be reduced. In this paper, we will provide such an improvement. The main result of this paper is the following theorem.

Theorem 1.2. Fix an even integer $k\geq 0$ . The integer sequence $(x_n)_{n\geq 1}$ defined by $x_{n+2}=\phi (x_{n+1})+\phi (x_{n})+k$ , where $x_1,x_2\geq 1$ , is bounded by $2^{2X^2+X-3}$ , where ${X=x_1+x_2+2k}$ .

Note that the bound in Theorem 1.2 is exponentially smaller than the bound in Theorem 1.1. To prove Theorem 1.2, we will use the Chinese remainder theorem in combination with some estimates on prime numbers due to Erdős (Lemma 2.4) and Rosser (Lemma 2.3).

2 Proof of Theorem 1.2

Case 1: $x_3=2$ . Since $k\geq 0$ , $2 \mid k$ and $\phi (x_1)+\phi (x_2)+k=x_3=2$ , we must have $k=0$ and $\phi (x_1)=\phi (x_2)=1$ . Hence, $x_1,x_2\in \{1,2\}$ . Note that if ${\phi (x_n)=\phi (x_{n-1})=1}$ , then $x_{n+1}=\phi (x_n)+\phi (x_{n-1})=2$ . By induction, $x_n=2$ for all $n\geq 3$ . Since $X=x_1+x_2+ 2k\geq 2$ , we have $2^{2X^2+X-3}>2$ . Hence, ${x_n< 2^{2X^2+X-3}}$ for all $n\geq 1$ .

Case 2: $x_3\geq 3$ . Then $x_{4}=\phi (x_3)+\phi (x_2)+k\geq 3$ . Note that if $x_n\geq 3$ with $n\geq 3$ , then

$$ \begin{align*}x_{n+1}=\phi(x_n)+\phi(x_{n-1})+k\geq 3+k\geq 3.\end{align*} $$

By induction, $x_n\geq 3$ for all $n\geq 3$ , so that $2 \mid \phi (x_n)$ for all $n\geq 3$ . Therefore, ${2 \mid \phi (x_{n-1})+\phi (x_{n-2})+k=x_n}$ for all $n\geq 5$ and so

(2.1) $$ \begin{align} \phi(x_n)\leq \dfrac{n}{2} \quad\mbox{for all } n\geq 5. \end{align} $$

Lemma 2.1. For $n=1,2,\ldots ,6$ ,

(2.2) $$ \begin{align} x_n< 2^{X}. \end{align} $$

Proof. We consider each value of n in turn.

$n=1$ or $n=2$ . Then (2.2) holds because $\max \{x_1,x_2\}<x_1+x_2\leq X<2^{X}$ .

$n=3$ . Then (2.2) holds because $3\leq x_3=\phi (x_1)+\phi (x_2)+k\leq x_1+x_2+k\leq X<2^{X}$ .

$n=4$ . Since $\phi (x_3)\leq x_3-1\leq x_1+x_2+k-1$ and $\phi (x_2)\leq x_2$ ,

$$ \begin{align*} x_4=\phi(x_3)+\phi(x_2)+k \leq x_1+2x_2+2k-1 <2X\leq 2^{X} \quad (\text{since}\ 2^X\geq 2X\ \text{for}\ X\geq 2). \end{align*} $$

$n=5$ . Since $\phi (x_4)\leq x_4-1\leq x_1+2x_2+2k-2$ and $\phi (x_3)\leq x_1+x_2+k-1$ ,

(2.3) $$ \begin{align} x_5=\phi(x_4)+\phi(x_3)+k &\leq 2x_1+3x_2+4k-3\nonumber\\[2pt]&=3(x_1+x_2+2k)-x_1-2k-3\nonumber\\[2pt]&\leq 3X-4\quad (\text{since}\ x_1+2k+3\geq 4)\nonumber\\[2pt]&<2^X \quad(\text{since}\ 2^X>3X-4\ \mathrm{for}\ X\geq 2). \end{align} $$

$n=6$ . By (2.1) and (2.3), $\phi (x_5)\leq x_5/2\leq (2x_1+3x_2+4k-3)/2$ . Combining this with the estimate $\phi (x_4)\leq x_1+2x_2+2k-2$ gives

$$ \begin{align*} x_6=\phi(x_5)+\phi(x_4)+k &\leq \dfrac{2x_1+3x_2+4k-3}{2}+(x_1+2x_2+2k-2)+k\\[4pt]&=\dfrac{4x_1+7x_2+10k-7}{2} =\dfrac{7(x_1+x_2+2k)}{2}-\dfrac{3x_1+4k+7}{2}\\&\leq \dfrac{7}{2}X-5\quad(\text{since}\ (3x_1+4k+7)/2\geq 5\\&<2^X\quad(\text{since}\ 2^X>7X/2-5\ \text{for}\ X\geq 2).\\[-35pt] \end{align*} $$

We now return to the proof of Theorem 1.2 when $x_3\ge 3$ (Case 2).

Case 2.1: $k=0$ . Then $x_n=\phi (x_{n-1})+\phi (x_{n-2})$ for all $n\geq 3$ . By (2.1),

(2.4) $$ \begin{align} x_{n+2}=\phi(x_{n+1})+\phi(x_{n})\leq \dfrac{x_{n+1}}{2}+\dfrac{x_n}{2}\quad \text{for all}\ n\geq 5. \end{align} $$

An induction, using Lemma 2.1 and (2.4), shows that $x_n< 2^X$ for all $n\geq 1$ . Hence, $x_n<2^X<2^{2X^2+X-3}$ for all $n\geq 1$ .

Case 2.2: $k\geq 1$ . Let $p_1<p_2<\cdots <p_{2k+2}$ be the first $2k+2$ primes. By the Chinese remainder theorem, there exist infinitely many positive integers x such that

(2.5) $$ \begin{align} x\equiv - i \pmod{p_i}\quad \text{for all}\ i=1,2,\ldots,2k+2. \end{align} $$

Lemma 2.2. Let M be a positive integer satisfying the congruences (2.5) and such that $M\geq \max \{2^{X}-2k-2,kp_{2k+2}-k-2\}$ . Then, for all positive integers n,

(2.6) $$ \begin{align} x_{n}\leq M+2k+2. \end{align} $$

Proof. Since $M+2k+2\geq 2^{X}$ , by Lemma 2.1, (2.6) holds for $n=1,2,\ldots ,6$ . Suppose $n\geq 7$ and assume that Lemma 2.2 is not true. Let m be the smallest positive integer such that $x_m>M+2k+2$ . Then $x_{m-1},x_{m-2}\leq M+2k+2$ and $m\geq 7$ . Thus, $2 \mid x_{m-1}, x_{m-2}$ . Therefore,

$$ \begin{align*} M+2k+2<x_m=\phi(x_{m-1})+\phi(x_{m-2})+k\leq \dfrac{x_{m-1}}{2}+\dfrac{x_{m-2}}{2}+k \end{align*} $$

and so $x_{m-1}+x_{m-2}>2M+2k+4$ . It follows that $x_{m-1},x_{m-2}>M+2$ since $x_{m-1},x_{m-2}\leq M+2k+2$ . Let $x_{m-1}=M+2+r$ and $x_{m-2}=M+2+s$ , where $r,s\in {\mathbb{Z}} $ and $0< r,s\leq 2k$ . Since M satisfies (2.5), there exist odd primes $p,q\leq p_{2k+2}$ such that $p \mid M+2+r=x_{m-1}$ and $q \mid M+2+s=x_{m-2}$ . Therefore, $2p \mid x_{m-1}$ and $2q \mid x_{m-2}$ . Recalling that $x_{m-1},x_{m-2}\leq M+2k+2$ and $p,q\leq p_{2k+2}$ ,

$$ \begin{align*} x_{m}=\phi(x_{m-1})+\phi(x_{m-2})+k &\leq \dfrac{x_{m-1}}{2}\bigg(1-\dfrac{1}{p}\bigg)+\dfrac{x_{m-2}}{2}\bigg(1-\dfrac{1}{q}\bigg)+k\\ &\leq 2\cdot \dfrac{M+2k+2}{2}\bigg(1-\dfrac{1}{p_{2k+2}}\bigg)+k \\ &= (M+2k+2)\bigg(1-\dfrac{1}{p_{2k+2}}\bigg)+k\\ &\leq M+2k+2\quad (\text{since}\ M+2k+2\geq p_{2k+2}k), \end{align*} $$

which contradicts the assumption that $x_m>M+2k+2$ . Therefore, (2.6) holds for all positive integers n. Lemma 2.2 is proved.

Lemma 2.3 (Rosser [Reference Rosser4, Theorem 2])

For all positive integers $n\geq 4$ ,

$$ \begin{align*}p_n<n(\log n+ 2\log \log n),\end{align*} $$

where $p_n$ is the nth prime and $\log $ denotes the natural logarithm.

Lemma 2.4 (Erdős [Reference Erdős2]; see Aigner and Ziegler [Reference Aigner and Ziegler1, Ch. 2, page 10])

For all positive integers $n\geq 2$ ,

$$ \begin{align*}\prod_{p\leq n}p\leq 4^{n-1},\end{align*} $$

where the product is taken over all primes $p\leq n$ .

Lemma 2.5. For all positive integers $n\geq 4$ ,

(2.7) $$ \begin{align}p_{n}<n^2,\end{align} $$
(2.8) $$ \begin{align} p_1p_2\cdots p_{n}<4^{n^2-1}.\end{align} $$

Proof. It is a routine verification that $\log {x}+2\log {\log {x}}<x$ for all $x>1$ . Hence,

(2.9) $$ \begin{align}n(\log{n}+2\log\log{n})<n^2.\end{align} $$

Then (2.7) follows from Lemma 2.3 and inequality (2.9).

Inequality (2.8) is a consequence of Lemma 2.4 and (2.7). Indeed,

$$ \begin{align*} p_1p_2\cdots p_n\leq 4^{p_n-1} < 4^{n^2-1}.\\[-33pt] \end{align*} $$

We return to the proof of Theorem 1.2. Let $\alpha $ be the smallest positive integer satisfying (2.5). Then $\alpha \leq p_1p_2\cdots p_{2k+2}$ . Note that $4\leq 2k+2\leq 2k+x_1+x_2=X$ . It follows from (2.8) that

(2.10) $$ \begin{align} \alpha\leq p_1p_2\cdots p_{2k+2}< 4^{(2k+2)^2-1} \leq 4^{X^2-1}. \end{align} $$

Let $M=\alpha +2^{x_1+x_2}p_1p_2\cdots p_{2k+2}$ . Then M satisfies (2.5). Since $p_1p_2\cdots p_{2k+2}>2^{2k}$ and $p_1p_2\cdots p_{2k+2}>p_kp_{2k+2}>kp_{2k+2}$ ,

$$ \begin{align*}M>2^{x_1+x_2}p_1p_2\cdots p_{2k+2}>2^{x_1+x_2}2^{2k}=2^X\end{align*} $$

and

$$ \begin{align*}M>p_1p_2\cdots p_{2k+2}>kp_{2k+2}.\end{align*} $$

Thus, M satisfies all the conditions in Lemma 2.2. Hence,

(2.11) $$ \begin{align}x_n\leq M+2k+2 \quad\text{for all}\ n\geq 1.\end{align} $$

Since $x_1+x_2=X-2k\leq X-2$ , by (2.10),

(2.12) $$ \begin{align} M=\alpha+2^{x_1+x_2}p_1p_2\cdots p_{2k+2} < (1+2^{X-2})\cdot 4^{X^2-1}. \end{align} $$

Note that $X\leq 2^{X-2}$ since $X\geq 4$ . Thus,

(2.13) $$ \begin{align}2k+2\leq 2k+x_1+x_2=X\leq 2^{X-2}.\end{align} $$

Combining (2.12) and (2.13) gives

(2.14) $$ \begin{align} M+2k+2\leq M+2^{X-2}&< (1+2^{X-2})\cdot 4^{X^2-1}+2^{X-2}\nonumber\\ & <2^{X-2}\cdot 4^{X^2-1}+2^{X-2}\cdot 4^{X^2-1}=2^{2X^2+X-3}.\end{align} $$

It follows from (2.11) and (2.14) that $x_n<2^{2X^2+X-3}$ for all $n\geq 1$ . This completes the proof of Theorem 1.2.

Remark 2.6. Leonetti and Luca [Reference Leonetti and Luca3] also proved that the integer sequence $(x_n)_{n\geq 1}$ defined by $x_{n+1}=\phi (x_n)+k$ , where $x_1\geq 1$ and $k\geq 0$ , is bounded by ${\max \{x_1,k^4\}+(k+1)^2}$ . A similar argument to that in the proof of Theorem 1.2 shows that the sequence $(x_n)$ is bounded but with a worse upper bound.

Remark 2.7. It is an open question to find the best possible bound (in terms of $x_1,x_2$ and k) for the sequence $(x_n)$ in Theorems 1.1 and 1.2.

Acknowledgements

This project started during a training session of the Vietnam team preparing for the 2023 International Mathematical Olympiad (IMO). The first six authors are the members of the Vietnam 2023 IMO team. The idea of using the Chinese remainder theorem is due to Dung and Hung. Dung won a silver medal in IMO 2023 and Hung won gold medals in both IMO 2022 and IMO 2023.

We would like to thank the Vietnam Institute for Advanced Study in Mathematics (VIASM) for their support. We would like to thank Professor Le Anh Vinh (the IMO team leader), Doctor Pham Duc Hiep and Master Tran Quang Hung for giving us the opportunity to work together.

Footnotes

Nguyen Xuan Tho is funded by the Vietnam Ministry of Education and Training under the project number B2022-CTT-03.

References

Aigner, M. and Ziegler, G. M., Proofs from The Book, 6th edn (Springer, Berlin, 2018).CrossRefGoogle Scholar
Erdős, P., ‘Beweis eines Satzes von Tschebyschef’, Acta Sci. Math. (Szeged) 5 (1930–1932), 194198.Google Scholar
Leonetti, P. and Luca, F., ‘On the iterates of the shifted Euler’s function’, Bull. Aust. Math. Soc., to appear. Published online (12 May 2023).CrossRefGoogle Scholar
Rosser, J. B., ‘The $n$ -th prime is greater than $n \log n$ ’, Proc. Lond. Math. Soc. (3) 45 (1939), 2144.CrossRefGoogle Scholar