Power 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

Power sequence

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ELMO Shortlist 2023 N2

The post below has been deleted. Click to close.

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

1753 posts

#1 h Jun 29, 2023, 1:41 AM • 5 Y

Y by ImSh95, p_ben, PikaPika999, ehuseyinyigit, cubres

Determine the greatest positive integer $n$ for which there exists a sequence of distinct positive integers $s_1$ , $s_2$ , $\ldots$ , $s_n$ satisfying $s_1^{s_2}=s_2^{s_3}=\cdots=s_{n-1}^{s_n}.$
Proposed by Holden Mui

Z K Y

The post below has been deleted. Click to close.

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

158 posts

#2 h Jun 29, 2023, 12:13 PM • 3 Y

Y by ImSh95, PikaPika999, cubres

Very nice, any ideas, i think maximum value of $n$ would be $3$

Z K Y

The post below has been deleted. Click to close.

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

138 posts

sman96

#5 h Jun 29, 2023, 1:34 PM • 4 Y

Y by ImSh95, PikaPika999, ehuseyinyigit, cubres

shinhue wrote:

Very nice, any ideas, i think maximum value of $n$ would be $3$

$s_1 = 6^6, s_2 = 6, s_3 = 36, s_4 = 18$ works

Z K Y

The post below has been deleted. Click to close.

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

predictableprimes

6 posts

predictableprimes

#6 h Jun 29, 2023, 6:36 PM • 3 Y

Y by ImSh95, Sedro, cubres

Nice problem. The answer is $n=5$ .
Claim: if $n>4$ then $s_{n-3}=2,s_{n-2}=16,s_{n-1}=4$ .
Proof: suppose $s_1^{s_2}=s_2^{s_3}= ... =s_{n-1}^{s_n}$ and $n>4$ then $p|s_i$ $\implies$ $p|s_j$ for $i,j\in$ { $1,2,..n-1$ }
also for any prime $p$ dividing $a_i$ we have $s_2V_p(s_1)=s_3V_p(s_2)= ..= s_{n-2}V_p(s_{n-1})=s_{n-1}V_p(s_n)$ $\implies$ $\frac{V_p(s_i)}{V_q(s_i)}$ is constant for all $i\in$ { $1,2,..n-1$ } and any prime divisors $p$ and $q$ of $s_1$ .
Since $\frac{V_p(s_i)}{V_q(s_i)}$ is constant , each $s_i$ must be a perfect power of some integer.
(This is true since exponent of primes of $s_i$ are in a fixed ratio)
Now let $s_i=a^{b_i}$ for all $i\in$ { $1,2,..n-1$ }.
$\implies$ $b_1a^{b_2}= .. =b_{n-4}a^{b_{n-3}}=b_{n-3}a^{b_{n-2}}=b_{n-2}a^{b_{n-1}}=b_{n-1}s_n$
For simplicity let $c_1=b_{n-4} , c_2=b_{n-3} , c_3=b_{n-2} , c_4=b_{n-1}$
We will prove that $c_{1}a^{c_2}=c_{2}a^{c_{3}}=c_{3}a^{c_{4}}=c_{4}s_n$ is not possible.
Case 1: $c_2>c_1$
$c_{1}a^{c_2}=c_{2}a^{c_{3}}$ $\implies$ $a^{c_2}>a^{c_3}$ $\implies$ $c_2>c_3$ also $c_{2}a^{c_{3}}=c_{3}a^{c_{4}}$ $\implies$ $c_3>c_4$ $\implies$ $\frac{c_2}{c_3}$ $=a^{c_4-c_3}$ $\implies$ $c_3|c_2$
also $\frac{c_2}{c_1}$ $=a^{c_2-c_3}$ since $c_3|c_2$ we have $c_3<$ $\frac{c_2}{2}$ $\implies$ $\frac{c_2}{c_1}$ $>$ $a^{c_2/2}$ which is only possible if $(a,c_2,c_1)=(2,2,1),(2,3,1),(2,4,1)$ .
Now for $(a,c_2,c_1)=(2,2,1),(2,3,1)$ , $(c_1,c_2,c_3,c_4)=(1,2,1,2),(1,3,log_2(8/3),idk)$ ,Both of which are contradiction.
But $(a,c_2,c_1)=(2,4,1)$ gives the desired result.
Case 2: $c_2<c_1$
$c_{1}a^{c_2}=c_{2}a^{c_{3}}$ $\implies$ $a^{c_2}<a^{c_3}$ $\implies$ $c_2<c_3$ also $c_{2}a^{c_{3}}=c_{3}a^{c_{4}}$ $\implies$ $c_3>c_4$
Now we prove that $c_4|c_3$ , if not then there exist a prime $P$ such that $V_P(c_4)>V_P(c_3)$ but $c_4s_n=c_3a^{c_4}$ $\implies$ $P$ divides a.
Let $V_P(a)=m , V_P(c_4)=l$ .Note that $c_3=c_2a^{c_3-c_4}$ $\implies$ $V_P(c_3)>(c_3-c_4)m$
and since $l>V_P(c_3)$ ,we have $V_P(c_3)|c_3,c_4$ $\implies$ $V_P(c_3)>P^{V_P(c_3)}$ $\frac{c_4-c_3}{P^{V_P(c_3)}}m$ $\implies$ $V_P(c_3)>P^{V_P(c_3)}$ which is a contradiction.
Hence $c_4|c_3$ now from $\frac{c_3}{c_2}$ $=a^{c_3-c_4}$ we will get $\frac{c_3}{c_2}$ $>$ $a^{c_3/2}$ which implies $(a,c_3,c_2)=(2,2,1),(2,3,1),(2,4,1)$
which would give contradiction as $(c_1,c_2,c_3,c_4)=(2,1,2,1),(4,1,3,log_2(8/3)),(2,1,4,4)$ for $(a,c_3,c_2)=(2,2,1),(2,3,1),(2,4,1)$ respectively ,all of which are contradiction.
Hence
$s_{n-3}=2,s_{n-2}=16,s_{n-1}=4$ $\implies$ $s_1^{s_2}=s_2^{s_3}= ... =s_{n-1}^{s_n}=2^{16}$
$\implies$ $s_n=8,s_{n-4}=2^8$
Note that $s_{n-5}$ does not exist as if it did then $s_{n-5}^{2^8}=2^{16}$ which would be a contradiction.
Hence $n=5$ and the only solution is $(s_1,s_2,s_3,s_4,s_5)=(2^8,2,16,4,8)$ .

Initially I did not checked the case for $(a,c_2,c_1)=(2,4,1)$ and fake solved that $n=4$ :blush:

:blush:

This post has been edited 2 times. Last edited by predictableprimes, Jun 29, 2023, 7:50 PM

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7419 posts

DottedCaculator

#7 h Jun 29, 2023, 6:50 PM • 3 Y

Y by ImSh95, predictableprimes, cubres

Let $s_i=c^{a_i}$ where $c\neq1$ for $i\leq n-1$ . Then, $a_1c^{a_2}=a_2c^{a_3}=\ldots=a_{n-2}c^{a_{n-1}}$ , so $a_i=xc^{b_i}$ for $i\leq n-2$ . Therefore, we get $b_1+xc^{b_2}=b_2+xc^{b_3}=\ldots=b_{n-3}+xc^{b_{n-2}}=N$ . Let $j$ be the largest number such that $N\geq xc^j$ . Since the numbers are distinct, we have $b_1\neq b_2\neq\ldots\neq b_{n-2}$ , so at least $n-5$ of the $b_i$ for $i\geq2$ satisfy $N-xc^{b_i}=b_{i-1}\geq xc^{j-1}(c-1)$ so $xc^{n-6+xc^{j-1}(c-1)}\leq N<xc^{j+1}$ . Solving gives $n-6+xc^{j-1}(c-1)<j+1$ . Since $c>1$ , we get
$j+1>n-6+xc^{j-1}(c-1)\geq n-6+2^{j-1},$ or $n<j+1-2^{j-1}+6\leq7.$ Therefore, $n\leq6$ .

If equality holds, then $c=2$ and $x=1$ , so $a_i$ is a power of $2$ . Therefore, $s_i$ must be a power of $2$ for all $i\leq n$ , which gives a contradiction after the same steps. Therefore, $\boxed{n=5}$ . A construction for $n=5$ is given by $256^2=2^{16}=16^4=4^8=65536$ .

Z K Y

The post below has been deleted. Click to close.

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

5007 posts

#8 h Jun 30, 2023, 2:27 AM • 4 Y

Y by GeoKing, ImSh95, centslordm, cubres

The answer is $5$ ; construction is $256^2=2^{16}=16^4=4^8$ .
Observe that for any $i<n$ and prime $p$ , we have $\tfrac{\nu_p(s_i)}{\nu_p(s_1)}=\tfrac{s_{i+1}}{s_{2}}$ , so for any $i$ , $s_i$ is some rational power of $s_1$ . This implies that there exists some natural number $P$ such that $s_i=P^{a_i}$ for all $i$ , where $a_i$ is a positive integer. The equation then becomes
$a_1P^{a_2}=a_2P^{a_3}=\cdots=a_{n-1}P^{a_n}.$ But then for any $i<j<n$ , the ratio $\tfrac{a_i}{a_j}$ is a power of $P$ , hence we can let $a_i=cP^{b_i}$ for all $i<n$ , where $c$ is a (fixed) natural number. The equation then becomes
$b_1+cP^{b_2}=b_2+cP^{b_3}=\cdots=b_{n-2}+cP^{b_{n-1}}=b_{n-1}+a_n.$
The key claim here is that for $2 \leq i \leq n-1$ we must have $b_i \leq 2$ . Indeed, by taking $i$ such that $b_i$ is maximal, we find that
$b_{i-1}+cP^{b_i}=b_i+cP^{b_{i+1}} \implies b_{i-1}=b_i-c(P^{b_i}-P^{b_{i+1}})\leq b_i-cP^{b_i-1}\leq b_i-2^{b_i-1},$ but if $b_i \geq 3$ then this final value is negative. Since we need $a_i$ to be a positive integer, we have $cP^{b_{i-1}} \geq 1$ , so $cP^{b_i-1}=cP^{b_{i-1}}\cdot P^{b_i-b_{i-1}-1}\geq P^{b_i-b_{i-1}-1}$ , so $b_{i-1} \leq b_i-P^{b_i-b_{i-1}-1} \implies P^{b_i+(-b_{i-1})-1} \leq b_i+(-b_{i-1})$ , but this can clearly be checked to be impossible (for $b_i \geq 3$ ).

This finishes the problem, since the $b_i$ must be distinct, so between $2$ and $n-1$ inclusive there are at most $3$ of them. This misses $b_1$ and also $a_n$ (since $b_n$ doesn't exist), so $n=5$ is maximal. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

254 posts

#9 h Jul 1, 2023, 4:00 PM • 2 Y

Y by GeoKing, cubres

My problem!

Original problem statement wrote:

Determine the longest possible length of a sequence of distinct positive integers $s_1$ , $s_2$ , $\ldots$ , $s_n$ for which
$s_1^{s_2} = s_2^{s_3} = \ldots = \left(s_{n-1}\right)^{s_n}.$

Solution

Z K Y

The post below has been deleted. Click to close.

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

1605 posts

#10 h May 15, 2025, 11:00 PM • 1 Y

Y by cubres

For some prime $p$ basically we have $s_2 \nu_p(s_1)=s_3 \nu_p(s_2) = \cdots =s_n \nu_p(s_{n-1})$ , also notice if a prime $p$ divides some $s_i$ here for $i$ between $1,n-1$ , then it divides all as well and combined we have that for any two primes $p \ne q$ that $\frac{\nu_p(a_i)}{\nu_q(a_i)}$ is constant for all $1 \le i \le n-1$ (as long as $q$ divides one of the terms at least ofc), then from fixing the pick of $q$ and moving $p$ over all primes dividing the terms $s_1, \cdots, s_{n-1}$ we have that each of them is the power of a same positive integer $P$ , so now let $s_i=P^{a_i}$ for some positive integer $a_i$ for all $1 \le i \le n-1$ , then we have that $a_1 \cdot P^{a_2}= \cdots =a_{n-2} \cdot P^{a_{n-1}}=a_{n-1}s_n$ , also notice that for $n=5$ we have the construct $256^2=2^{16}=16^4=4^8$ , so now FTSOC suppose we can have $n \ge 6$ .
The idea is that we can check the $a_2 \cdot P^{a_3}=a_3 \cdot P^{a_4}=a_4 \cdot P^{a_5}$ then $P^{a_4}=\frac{a_2}{a_3} \cdot P^{a_3}$ so $\frac{a_3}{a_2}$ is $P^k$ for some $k \in \mathbb Z$ that is nonzero, and thus $a_3=a_2 \cdot P^k$ but also $a_4=a_3-k=a_2 \cdot P^k-k$ and thus we have that $P^{a_5}=\frac{P^{a_2 \cdot P^k}}{P^k-\frac{k}{a_2}}$ and so the denominator also has to be a rational power of $P$ , now if $k>0$ then $P^k-k \le P^k-\frac{k}{a_2} \le P^{k-1}$ which gives that $k \ge P^{k-1}(P-1)$ and if $P \ge 3$ then you will just never reach it, otherwise you must have $P=2$ and $k=1,2$ and thus equality always holds regardless which means that $a_2=1$ so if $k=2$ then $a_3=4$ and thus $a_4=2$ but then remember $2a_1=16$ so $a_1=8$ and then $2^{a_5}=8$ so $a_5=3$ but then we have $a_5 \mid 16$ which can't happen so contradiction, and if $k=1$ then $a_3=2$ but also $a_1 \cdot 2=4$ so $a_1=2$ which can't happen.
Therefore $k>0$ can't happen so if $k<0$ then we have $1-\frac{k}{a_3}$ to be a power of $P$ as well which is $1-\frac{k \cdot P^{-k}}{a_2}$ being an integer power of $P$ . So if $-k \ge a_2$ then its a power of $P$ greater than $P^{-k}$ but as a result $P^{-k} \mid a_2$ so $-k \ge P^{-k}$ and this is just never true so we must have $a_2 \ge 1-k$ , in fact notice we just also have $a_2=a_3 \cdot P^{-k} \ge P^{-k}$ but it happens now that $a_1=a_2 \cdot P^{a_2(P^k-1)}=a_3 \cdot P^{a_3(1-P^{-k})-k} \ge 1$ which means that $a_3 \ge P^{a_3(P^{-k}-1)+k} \ge 2^{a_3(2^{-k}-1)+k}$ so if $a_3=1$ we have a trivial contradiction, if $a_3=2$ then we have $1 \ge 2^{1-k}-2+k$ so $3-k \ge 2^{1-k}$ which can only happen when $k=-1$ so $a_2=4$ but as equality holds we have $a_1=1$ and then $a_4=3$ but that would mean $a_4 \mid 16$ which is false, so if $a_3 \ge 3$ then think that $a_3(2^{-k}-1)+k \ge a_3-1$ and thus $a_3 \ge 2^{a_3-1}$ which is only true when $a_3=1,2$ so contradiction!.
Therefore either way $n \ge 6$ is not feasable, thus $n=5$ is maximun thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

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

284 posts

#11 h Jun 14, 2025, 5:33 PM • 1 Y

Y by cubres

See that we have $s_i=a^{x_i}$ where $a$ is not a perfect square and hence we are solving $x_1a^{x_2}=\dots=x_{n-1}a^{x_n}$ Now $x_i/x_j$ is a perfect square for $1 \le i,j \le n-1$ and hence write $x_i=Ca^{y_i}$ for $1 \le i \le n-1$ and finally we are solving $y_1+Ca^{y_2}=\dots=y_{n-2}+Ca^{y_{n-1}}$ where $y_i \ge 0$ are pairwise distinct. Assume $a \ge 2$ otherwise $n=2$ and assume from now $n$ is as large as it can be.

Let $y_k=\max\{y_2,\dots,y_{n-1}\}$ and hence let $i$ be in this range with $i \ne 2,k$ and so $a^{y_k-1} \le Ca^{y_k-1}(a-1) \le Ca^{y_k}-Ca^{y_i}=y_{i-1}-y_{k-1} \le y_k \implies y_k \le 2$ Now as $y_2$ , $\dots$ , $y_{n-1}$ are all pairwise distinct and in range $[0,2]$ we have $n-2 \le 3$ so $n \le 5$ .

The construction is $256^2=2^{16}=16^4=4^8$ and hence $\boxed{n=5}$ is the answer.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a