Easy Number Theory

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Easy Number Theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: SMO 2020/1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#1 h Aug 28, 2020, 6:06 PM

Y by

The sequence of positive integers $a_0, a_1, a_2, \ldots$ is recursively defined such that $a_0$ is not a power of $2$ , and for all nonnegative integers $n$ :

(i) if $a_n$ is even, then $a_{n+1}$ is the largest odd factor of $a_n$
(ii) if $a_n$ is odd, then $a_{n+1} = a_n + p^2$ where $p$ is the smallest prime factor of $a_n$

Prove that there exists some positive integer $M$ such that $a_{m+2} = a_m$ for all $m \geq M$ .

Proposed by Andrew Wen

This post has been edited 5 times. Last edited by jj_ca888, Aug 28, 2020, 6:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1350 posts

i3435

#2 h Aug 28, 2020, 9:31 PM • 1 Y

Y by Mango247

Sol

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

245 posts

gnoka

#3 h Aug 29, 2020, 12:35 AM

Y by

Excuse me， what is the full name of SMO？

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1201 posts

#4 h Aug 29, 2020, 1:40 AM • 1 Y

Y by gnoka

gnoka wrote:

Excuse me， what is the full name of SMO？

Summer Math Olympiad

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

245 posts

gnoka

#5 h Aug 29, 2020, 8:30 AM

Y by

brianzjk wrote:

gnoka wrote:

Excuse me， what is the full name of SMO？

Summer Math Olympiad

thanks very much

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

238 posts

#6 h Apr 2, 2021, 11:14 PM

Y by

Assume WLOG $a_1$ is odd. Observe that if $p_1$ is the smallest prime factor $a_1 \implies p_1|a_2=a_1+p_1^2 \implies p_1|a_n \quad \forall n \in \mathbb{N}.$ Hence if $p_n$ is the smallest odd prime factor of $a_n$ , we have that $p_0 \geq p_1 \geq p_2 \geq ... \implies$ since this sequence is bounded below, we have that it is eventually constant, i.e., there exists an $N$ such that for all $n \geq N, p_{n+1}=p_n. \quad (*)$

Now, observe that if $a_n$ is odd and composite, $\implies a_{n+1}=a_n+p_n^2 \leq a_n + (\sqrt{a_n}^2)=2a_n \implies a_{n+2}= \frac{a_{n+1}}{2^{v_2(a_{n+1})}} < a_n \implies a_{n+2} < a_n$ . Thus, if $a_n$ is composite for all odd $a_n$ , $a_n$ is eventually negative, which is clearly a contradiction. Hence, there exists $m_0$ such that $a_{m_0}=q_0$ , where $q_0$ is an odd prime number.
$\implies a_{m_0+1}=q_0(q_0+1) \implies a_{m_0+2}= \frac{q_0(q_0+1)}{2^{v_2(q_0+1)}}$ .

If $\frac{q_0+1}{2^{v_2(q_0+1)}} >1 \implies$ we find $m_1>m_0$ such that $a_{m_1}$ is an odd prime, and defining $q_n$ in a similar way as previously, keep doing this until $\frac{q_n+1}{2^{v_2(q_n+1)}}=1$ or $m_n \geq N$ (from $(*)$ ). In both cases we are done! :-D

:-D

$\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

779 posts

#7 h Apr 3, 2021, 3:23 AM

Y by

Suppose FTSOC that such an $M$ does not exist, and assume $a_0$ is odd. Let $b_i=a_{2i}$ for all $i$ , and let $p_i$ denote the smallest prime factor of $b_i.$

$\textbf{Claim: }$ For all $i,$ there exists $j>i$ such that $p_i>p_j.$

$\emph{Proof: }$ If $b_i=p_i,$ then we have $b_{i+1}=\frac{p_i(p_i+1)}{2^{\nu_2(p_i+p_{i}^2)}}.$

If $p_i+1$ is a power of $2,$ then $b_{i+1}=b_{i},$ contradiction.
Otherwise, $p_i+1$ has a prime factor smaller than $p_i.$ .

On the other hand, if $b_i$ is composite, write $b_i=kp_i$ for some $k>p_i$ (check that $k=p_i$ is impossible). Then, note that $b_{i+1}=\frac{kp_{i}+p_{i}^2}{2^{\nu_2(kp_{i}+p_{i})^2}}\le\frac{kp_{i}+p_{i}^2}{2}<kp_{i}=b_i.$ Continuing in this manner, we will eventually reach $b_{i'}$ which is at most $p_i^2.$

If $b_{i'}=p_{i}^2,$ then $b_{i'}=b_{i'+2},$ contradiction.
If $b_{i'}=p_i,$ we are done by our previous work.
Otherwise, $b_{i'}$ has a prime factor smaller than $p_i,$ as desired.

$\blacksquare$

Since the set of odd primes has a minimum, we are done.

This post has been edited 3 times. Last edited by amuthup, Apr 3, 2021, 3:26 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#8 h Jan 14, 2022, 10:38 PM • 1 Y

Y by centslordm

Let $A_{x}=a_{2x}$ .

$p$ represents any generic prime. Note that the smallest prime divisor of the sequence cannot increase. Also, if $A_i$ isn't $p$ or $p^2$ , $A_{i+1}$ strictly decreases. Hence, we will eventually reach a number of the form $p$ or $p^2$ ; in the latter case we are done, and in the former case, notice that the smallest prime factor will strictly decrease, and if we never hit $p^2$ , we will eventually get to $A_i=p=2^k-1$ since $3=2^2-1$ , at which we achieve the periodicity.

This post has been edited 1 time. Last edited by mathleticguyyy, Jan 15, 2022, 3:19 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#9 h Sep 10, 2022, 1:37 AM

Y by

Obviously the smallest odd prime factor of $a_n$ is nonincreasing, hence eventually constant. Suppose that for every $n>N_0$ , the least prime divisor of $a_n$ is a fixed prime $p$ . If $a_n>p^2$ , then advancing two moves starting with (ii) (so then we do (i), and go back to (ii), etc.) will go from $a_n$ to at most $\tfrac{a_n+p^2}{2}$ , hence $a_n$ will strictly decrease. Suppose that for all $n>N_1>N_0$ we have $a_n \leq p^2$ . Then $a_n/p \in \{1,p\}$ for size reasons, else $p$ is not the minimal prime divisor. If $a_n/p=1 \implies a_n=p$ , then we go from $p \to p^2 \to \tfrac{p(p+1)}{2^{\nu_2(p+1))}}$ . Since this final fraction is strictly less than $p^2$ , we must have $\tfrac{p+1}{2^{\nu_2(p+1)}}=1$ , else this term has a smaller prime divisor than $p$ , in which case our fraction just equals $p$ so we have the desired periodicity. If $a_n/p=p \implies a_n=p^2$ (the easy case) we go $p^2 \to 2p^2 \to p^2$ so we're done here as well. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

821 posts

#10 h Jan 8, 2024, 12:06 AM • 1 Y

Y by OronSH

Solved with OronSH

Note that the smallest prime factor of each term is non increasing. Thus, after some point, it remains constant, say this is after the term $a_n=p\cdot k$ with $p$ being said factor (WLOG $k$ is odd, otherwise (i) is applied). We take $3$ cases.

If $k=1$ , then $a_{i+1}=p(p+1)$ . By assumption, $p+1$ thus must be a power of $2$ , hence $a_{i+2}=p$ again.
If $k=p$ then It oscillates between $p^2$ and $2p^2$
If $k>p$ , then $a_{i+2}\leq \frac{p(p+k)}{2}<pk=a_i$ . Thus the sequence is decreasing and thus either hits $p$ or $p^2$ .

This post has been edited 1 time. Last edited by GrantStar, Jan 8, 2024, 12:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8860 posts

#11 h Jun 21, 2024, 3:11 AM

Y by

For each $n$ , let $p_n$ denote the smallest prime factor of $a_n$ . Observe that the $\{a_n\}$ alternate parity, so we will assume WLOG that $a_n \equiv n \pmod 2$ .

Claim. $\{p_n\}$ is nondecreasing.

Proof. Clearly $p_n \neq 2$ , so if $a_n$ is even, then $p_n \mid a_{n+1}$ . If $a_n$ is odd, then $a_{n+1} = a_n + p_n^2$ is still a multiple of $p_n$ too. $\blacksquare$

It follows that there is some $N$ such that for all $n > N$ , $p_n = p$ is constant.

Claim. There is some $n > N$ such that $a_n \leq p^2$ .

Proof. If otherwise, then note that $a_{2n+1} \leq \frac 12 a_{2n}$ as $a_{2n}$ is always even, so
$a_{2n+1} \leq \frac 12 a_{2n} = \frac 12 (a_{2n-1} + p^2) < a_{2n-1}$ meaning that $\{a_{2n+1}\}$ is strictly decreasing. So it must drop below $p^2$ at some point, contradiction. $\blacksquare$

Consider the $a_n$ described by the claim. Clearly $p \mid a_n$ , but if $a_n = pk$ for $2 \leq k \leq p-1$ , then there is a smaller prime factor of $a_n$ than $p$ , contradiction. Hence either $a_n = p$ or $a_n = p^2$ .

If $a_n = p^2$ , then $a_{n+1} = 2p^2$ and $a_{n+2} = p^2$ , and the conclusion follows immediately. If $a_n = p$ , either $p+1$ is a power of two, or it has an odd prime factor less than $p$ . The latter case yields a contradiction, and the former case yields $a_{n+2} = p$ , so again $\{a_n\}$ is periodic with period $2$ . This finishes the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

719 posts

#12 h Nov 20, 2024, 7:22 PM

Y by

This is a similar one.
Let $p_i$ be the smallest odd prime divisor of $a_i$ . First, if $a_n$ is even then $p_n|a_{n+1}$ hence $p_{n+1}\leq p_n$ . Also if $a_n$ is odd, then $a_{n+1}=p_n(p_n+\frac{a_n}{p_n})$ which implies $p_{n+1}\leq p_n$ again. Since $\{p_i\}$ is nondecreasing and is a set of primes, this seuqence must be constant evantually. Let this constant prime be $p$ . Let $p_n=p$ for $n\geq T$ . Consider some constant $C>a_i$ for $i\geq T^T$ . If $a_l$ is even, then $a_{l+1}<a_l$ and if $a_l$ is odd, then $a_{l+1}=p^2+a_l<2C$ and $a_{l+2}\leq \frac{a_{l+1}}{2}=\frac{p^2+a_l}{2}<C$ hence $a_i<2C$ for all $i$ . Note that there is an $a_k$ repeating at least twice (actually for infinitely many times) and $a_k=a_l$ causes $a_{k+i}=a_{l+i}$ hence this sequence becomes periodic. Let $a_i=pb_i$ for $i\geq T$ .
$2^{r_1}pk_1\rightarrow pk_1\rightarrow 2^{r_2}pk_2\rightarrow pk_2\rightarrow \dots \rightarrow 2^{r_m}pk_m\rightarrow pk_m\rightarrow 2^{r_1}pk_1$ Also we have the equations $p(p+k_i)=2^{r_{i+1}}pk_{i+1}$ or $p+k_i=2^{r_{i+1}}k_{i+1}$ . By adding these we get $pm\geq k_1+\dots + k_m$ and since $k_i=1$ or $k_i\geq p+1$ , we observe that there must exist some $k_i=1$ . WLOG $k_1=1$ . However, $p+1=2^{r_2}k_2\geq 2k_2$ thus, $k_2=1$ . Similarily, $k_1=k_2=\dots =k_m=1$ . So the length of the period must be $2$ where $p$ is a prime with $p+1=2^n$ as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2534 posts

#13 h Apr 27, 2025, 4:54 PM

Y by

Begin by noticing that we only need $a_{i+2} = a_i$ for any $i$ . Take an arbitrary term $a_k = px$ where $a_k$ is odd and $p$ is the smallest prime factor of $a_k$ . Note that $a_{k+2} = \tfrac{p(x+p)}{2} > a_k$ unless $x=1$ or $x=p$ . Hence, the sequence is decreasing until one of the terms is $p^2$ or $p$ .

If $a_k = p^2$ , then $a_{k+2}=a_k=p^2$ . If $a_k=p$ , then $a_{k+1} = p(p+1)$ ; we have $a_{k+2} < a_k$ unless $p+1$ is a power of $2$ , at which point the sequence satisfies $a_{k+2} = a_k$ . Thus, the primes decrease until $p=3$ , at which point $p+1$ is a power of $2$ , implying periodicity. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a