Strange Conditional Sequence

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

Strange Conditional Sequence

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: APMO 2019 P2

The post below has been deleted. Click to close.

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

1595 posts

#1 h Jun 11, 2019, 12:18 AM • 2 Y

Y by Adventure10, Mango247

Let $m$ be a fixed positive integer. The infinite sequence $\{a_n\}_{n\geq 1}$ is defined in the following way: $a_1$ is a positive integer, and for every integer $n\geq 1$ we have
$a_{n+1} = \begin{cases}a_n^2+2^m & \text{if } a_n< 2^m \\ a_n/2 &\text{if } a_n\geq 2^m\end{cases}$ For each $m$ , determine all possible values of $a_1$ such that every term in the sequence is an integer.

This post has been edited 1 time. Last edited by MarkBcc168, Jun 12, 2019, 2:42 PM

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#2 h Jun 11, 2019, 12:29 AM • 2 Y

Y by Bunrong123, Adventure10

Solution

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#3 h Jun 11, 2019, 12:34 AM • 10 Y

Y by AbodeMokayed, ks_789, karitoshi, ArMath, ILOVEMYFAMILY, Muaaz.SY, MatBoy-123, SADAT, Adventure10, Mango247

$\textcolor{blue}{\textbf{-}}$ The only solution is $m=2$ and $a_1=2^r$ for some positive integer $r$ .
$\textcolor{red}{\textbf{\underline{Claim.1:}}}$ There is no $i\ge 1$ such that $a_i$ is odd.
$\textcolor{blue}{\textbf{The proof:}}$
Assume that there exist $i\ge 1$ such that $a_i=s$ is odd.
If $s\ge 2^m$ then $a_{i+1}=\frac{s}{2}$ and this is not integer.
If $s<2^m$ then $a_{i+1}=s^2+2^m \Longrightarrow a_{i+2}=\frac{s^2+2^m}{2}$ and this is not integer.
Contradiction, so There is no $i\ge 1$ such that $a_i$ is odd.

$\textcolor{red}{\textbf{\underline{Claim.2:}}}$ All the odd parts of the terms of the sequence $(a_n) _{n \ge 1}$ are less than $2^{m-1}$ .
$\textcolor{blue}{\textbf{The proof:}}$
Assume that there exist $a_i=2^r s$ such that $gcd(s,2)=1$ and $s \ge 2^{m-1}$ then.
$a_{i+1}=2^{r-1} s, \cdots, a_{i+r-1}=2s$ but $2s\ge 2^m$ so $a_{i+r}=s$ and this is a contradiction with claim.1 so always $s<2^{m-1}$ .

Now let's discuss the following cases:
$\textcolor{red}{\textbf{-}}$ When $m=1$ , let $a_1=2^r s$ , we know by using claim.2 that $s<1$ and this is a contradiction. So there is no possible values of $a_1$ .
$\textcolor{red}{\textbf{-}}$ When $m=2$ , let $a_1=2^r s$ , we know by using claim.2 that $s<2$ so $s=1$ .
$a_1=2^r \Longrightarrow a_2=2^{r-1}, \cdots, a_r=2 \Longrightarrow a_{r+1}=8 \Longrightarrow a_{r+2}=4 \Longrightarrow a_{r+3}=2$ .
So $a_{r+3k}=2,a_{r+3k+1}=8,a_{r+3k+2}=4$ for every integer $k \ge 0$ , so all the terms of the sequence $(a_n)_{n \ge 1}$ are integers when $m=2$ and $a_1=2^r$ for some positive integer $r$ .
$\textcolor{red}{\textbf{-}}$ When $m \ge 3$ , let $a_i=2^r s$ , assume that $a_i<2^m$ otherwise we can divide by $2$ so many times to achieve to a term that is less than $2^m$ . So $a_{i+1}=2^{2r}s^2+2^m$ :

1- If $2r>m$ then $a_{i+1}=2^m(2^{2r-m}s^2+1)$ and if $m>2r$ then $a_{i+1}=2^{2r}(s^2+2^{m-2r})$ ,but $2^{2r-m}s^2+1>s$ and $s^2+2^{m-2r}>s$ . So the odd part is increasing.
2- If $m=2r$ then $a_{i+1}=2^m(s^2+1)$ , here we know that $4 \nmid s^2+1$ so $\frac{s^2+1}{2}$ is the odd part of $a_{i+1}$ , but we know by using $AM-GM$ inequality that $\frac{s^2+1}{2} \ge s$ and the equality holds if and only if $s=1$ , but if $s=1$ then $a_{i+1}=2^{m+1} \Rightarrow a_{i+3}=2^{m-1} \Rightarrow a_{i+4}=2^m(2^{m-2}+1)$ , but $2^{m-2}+1>s=1$ and if $s \neq 1$ then $\frac{s^2+1}{2} > s$ , so the odd part is increasing as well. So this is a contradiction with claim.2 because the odd part is increasing but it is always less than $2^{m-1}$ . So there is no possible values of $a_1$ .
$\blacksquare$

This post has been edited 1 time. Last edited by Anaskudsi, Jun 11, 2019, 5:21 PM

Z K Y

The post below has been deleted. Click to close.

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

466 posts

#4 h Jun 12, 2019, 6:12 AM • 3 Y

Y by alex_g, Adventure10, Mango247

Should the problem statement read "if $a_n < 2^m$ " and "if $a_n \ge 2^m$ "?

Z K Y

The post below has been deleted. Click to close.

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

1595 posts

#5 h Jun 12, 2019, 2:43 PM • 2 Y

Y by Adventure10, Mango247

rocketscience wrote:

Should the problem statement read "if $a_n < 2^m$ " and "if $a_n \ge 2^m$ "?

Fixed, thanks.

Z K Y

The post below has been deleted. Click to close.

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

157 posts

#6 h Jun 19, 2019, 1:29 AM • 7 Y

Y by e_plus_pi, TLP.39, Aryan-23, Justpassingby, sabkx, Adventure10, Deadline

This problem was proposed by me. The solutions I sent are exactly the same as those in the replies, but in different words, so I won't put them here.

Z K Y

The post below has been deleted. Click to close.

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

214 posts

#7 h Jan 16, 2020, 4:55 AM • 2 Y

Y by Adventure10, Mango247

claim(1): if $a_i < 2^m$ then $a_i=2^{\frac{m}{2}}$
define $b_n=\frac{a_n}{v_2(a_n)}$
suppose WLOG $a_1<2^m$
suppose there is no $a_i = 2^{\frac{m}{2}}$
claim(1.1): $b_n$ is never decrease
the second operation doesn't change $b_n$
for the fisrt let $a_n=2^{k_n}b_n$ then:
$a_{n+1}=2^{2k_n}(b_n)^2+2^m=2^a(2^c (b_n)^2 +1)=2^a(b_{n+1})$
but $2^c (b_n)^2 +1 \ge (b_n)^2 +1 > b_n$
so b_n wil grow until we will have for large enough $i$ $b_i >2^m$
which is contradiction

so there exist $a_i=2^{\frac{m}{2}}$
$a_{i+1}=2^{m+1}$
$a_{i+2}=2^{m}$
$a_{i+3}=2^{m-1}=2^{\frac{m}{2}} \implies m=2$ and $a$ is a power of $2$
and we win

Z K Y

The post below has been deleted. Click to close.

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

300 posts

hansu

#8 h Apr 2, 2020, 7:54 PM

Y by

We will check the case $m=1,2$ manually. We get that there is no solution for $m=1$ and for $m=2$ , $a_1=2^t(t>0)$ works. Now we will prove that there is no such value of $a_1$ for $m>2$ .

For $n=2^a b$ with $b$ odd, we will $b$ the odd part of $n$ . The key observation is that the odd part of the elements of the sequence is increasing.
Proof: Suppose $a_i=2^ab$ where $b$ is odd. Then let $a_{i+1}=2^{2a}b^2+2^m$ (the other case being obvious). It's easy to observe that unless $2a=m$ , the odd part of $a_{i+1}$ obviously increases. If $2a=m$ we have $a_{i+1}=2^m{b^2+1}$ . But observe that $v_2(b^2+1)=1$ . Hence the odd part of $a_{i+1}=\frac{b^2+1}{2}\ge b$ with equality happening iff $b=1$ . Thus we we will look into the case $a_i=2^\frac{m}{2}$ . Thus we have $a_{i+1}=2^{m+1}, a_{i+3}=2^{m-1}, a_{i+4}=2^m(2^{m-2}+1),a_{i+5}=2^{m-1}+2, a_{i+6}=4[(2^{m-2}+1)^2+2^{m-2}]$ . Thus the odd part of $a_{i+6}$ is greater than $2^m$ . Thus there is no solution for $m>2$ .

Z K Y

The post below has been deleted. Click to close.

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

square_root_of_3

78 posts

square_root_of_3

#9 h Apr 21, 2020, 12:00 PM

Y by

Here's a sort of ugly (because of technicalities) solution, but I think the idea behind it is nice and motivated. Basically, the idea is that we'll always come back to a term in the interval $[2^{m-1}, 2^m)$ , which can be written as $2^{m-1}+r$ . Now we just want to prove that $\nu_2(r)<0$ at some point.

Let $m>4$ be an integer and let $2^{m-1}+r$ with $0\leqslant r <2^{m-1}$ be a term in the sequence, and suppose all terms in the sequence are integers. Then, the sequence goes as follows:
$2^{m-1}+r \mapsto 2^m+2^{2m-2}+2^mr+r^2 \mapsto \ldots \mapsto 2^{m-1}+2+2r+r^2/2^{m-1}.$ Now, if $2+2r+r^2/2^{m-1}<2^{m-1}$ , this is our 'new' $r$ . If this is not the case, then $2^{m-1}+2+2r+r^2/2^{m-1} \mapsto 2^{m-1}-2^{m-2}+1+r+r^2/2^m$ , and our 'new' $r$ is $1+r+r^2/2^m-2^{m-2}$ . We prove that in both cases, the $\nu_2$ decreased.

Case $1$ : We will prove $\nu_2(r)>\nu_2(2+2r+r^2/2^{m-1})$ . If $r=0$ , the claim is obvious. If $\nu_2(r^2)<m-1$ , then the right hand side isn't an integer which is a contradiction.

Since $r<2^{m-1}$ , we have $\nu_2(r)<m-1$ . This implies $\nu_2(2r)>\nu_2(r^2/2^{m-1}$ , and if $\nu_2(2)\neq \nu_2(r^2/2^{m-1})$ , we have that $\nu_2$ of the right hand side is less than or equal to $\nu_2(2)$ , which is impossible.

If $\nu_2(r^2/2^{m-1})=\nu_2(2)$ , then $\nu_2(r)=m/2$ . In this case, $r=2^{m/2}k$ for some odd $k$ . Then $2+2r+r^2/2^{m-1}=2+2^{m/2+1}k+2k^2$ .

Since $2+2k^2 \equiv_8 4$ , and $\nu_2(2^{m/2+1}k)>2$ , we get that $\nu_2$ of the right hand side equals $2$ , which is less than $m/2$ . In any case, $\nu_2$ decreases and eventually it must reach something smaller than zero, which is a contradiction.

Case $2$ : We will prove $\nu_2(r)>\nu_2(1+r+r^2/2^{m}-2^{m-2})$ . Again, as in previous case, $m/2\leqslant \nu_2(r) \leqslant m-2$ .

If $\nu_2(r)=m-2$ , then $r=2^{m-2}$ since $r<2^{m-1}$ . In this case, the left hand side equals $m-2$ , and the right hand side equals $\nu_2(1+2^{m-4})$ , which equals $0$ since $m>4$ .

Suppose $\nu_2(r)<m-2$ and $\nu_2(r)>m/2$ . Then $\nu_2(2^{m-2})>\nu_2(r)>\nu_2(r^{2}/2^m)>\nu_2(1)=0$ , and then $\nu_2$ of the whole expression equals $0$ , which is smaller than $m/2$ .

The only case left is $r=2^{m/2}k$ for some odd $k$ . Then the right hand side equals $\nu_2(1+2^{m/2}k+k^2-2^{m-2})$ , which equals $1$ since $1+k^2\equiv_4 2$ , and $\nu_2(2^{m/2}k-2^{m-2})>1$ . This proves our claim.

Therefore, there are no solutions for $m>4$ .

For small $m$ , it's enough to check for cycles which start at a number from $[2^{m-1}, 2^m)$ .

For $m=1$ , we have $1\mapsto 3 \mapsto 3/2$ , so there are no solutions.

For $m=2$ , we have $2\mapsto 8 \mapsto 4 \mapsto 2$ , so any number which eventually ends up at $2$ is a solution. These numbers are exactly all powers of $2$ except for $2^0$ .

For $m=3$ , we have $4 \mapsto 24 \mapsto 12 \mapsto 6 \mapsto 44 \mapsto 22 \mapsto 11 \mapsto 5.5$ , $5 \mapsto 33 \mapsto 16.5$ , $7 \mapsto 57 \mapsto 28.5$ , so there are no solutions.

For $m=4$ , all odd numbers $x$ eventually map into $x^2/2+8$ , $8 \mapsto 80 \mapsto \ldots \mapsto 10 \mapsto 116 \mapsto 58 \mapsto 29 \mapsto 14.5$ , $12 \mapsto 160 \mapsto \ldots \mapsto 10$ , $14 \mapsto 210 \mapsto \ldots \mapsto 52.5$ , so there are no solutions.

This post has been edited 1 time. Last edited by square_root_of_3, Apr 21, 2020, 12:01 PM

Z K Y

The post below has been deleted. Click to close.

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

1 post

#10 h Apr 21, 2020, 5:21 PM

Y by

thanks for your replies... still learning and i found a solution to my question. appreciating your help a lot. healthy recipes

This post has been edited 1 time. Last edited by Joand999, May 6, 2020, 4:37 PM
Reason: grammar

Z K Y

The post below has been deleted. Click to close.

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

626 posts

#11 h May 21, 2020, 3:14 PM

Y by

Define the function $f(n) = \nu_2(n)-\log_2(n)$ ; note that if $\frac{n}{2^{\nu_2(n)}}=k$ , then $f(n) = -\log_2(k)$ . I claim that $f(a_n)$ is non-increasing. If $a_n \geq 2^m$ , then $f(a_{n+1}) = (\nu_2(a_n)-1)-(\log_2(a_n)-1) = f(a_n)$ , as claimed. Thus we now show that whenever $a_n<2^m$ we have $f(a_n^2+2^m) \leq f(a_n)$ .

Case 1: $2\nu_2(a_n)<m$ . Then $\nu_2(a_{n+1})=2\nu_2(a_n)$ and we have $f(a_{n+1})=2\nu_2(a_n)-\log_2(a_n^2+2^m) < 2\nu_2(a_n)-2\log_2(a_n) \leq \nu_2(a_n)-\log_2(a_n)$ .

Case 2: $2\nu_2(a_n)>m$ . Then $\nu_2(a_{n+1})=m$ and we have $f(a_{n+1})=m-\log_2(a_n^2+2^m)<2\nu_2(a_n)-2\log_2(a_n) \leq \nu_2(a_n)-\log_2(a_n)$ .

Case 3: $2\nu_2(a_n)=m$ . Let $\frac{a_n}{\nu_2(a_n)}=b_n$ ; then we have $a_{n+1}=(2^{m/2}b_n)^2+2^m = 2^{m+1} \left( \frac{b_n^2+1}{2} \right)$ (note that $\frac{b_n^2+1}{2}$ is an odd integer because $b_n$ is odd). Thus $f(a_{n+1})=-\log_2(\frac{b_n^2+1}{2}) \leq -\log_2(b_n)=f(a_n)$ .

Now observe that since $f(a_n)$ can only attain a finite number of values (assuming $a_n$ is always an integer), Cases 1 and 2 can only happen a finite number of times (because they are strict inequalities). Also note that equality occurs in Case 3 iff $b_n=1$ , i.e. $a_n=2^{m/2}$ . Then $a_{n+1}=2^{m+1}, a_{n+2}=2^m, a_{n+3}=2^{m-1}$ . Because Cases 1 and 2 can't happen infinitely often, we must have that $2^{m-1}=2^{m/2} \Rightarrow m=2$ . It can easily be checked that when $m=2$ , the sequence is always an integer iff $a_1=2^k$ for some positive integer $k$ . In conclusion, the answer is any even power of $2$ when $m=2$ , and no solutions for other $m$ .

This post has been edited 1 time. Last edited by VulcanForge, May 21, 2020, 3:16 PM

Z K Y

The post below has been deleted. Click to close.

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

2726 posts

#12 h Oct 22, 2020, 5:50 PM

Y by

This problem is such a typical APMO #2.

Note that at any point, we do not want $a_i$ to become odd else it will continue to be odd until it becomes $\geq 2^m$ and is then not divisible by $2$ . For $m = 1$ , for this reason, we see that $a_1$ must not be odd. Furthermore, if $a_1$ is even, it will be stripped of all its $2$ 's and it will become odd, which is bad. Hence, $m = 1$ has no solutions for $a_1$

For $m = 2$ , we also see that $a_1$ must not be odd. Let $a_1 = 2^s \cdot t$ for some odd $t$ and maximal $s \geq 1$ . If $t > 4$ , then we are already doomed because then we will divide out $2$ 's until some term $a_i = t$ which will be forced to be divided by $2$ , which is bad. If $t = 3$ , then $a_1 \geq 4$ so the first move will bbe to divide out all $2$ 's until some $a_i = t = 3$ . Then, we have an odd term, which is bad. If $t = 1$ , then note that if $s \geq 2$ we keep dividing until a term becomes $a_i = 2$ and then the next term is $a_{i+1} = 3$ and it continues to cycle $2 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 8 \ldots$ and similarly if $s = 1$ , this same cycle takes place. Hence, for $\boxed{m = 2}$ , all even powers of $2$ work.

Now, consider $m > 2$ . Again, $a_1$ may not be odd so let $a_1 = 2^s \cdot t$ for maximal $s \geq 1$ and odd $t$ . If $a_1 \geq 2^m$ , then enough $2$ 's will be stripped so that some term $a_i = 2^{s'} \cdot t$ will be $< 2^m$ . We start from there. See that $a_{i+1} = 2^{2s'} \cdot t^2 + 2^m.$ When $2s' < m$ , we see that $a_{i+1} = 2^{2s'} \cdot (t^2 + 2^{m - 2s'})$ so the odd part $t$ is eventually increasing. It eventually becomes larges enough to exceed $2^m$ at which point dividing by $2$ becomes impossible.

When $2s' > m$ , we see that $a_{i+1} = 2^m \cdot (2^{2's - m}t^2 + 1)$ so the odd part $t$ is still eventually increasing. Similarly, it becomes large enough to a point where it exceeds $2^m$ and dividing by $2$ is again impossible.

Lastly, we consider when $2^s = m$ . Note that $a_{i+1} = 2^m(t^2 + 1)$ . We see that $t^2 + 1 \equiv 2 \pmod 4$ hence the odd part of this $a_{i+1}$ is therefore $\tfrac{t^2 + 1}{2}$ . Note that this sequence of $t$ 's becomes increasing if $t^2 + 1 > 2t$ , or when $t > 1$ . So when $t > 1$ , we are doomed. When $t = 1$ , we once again arrive at the prospect of $a_1$ being a perfect $2$ th power. A quick check shows that this ends up not working, because eventually we will get a term that isnt a power of $2$ : $2^k \rightarrow 2^{k'} \rightarrow 2^{2k'} + 2^m \rightarrow 2^{m+1} \rightarrow 2^{m-1} \rightarrow \text{not power of 2}$ in the best case scenario, where a possible early break happens when $2k' \neq m$ . So $m > 2$ do not work.

So indeed, our only solutions are when $m = 2$ and $a_1 = 2^k$ with $k \geq 1$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

492 posts

#14 h Oct 29, 2020, 2:48 AM

Y by

For $m = 2$ the only solution that works is $a_1 = 2^n$ for $n > 0$ and $m=1$ has no solutions. This not too hard to check.

We will prove that all $m > 2$ don't have any solutions.

Let $a_i = 2^{\nu_2(a_i)}k$ where $k$ is an odd integer for some arbitrary $i.$
If $a_i \ge 2^m,$ there must exist some $\ell \le \nu_2(a_i)$ such that $2^{m-1} \le \frac{a_i}{2^{\ell}} < 2^m \implies 2^{\nu_2(a_i)-\ell}k \in [2^{m-1}, 2^m)$ for $a_i$ to be an integer until $a_i < 2^m$ Now, if $k \in [2^{s-1}, 2^{s}),$ for some $m \ge s \ge 1.$ It is sufficient (and necessary) to let $\nu_2(a_i)-\ell = m-s \implies \nu_2(a_i) > m-s$ (1)

It is obvious that $k = \frac{a_i}{2^{\nu_2(a_i)}}$ is always increasing if $m < 2\nu_2(a_i),$ since $a_{i+1} = (a_i^2+2^m) = 2^m(2^{2\nu_2(a_i)-m}k^2+1)$ has odd part $2^{2\nu_2(a_i)-m}k^2+1,$ which is is greater than $k.$

If $m > 2\nu_2(a_i),$ then $\nu_2(2^m(2^{2\nu_2(a_i)-m}k^2+1)) = 2\nu_2(a_i)$ so the odd part is $(2^{m-2\nu_2(a_i)}k^2+1)$ which is obviously greater than $k.$

If $2\nu_2(a_i) = m,$ then $\nu_2(k^2+1) = 1 \Longleftrightarrow k^2+1 \equiv 2 \pmod{2^2}$ so the odd part will be $\frac{k^2+1}{2},$ which is greater than $k.$

To finish, note that at some point $k$ will be greater than $2^m,$ which will cause a contradiction.

This post has been edited 1 time. Last edited by fukano_2, Oct 29, 2020, 2:48 AM

Z K Y

The post below has been deleted. Click to close.

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

308 posts

#15 h Feb 17, 2021, 11:10 AM

Y by

If $m=2$ then $a_1=2^n$ are obviously solutions, we now show that otherwise such numbers doesn't exist.

It is easy to show that $m=1,3,4$ yields no solution, now suppose $m\geq 5$
Notice that there exists sufficiently large $n$ such that $2^{m-1}<a_n<2^m$ . Therefore,
$2^m(2^{m-2})<a_n^2+2^m<2^m(2^m)$ Therefore, we have
$a_{n+m}=\frac{a_{n+1}}{2^{m-1}}$ In particular this implies $v_2(a_n^2+2^m)\geq m-1$ for all $2^{m-1}<a_n<2^m$ . Now if $v_2(a_n^2)\neq m$ , then $v_2(a_{n+1})=m$ and so
$a_{n+m}=1$ and hence $v_2(a_{n+m}^2+2^m)=m$ . Hence $v_2(a_n^2)=m$ and so $m$ is even, let $m=2k$ . Then $v_2(a_{n+1})\geq 3k-1$
However, if $v_2(x)=k$ then
$x^2\equiv 2^{m}\pmod 2^{m+1}$ and so $v_2(a_{n+1})=v_2(2^m+2^m)=m+1<3k-1$ , contradiction.

This post has been edited 3 times. Last edited by mathaddiction, Feb 17, 2021, 11:16 AM

Z K Y

The post below has been deleted. Click to close.

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

113 posts

#16 h Apr 7, 2021, 1:13 AM

Y by

The only solutions are $(m, a_1) = (2, 2^i)$ for some positive integer $i$ .

Let the odd part of a number be its largest odd divisor.

Let's consider only the subsequence $(b_n)$ of $(a_n)$ with terms less than $2^m$ . First we claim that the odd parts of the terms of $(b_n)$ are nondecreasing. Say $b_n=2^d \cdot o$ where $o$ is its odd part, then $b_{n+1}$ is $2^{2d} \cdot o^2 + 2^m$ divided by some power of $2$ (which doesn't affect its odd part so we can ignore it). There are $3$ cases,

If $2d > m$ , then $2^{2d} \cdot o^2 + 2^m = 2^m (2^{2d-m} o^2 + 1)$ . $2^{2d-m} o^2 + 1$ is odd, and $2^{2d-m} o^2 + 1 > o^2 + 1 > o$ .
If $2d = m$ , then $2^{2d} \cdot o^2 + 2^m = 2^m (o^2 + 1)$ . Now all odd squares are $1$ mod $4$ , so it follows that $o^2+1$ is $2$ mod $4$ . Hence the odd part of $b_{n+1}$ is $(o^2+1)/2$ . $(o^2+1)/2 \ge o$ rearranges to $(o-1)^2 \ge 0$ , which is true, with equality at $o=1$ .
If $2d < m$ , then $2^{2d} \cdot o^2 + 2^m = 2^{2d} (o^2 + 2^{m-2d})$ . $o^2 + 2^{m-2d}$ is odd, and $o^2 + 2^{m-2d} > o^2 + 1 > o$ .

The claim is proven, and furthermore we know that there is equality iff $o=1$ and $2d=m$ , i.e. $b_{n+1} = 2^{m/2}$ .

Clearly there are finitely many possible integer values for a term $b_n$ , and at some point we must repeat a term by pigeonhole. Then since $b_{n+1}$ is uniquely determined by $b_n$ , the sequence becomes periodic after this. It follows that the odd part is also eventually periodic, but it is non decreasing so it must be constant. Thus, $b_n$ is eventually always equal to $2^{m/2}$ .

Clearly $m$ must be even for this to be true. Furthermore,
$\left(2^{m/2} \right)^2 + 2^m = 2^{m+1},$ so if $b_n = 2^{m/2}$ , then $b_{n+1} = 2^{m-1}$ . Thus $\frac{m}2 = m-1$ , so $m=2$ .

To finish, notice that for $m=2$ , $a_1 = 2^i b_1$ for some nonnegative integer $i$ , and we can check that

If $b_1=1$ , $b_2 = \frac{1+4}4 = \frac54$ , which is bad.
If $b_1=2$ , $b_2 = \frac{4+4}4 = 2$ , which is good.
If $b_1=3$ , $b_2 = \frac{9+4}8 = \frac{13}8$ , which is bad.

Thus $m=2$ and $a_1 = 2 \cdot 2^i$ for some nonnegative integer $i$ , i.e. $2^i$ for some positive integer $i$ , as desired. $\blacksquare$

This post has been edited 1 time. Last edited by Vitriol, Apr 7, 2021, 1:13 AM
Reason: \blacksquare

Z K Y

The post below has been deleted. Click to close.

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

1184 posts

L567

#17 h Feb 10, 2022, 6:57 AM

Y by

The answer is it is possible only for $m = 2$ in which $a_1 = 2^k$ only, which can easily be seen to work because it goes to $2$ and then $2,8,4,2,8,4,2, \cdots$

The main idea is to look at the odd part of $a_n$ . I claim this is (mostly) always increasing. Suppose $a_n < 2^m$ and say $a_n = 2^l k$ . If $l \neq \frac{m}{2}$ , then $a_n^2 + 2^m = 2^{2l}k^2 + 2^m$ which has odd part at least $l^2$ so its increasing.

So assume $m = 2z$ and $a_n = 2^zk$ , then $a_n^2 + 2^m = 2^m(l^2 + 1)$ , but $l^2 + 1 \equiv 2 \pmod 4$ so the odd part is now $\frac{l^2 + 1}{2} \ge l$ with equality iff $l = 1$ . Therefore, since the odd part must eventually stabilize, we must have $a_i = 2^z$ at some point. But then see that it goes $2^z \rightarrow 2^{2z+1} \rightarrow 2^{2z} \rightarrow 2^{2z-1}$ and then goes up again, so the only way this can work is to have $z = 2z - 1 \implies z = 1$ , which corresponds to $m = 2$ , from which its easy to see that the only $a_1$ that work are the ones claimed above, so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

626 posts

#18 h Mar 6, 2022, 11:44 PM

Y by

Answer: only $m=2$ and $a_1 \in \{ 2, 4, 8\}$ . Call the case where $a_i<2^m$ a "type 1 operation" and the case where $a_i \ge 2^m$ a "type 2 operation".

Consider the odd parts of the sequence, i.e. $a_i/\nu_2(a_i)$ . Clearly this is preserved during a type 2 operation; the claim is that the odd part always increases during a type 1 operation, unless $a_i^2=2^m$ . Write $a_i=2^kn<2^m$ for odd $n$ .

If $2k>m$ then the odd part of $2^{2k}n^2+2^m$ is $2^{2k-m}n^2+1$ , which is clearly greater than $n$ .
If $2k<m$ then the odd part of $2^{2k}n^2+2^m$ is $n^2+2^{m-2k}$ , which is clearly greater than $n$ .
If $2k=m$ then the odd part of $2^{2k}n^2+2^m$ is equal to the odd part of $n^2+1$ , which is $\tfrac{n^2+1}{2}$ due to the fact that $n^2 \equiv 1 \pmod{4}$ . This is greater than $n$ unless $n=1$ , i.e. $a_i^2=2^m$ .

The $m=1,2$ cases are easily resolved by hand. Observe that if $m \ge 3$ , the smallest possible result of an operation is $2^{m-1} > \sqrt{2^m}$ , hence we can only get $\sqrt{2^m}$ at most once (if it's the starting value). So infinitely many of the type 1 operations increase the odd part, while type 2 operations preserve the odd part; this clearly causes the problem to shut down.

Z K Y

The post below has been deleted. Click to close.

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

11361 posts

#19 h Mar 30, 2022, 3:36 PM

Y by

Suppose $m\ge5$ .
First we claim that some $k$ satisfies $2^{m-1}\le a_k<2^m$ .
If $a_1\ge2^m$ then we apply the recursion $a_{n+1}=\frac{a_n}2$ until we obtain such a $k$ .
If $a_1<2^m$ we repeat this argument starting from $a_2\ge2^m$ .

Then:
$a_{k+1}=a_k^2+2^m\ge2^{2m-2}+2^m\ge2^{2m-2}$ and similarly $a_{k+1}<2^{2m-1}$ . Now every subsequent term must be half of the previous one, until $a_{m+k}$ . We can calculate:
$a_{m+k}=\frac{a_{k+1}}{2^{m-1}}\Rightarrow v_2(a_{k+1})=v_2(a_{m+k})+m-1\ge m-1.$ If $2v_2(a_k)\ne m$ , then:
$v_2(a_{k+1})=\min\{v_2(a_k^2),v_2(2^m)\}=\min\{2v_2(a_k),m\}\le m$ which contradicts the previous inequality. So $v_2(a_k)=\frac m2$ for all such $k$ . Now $m$ is even, so $m\ge6$ . Then $v_2(a_{m+k})=\frac m2$ so $v_2(a_{k+1})=\frac{3m}2-1$ . Let $a_k=2^{m/2}\cdot s$ where $s$ is odd. Then:
$\frac{3m}2-1=v_2(a_{k+1})=v_2(a_k^2+2^m)=v_2(2^m(1+s^2))=m+v_2(1+s^2)$ so $v_2(1+s^2)=\frac m2-1$ . But since $m\ge6$ , $v_2(1+s^2)\ge2$ , or $s^2+1\equiv0\pmod4$ . This is impossble for odd $s$ .

Now we deal with the cases $m\le4$ .
Suppose some $a_i$ is odd. We must have $a_i<2^m$ , otherwise $a_{i+1}=\frac{a_i}2$ is not an integer. But then $a_{i+1}=a_i^2+2^m>2^m$ is also odd, so $a_{i+2}$ is not an integer.
So all members of the sequence must be even.

$m=1$ : If $a_n<2$ then that term is odd, which is impossible. But then $a_{n+1}=\frac{a_n}2$ for each $n$ , which eventually is nonintegral.
$m=2$ : The recursion becomes
$a_{n+1} = \begin{cases}8 & \text{if } a_n=2 \\\frac{a_n}2 &\text{if } a_n\ge4\end{cases}$ Let $a_j=2$ for the minimal $j$ . Before that point, $a_{n+1}=\frac{a_n}2$ for each $n$ , so $a_1$ is a power of $2$ . Then $\boxed{(a_1,m)=(2^i,2)}$ for $i\ge1$ are indeed solutions, since all terms before $a_j$ are integers and we end in the loop $a_j=2\mapsto8\mapsto4\mapsto2$ .
$m=3$ : The recursion becomes
$a_{n+1} = \begin{cases} a_n^2+8& \text{if } a_n=2,4,6 \\\frac{a_n}2 &\text{if } a_n\ge8\end{cases}$ No member of the sequence can be $2$ , $4$ , or $6$ since:
$2\mapsto12\mapsto6\mapsto44\mapsto11$ $4\mapsto24\mapsto12\mapsto6\mapsto44\mapsto11$ $6\mapsto44\mapsto11$ which are all impossible. So $a_{n+1}=\frac{a_n}2$ for all $n$ which eliminates this case too.
$m=4$ : The recursion becomes
$a_{n+1} = \begin{cases} a_n^2+16& \text{if } a_n=2,4,6,8,10,12,14 \\\frac{a_n}2 &\text{if } a_n\ge16\end{cases}$ Similarly, we write:
$2\mapsto20\mapsto10\mapsto116\mapsto58\mapsto29$ $4\mapsto32\mapsto16\mapsto8\mapsto80\mapsto40\mapsto20\mapsto10\mapsto116\mapsto58\mapsto29$ $6\mapsto52\mapsto26\mapsto13$ $8\mapsto80\mapsto40\mapsto20\mapsto10\mapsto116\mapsto58\mapsto29$ $10\mapsto116\mapsto58\mapsto29$ $12\mapsto160\mapsto80\mapsto40\mapsto20\mapsto10\mapsto116\mapsto58\mapsto29$ $14\mapsto212\mapsto106\mapsto53$ which are all impossible. So $a_{n+1}=\frac{a_n}2$ for all $n$ which eliminates this case too.

Z K Y

The post below has been deleted. Click to close.

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

194 posts

Iora

#20 h Dec 10, 2022, 3:05 PM

Y by

Nice problem
Claim 1. All $a_i$ is even.

FTSOC, assume otherwise and let $a_i$ be odd integer for some $i$ . Then either $\frac{a_i}{2}$ or $\frac{a_i^2+2^m}{2}$ is not an integer, hence contradiction. $\square$

Therefore, let $a_i= 2^a \cdot c$ where $c$ is an odd integer and $a_i>2^m$ .

Claim 2. $2^{m-1} > c_i$ .
Let $e$ be an integer such that $2^{e+1}>c>2^e$ . Let $r$ be smallest integer such that $2^{a-r}<2^m$ . Then we have

$a_i= 2^a \cdot c <2^{a+e+1}$ . Let $a_{i+j}$ be the first time our variables goes to $<2^m$ . Then $a_{i+j} = 2^{a-r-e-1} \cdot c$ . But since $a_{i+j}$ is even, we have
$a-r-e-1 \ge 1 \Rightarrow a-r-2 \ge e \Rightarrow m-2 \ge e$ Then $2^{m-1} \ge c_i$ . $\square$ .

If $m=1$ , there are no such $c_i$ , hence impossible.
If $m=2$ , then $c_i=1$ . Then any $a_1=2^x, x \ge 1$ works.
If $m\ge 3$ ,we will divide into cases.
Case 1. $2a \neq m$ .
Then after some time, we will have $a_{i+j}= 2^m( 2^{2r-m} c^2-1)$ or $2^{2a}(c^2+2^{m-2a})$ then $c_{i+j}>c_i$ , but it clearly increases, but $c$ is bounded above, hence contradiction.

Case 2. $2a=m$ .

Then we have $a_{i+j}=2^m(c_i^2+1)$ . Since $c_i^2+1$ is divisible by $2$ but not $4$ , we know that $c_{i+j}= \frac{c_i^2+1}{2}$ . But then it is clearly increasing for $c_i>1$ . If $c_i=1$ , after some time we will have $a_j=2^m(2^{m-2}+1)$ . since $2^{m-2}+1>1$ , odd part will increase, hence contradiction.
Therefore the only solutions are $m=2$ , $a_1 =2^x, x \ge 1$ which clearly works.

Z K Y

The post below has been deleted. Click to close.

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

15 posts

#21 h Jul 2, 2023, 6:40 PM

Y by

hi . its really nice , i get a realy easy solution for that problem but im not sure if its true

Z K Y

The post below has been deleted. Click to close.

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

11 posts

#22 h Nov 26, 2024, 3:26 AM

Y by

The answer is $a_1=2^k$ with $k \geq 1$ and $m = 2$ . It is easy to check that these work and all of them lead to an eventually periodic sequence.

Assume $a_n = 2^kb$ with $b$ odd. We can also assume $a_n <2^m$ because it will become that after a few terms anyway.

We consider 3 cases: $2k<m, 2k=m, 2k>m$ .

Case 1: $2k<m$
$a_{n+1}=2^{2k}b^2+2^m = 2^{2k}(b^2+2^{m-2k})$ , so the odd part of $a_{n+1}$ is greater than the odd part of $a_n$ .
Case 2: $2k=m$
$a_{n+1}=2^{2k}(b^2+1)$ and $b^2+1$ is $2 \pmod 4$ because $b^2+1 \equiv (2x-1)^2+1 \equiv 4x^2-4x+2 \equiv 2 \pmod 4$ . Thus the odd part of $a_{n+1}$ is $\frac{b^2+1}{2} \geq b$ by AM-GM with equality iff $b=1$ . If $b=1$ , note that $a_k\neq a_n$ where $n \neq k$ unless $m=2$ because there is always an integer between $k$ and $m$ . So we will be "moved" to Case 3 for $a_{n+1}$ .
Case 3: $2k>m$
$a_{n+1} = 2^m(1+2^{2k-m}b^2)$ , so the odd part of $a_{n+1}$ is clearly greater than the odd part of $a_n$ . $(1+2^{2k-m}b^2>b)$ .

Finally, we know that no matter what, the odd part of sequence $a$ is strictly increasing, and it will eventually reach a value greater than $2^{m-1}$ . Then the sequence starts generating non-integers soon after. $\blacksquare$

This post has been edited 2 times. Last edited by cushie27, Nov 26, 2024, 3:39 AM

Z K Y

The post below has been deleted. Click to close.

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

243 posts

pie854

#24 h Mar 4, 2025, 1:20 PM

Y by

For $m=2$ , it's easy to check that $a_1$ works iff it is a power of two. And for $m=1,3,4,5$ we can check no such $a_1$ exists (we just need to check that $a_1<2^m$ ( $m=1,3,4,5$ ) doesn't work).

We claim that there exists no such sequence for $m>5$ . Assume to the contrary that (wlog) $a_1<2^m$ works. Since $\frac{2^{m-1}(a_1^2+2^m)}{2^{\lfloor \log_2(a_1^2+2^m)\rfloor}} < 2^m \leq \frac{2^{m}(a_1^2+2^m)}{2^{\lfloor \log_2(a_1^2+2^m)\rfloor}},$ there must exist a positive integer $i$ such that $a_i=\frac{2^{m-1}(a_1^2+2^m)}{2^{\lfloor \log_2(a_1^2+2^m) \rfloor }} .$

If $a_1\leq 2^{m-1}$ then $a_1\leq 2^{m-1} \leq \frac{2^{m-1}(a_1^2+2^m)}{2^{\lfloor \log_2(a_1^2+2^m)\rfloor}}=a_i$ with equality iff $a_1=2^{m-1}$ and $a_1^2+2^m=2^t$ for some $t$ . It's easy to check that this implies $m=2$ , contradiction. Thus $a_1<a_i$ . Repeating the same process, we get to some $a_j$ with $2^m>a_j>2^{m-1}$ . So it suffices to show that $a_1\in (2^{m-1},2^m)$ doesn't work.

Suppose $2^{m-1}<a_1<2^m$ . Then, $\log_2(a_1^2+2^m)>\log_2(2^{2(m-1)})=2(m-1)$ and so $\lfloor \log_2(a_1^2+2^m) \rfloor \geq 2m-2.$ Also $v_2(a_1^2+2^m)\leq m$ ; unless $a_1=2^{m/2}k$ ( $k$ odd) in which case we have $v_2(a_1^2+2^m)=m+v_2(k^2+1)=m+1.$ Thus $v_2(a_1^2+2^m)\leq m+1$ . Now $v_2(a_i)=m-1+v_2(a_1^2+2^m)-\lfloor \log_2(a_1^2+2^m) \rfloor \leq m-1+(m+1)-(2m-2)=2.$ Now note that there exists $j>i$ such that $a_j=\frac{2^{m-1}(a_i^2+2^m)}{2^{\lfloor \log_2(a_i^2+2^m) \rfloor }} .$ Then, $v_2(a_j)=m-1+v_2(a_i^2+2^m)-\lfloor \log_2(a_i^2+2^m) \rfloor \leq m-1+(2\cdot 2)-(2m-2)=5-m<0,$ contradiction.

This post has been edited 5 times. Last edited by pie854, Mar 4, 2025, 1:29 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a