Silly Sequences

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

Silly Sequences

G H J

Reveal topic tags

Integer sequence

L

G H BBookmark kLocked kLocked NReply

Source: ELMO 2018 #2, 2018 ELMO SL N3

The post below has been deleted. Click to close.

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

975 posts

#1 h Jun 28, 2018, 7:11 AM • 7 Y

Y by Carpemath, MathbugAOPS, k12byda5h, Hoto_Mukai, Dennis1208, Adventure10, Mango247

Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$ for all positive integers $k$ and $n.$ For a given positive integer $m,$ find the maximum possible value of $a_{2m}.$

Proposed by Krit Boonsiriseth

This post has been edited 1 time. Last edited by whatshisbucket, Jun 29, 2018, 1:05 AM

Z K Y

The post below has been deleted. Click to close.

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

698 posts

#2 h Jun 28, 2018, 7:21 AM • 4 Y

Y by Carpemath, MathbugAOPS, PRMOisTheHardestExam, Adventure10

outline of the solution

Z K Y

The post below has been deleted. Click to close.

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

dragonmaster3000

306 posts

dragonmaster3000

#3 h Jun 28, 2018, 7:33 AM • 8 Y

Y by Carpemath, wu2481632, cjquines0, enzoP14, centslordm, Kobayashi, Adventure10, Mango247

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

2130 posts

DrMath

#4 h Jun 28, 2018, 7:41 AM • 6 Y

Y by Hamel, Carpemath, Epison11, Kobayashi, Adventure10, Mango247

Note that $a_n\mid a_{k+n}-a_k$ since $a_n\mid a_k+\cdots + a_{k+n-1}$ and $a_n\mid a_{k+1}+\cdots + a_{k+n}$ ; subtracting gives the claim. Write $S_n=a_1+a_2+\cdots + a_n$ .

Note that $a_{2m}=\boxed{2^m-1}$ is attainable via the sequence $a_{2n}=2^n-1$ and $a_{2n-1}=1$ ; indeed, we only need to check the divisibility condition for even $n$ ; note that $a_{2n}\mid a_1+\cdots + a_{2n} = 2^{n+1}-2$ , $a_{2n}\mid a_{2k+2n}-a_{2k}=2^{k+n}-2^k$ , and $a_{2n}\mid a_{2k+2n-1}-a_{2k-1}=0$ ; from this, it is easy to see the divisibility condition holds.

We prove the following claims simultaneously via induction:

$S_{2m}\le 2^{m+1}-2 \text{ and } a_{2m}\le 2^m-1$
Indeed, the base case $m=1$ is easy: note that $a_2\mid a_1+a_2=1+a_2$ , so we are forced to have $a_2=1$ and $S_2=2$ .

Now, suppose the statement is true for $m$ . First, note that $a_i\mid S_{i-1}$ in general, since $a_i\mid a_1+\cdots + a_i=S_{i-1}+a_i$ . Let $S=S_{2m}$ . We have $a_{2m+1}\mid S$ , $a_{2m+2}\mid S_{m+1}=S+a_{2m+1}$ , and $a_{2m+1}\mid a_{2m+2}-a_1=a_{2m+2}-1$ . Now, note that $a_{2m+2}\mid a_{2m+1}\left(\frac{S}{a_{2m+1}}+1\right)\mid (a_{2m+2}-1)\left(\frac{S}{a_{2m+1}}+1\right)$ Thus, $a_{2m+2}\mid \frac{S}{a_{2m+1}}+1$ . But this means that $a_{2m+2}-1\le \frac{S}{a_{2m+1}}$ , so $a_{2m+1}(a_{2m+2}-1)\le S=S_m$ . In particular, since $a_{2m+1}$ and $a_{2m+2}$ are integers, we have $a_{2m+1}+a_{2m+2}-1\le S_m+1\le 2^{m+1}-1$ (since the sum of two integers with a product $P$ is at most $P+1$ ). Thus, $a_{2m+1}+a_{2m+2}\le 2^{m+1}$ . Since $a_{2m+1}\ge 1$ , we have $a_{2m+2}\le 2^{m+1}-1$ , proving the second part of the inductive step. To prove the first part, just note that $S_{m+1}=S_m+a_{2m+1}+a_{2m+2}\le 2^{m+1}-2+2^{m+1}=2^{m+2}-2$ . Thus by the inductive claim, we have $a_{2m}\le 2^m-1$ for all $m$ as desired. $\square$

Z K Y

The post below has been deleted. Click to close.

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

370 posts

#5 h Jun 28, 2018, 7:45 AM • 3 Y

Y by Carpemath, Adventure10, Mango247

First observe that $\gcd (a_n,a_{n+1})=1$ . Then I use induction to prove $a_{2n} \le 2^n-1$ and $S_{2n} \le 2^{n+1}-2$ By $\gcd (a_n,a_{n+1})=1$ , we have $a_{2n}a_{2n+1} \mid S_{2n}$ . Then it's enough to apply AM-GM inequality.

lol, seems to be similar as above.

This post has been edited 1 time. Last edited by liekkas, Jun 28, 2018, 7:46 AM

Z K Y

The post below has been deleted. Click to close.

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

698 posts

#6 h Jun 28, 2018, 7:57 AM • 3 Y

Y by Carpemath, Adventure10, Mango247

whatshisbucket wrote:

Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$ for all positive integers $k$ and $n.$

These sequences seem very interesting. Any extensions?

Z K Y

The post below has been deleted. Click to close.

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

354 posts

#7 h Jun 28, 2018, 8:01 AM • 3 Y

Y by Carpemath, Adventure10, Mango247

Superguy wrote:

So here is my solution.
We see that in the sequence
$a_n|a_k+a_{k+1}+\cdots +a_{k+n-1}$
And after replacing (k) with (k+1),
$a_n|a_{k+1}+a_{k+2}+\cdots +a_{k+n}$
Subtracting both the equations we get,

$a_{n+k}\equiv a_k\pmod{a_n}-(1)$ Which gives us a generalisation for all positive integers k and n.
I generate an arbitrary sequence $l_n$
Such that
$l_{2i}=2^i-1$
$l_{2i+1}=1$
For all Nonnegative integers i.
Claim-(1)
Claim-(2)
Using both our claims we can conclude that $l_n$ is also a type of sequence $a_n$ .
Using our generalisation we get
$gcd(a_{n},a_{n+1})=1$
$\implies lcm(a_n,a_{n+1})=a_n.a_{n+1}|a_1+a_2+a_3\cdots +a_n$

Now if $a_{2m}\geq 2^m$ for some sequence of type $a_n$ .
We get $a_{2m}.a_{2m-1}\leq a_1+a_2+a_3\cdots +a_{2m-1}$
$\implies 2^m-1\leq 2^m-1(a_{2m-1})\leq a_1+a_2+a_3\cdots +a_{2m-2}$
Now we are in a position to apply strong induction.
$\boxed{Claim-(3)}$

For all sequences $a_n$ ,
$2^m-1>a_1+a_2+a_3+\cdots +a_{2m-2}$

$\boxed{Proof}$

We will induct on m.
Base case:

$m=2$
$2^2-1=3>a_1+a_2=2$
$m=3$
$2^3-1=7>a_1+a_2+a_3+a_4=6(max)$
Inductive hypothesis

Assume for integers $m=(1,2,.....k)$ the statement holds true.
$\implies 2^k-1> a_1+a_2+\cdots +a_{2k-2}$
We need to prove for $m=k+1$
Now for $a_{2k-1}\geq 3$ and $a_{2k}\geq 4$
$a_{2k-1}+a_{2k}\leq (a_{2k-1})(a_{2k}-1)\leq a_1+a_2+a_3+a_+\cdots a_{2k-2}<2^k-1$
(Inductive hypothesis)
So in this case
$a_1+a_2+\cdots a_{2k}<2^k-1+2^k-1=2^{k+1}-2<2^{k+1}-1$
For the other cases,
If
$\boxed{a_{2k-1}=1}$
$a_{2k}\leq a_1+a_2+\cdots +a_{2k-2}+a. _{2k-1}<2^k-1+1=2^k$
So if $2^k>a_{2k}$ then $2^k\geq a_{2k}+1$
Thus $a_1+a_2+\cdots a_{2k}<2^k-1+2^k-1+1=2^{k+1}-1$

If
$\boxed{a_{2k}=1}$
$a_{2k-1}\leq a_1+a_2+\cdots +a_{2k-2}<2^k-1$
Thus again $a_1+a_2+\cdots a_{2k}<2^k-1+2^k-1+1=2^{k+1}-1$

If
$\boxed{a_{2k}=2}$ then clearly $a_{2k-1}=1$
So $a_1+a_2+\cdots a_{2k}<2^k-1+3<2^{k+1}-1$
For $k\geq 2$

If $a_{2k-1}=2$ and $a_{2k}=3$ ,
Again
$a_1+a_2+\cdots a_{2k}<2^k-1+5<2^{k+1}-1$
For $k\geq 3$

So we have tackled all the cases and our inductive step is complete. $\square$
So as per our last claim we can see that the statement that $a_{2m}\geq 2^m$ for some sequence $a_n$ is false.
So $a_{2m}\leq 2^m-1$ As we can see that in sequence $l_n$
The max value of $a_{2m}$ appears as $2^m-1$ .
Hence we conclude that maximum possible value of $a_{2m}=2^m-1$ .

Z K Y

The post below has been deleted. Click to close.

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

3042 posts

#8 h Jun 28, 2018, 10:15 AM • 3 Y

Y by Carpemath, Adventure10, Mango247

Main idea

Z K Y

The post below has been deleted. Click to close.

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

6870 posts

#9 h Jun 28, 2018, 2:43 PM • 6 Y

Y by Carpemath, Achillys, v4913, Hoto_Mukai, Adventure10, Mango247

For every even integer $n = 2m$ we will prove that $a_{n} \le 2^{m}-1$ . To see this is attainable, consider the sequence $a_n = \begin{cases} 1 & n \text{ odd} \\ 2^{n/2}-1 & n \text{ even}. \end{cases}$ This can be checked to work, so we prove it's optimal.

We have $a_2 \mid a_1+a_2 = 1+a_2 \implies a_2 = 1$ .

Now consider an integer $n$ , and let $s = s_n = a_1 + \dots + a_n$ . Then $\begin{align*} a_{n+1} &\mid s \\ a_{n+2} &\mid s + a_{n+1} \\ a_{n+2} &\equiv 1 \pmod{a_{n+1}}. \end{align*}$ Thus, $\gcd(a_{n+2}, a_{n+1}) = 1$ . So $a_{n+2} \le \frac{s + a_{n+1}}{a_{n+1}}$ , and thus $a_{n+1} + a_{n+2} \le 1 + a_{n+1} + \frac{s}{a_{n+2}} \le s+2.$
So, we have $\begin{align*} a_1 + a_2 &= 2 \\ a_3 + a_4 &\le 2+2 = 4 \\ a_5 + a_6 &\le (2+4)+2 = 8 \\ a_7 + a_8 &\le (2+4+8)+2 = 16 \\ &\vdots \\ a_{2m-1} + a_{2m} &\le 2^{m}. \end{align*}$ Thus $a_{2m} \le 2^{m} - a_{2m-1} \le 2^{m}-1$ .

Remark: [Motivational notes] It's very quick to notice $a_{n+1} \mid a_1 + \dots + a_n$ , which already means that given the first $n$ terms of the sequence there are finitely many possibilities for the next one. Thus it's possible to play with ``small cases'' by drawing a large tree.

When doing so, one might hope that somehow $a_n = a_1 + \dots + a_{n-1}$ is achievable, but quickly notices in such a tree that if $a_n$ is the sum of all previous terms, then $a_{n+1} = 1$ is forced. This gives the idea to try to look at the terms in pairs, rather than one at a time, and this gives the correct bound.

As for extracting the equality case from this argument, there are actually two natural curves to try. We have $a_3 \mid 1+1 = 2$ . If we have $a_3 = 2$ we get $a_4 = 1$ , $a_5 \le 5$ , but then $a_6$ actually gets stuck. But if we have $a_3 = 1$ instead, we get $a_4 = 3$ , $a_5 = 1$ , $a_6 = 7$ , and so on; pushing this gives the equality case above, seen to work. I think it's quite unnatural to guess the correct construction before having the corresponding $s+2$ estimate.

Z K Y

The post below has been deleted. Click to close.

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

442 posts

#10 h Jun 28, 2018, 4:56 PM • 5 Y

Y by Carpemath, MathbugAOPS, L567, Adventure10, Mango247

I think it's possible to completely characterize sequences $a$ for which $a_n \mid a_k + a_{k+1} + \cdots + a_{k+n-1}$ I would be thankful if someone could go through the attached pdf file and check if I have made any mistakes.

Note. I don't think I mentioned that I call a number $n$ important if $a_n>1$ and esteemed if $a_n = \sum_{i=1}^{n-1}a_i$ .

@below The problem only asks us to find the minimal possible value of $a_{2m}$ . I found all sequences $a$ that satisfy the problem condition

Attachments:

ELMO_Type_Sequences.pdf (202kb)

This post has been edited 4 times. Last edited by p_square, Jul 31, 2020, 11:14 AM

Z K Y

The post below has been deleted. Click to close.

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

343 posts

#11 h Jun 28, 2018, 5:14 PM • 3 Y

Y by Carpemath, Adventure10, Mango247

p_square wrote:

Slight generalisation: To find maximum of $a_m$ .
https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYi85L2VmZmZiMDdhYzM1YTA1MDk1Yzc0MWNjOGVlMTY5MGYyMDY3NGRhLnBkZg==&rn=RUxNT18xOC5wZGY=

I didn't see how you generalize it

Z K Y

The post below has been deleted. Click to close.

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

206 posts

#13 h Jul 31, 2020, 3:25 AM • 1 Y

Y by Nathanisme

Solution

Z K Y

The post below has been deleted. Click to close.

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

1081 posts

#14 h Nov 1, 2020, 2:12 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

691 posts

#15 h Jan 3, 2021, 9:26 AM

Y by

whatshisbucket wrote:

Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$ for all positive integers $k$ and $n.$ For a given positive integer $m,$ find the maximum possible value of $a_{2m}.$

Proposed by Krit Boonsiriseth

Interesting problem. I claim that the answer is $\boxed{a_{2m} \le 2^m - 1}$ achieved by the sequence:
$\begin{align*} \begin{cases} a_{2k + 1} &= 1 \ \ \ \ \ \ \ \ \text{for } k \in \mathbb{N} \\ a_{2k} &= 2^k - 1 \ \text{for } k \in \mathbb{N} \end{cases} \end{align*}$ Claim 01 (Main Claim). For any $m \in \mathbb{N}$ , $a_{2m - 1} + a_{2m} \le 2^{m}$ .
Proof. To prove this, let us observe the sequence
$a_n \mid a_k + a_{k + 1} + \dots + a_{k + n - 1}$ This quickly gives us
$a_n \mid a_1 + a_2 + \dots + a_{n - 1} \ \text{and} \ a_n \mid a_{n + 1} - a_1 = a_{n + 1} - 1$ Therefore,
$a_n \mid a_1 + a_2 + \dots + a_{n - 1}$ $a_{n + 1} \mid a_1 + a_2 + \dots + a_n = a_n \left( 1 + \frac{a_1 + a_2 + \dots + a_{n - 1}}{a_n} \right)$ Since $a_{n + 1} \equiv 1 \ (\text{mod} \ a_n)$ , then $\gcd(a_n, a_{n + 1}) = 1$ , and hence,
$a_{n + 1} \mid 1 + \frac{a_1 + a_2 + \dots + a_{n - 1}}{a_n}$ Therefore, we have $a_{n + 1} \le 1 + \frac{a_1 + a_2 + \dots + a_{n - 1}}{a_n}$ .

Now, we'll induct. The statement is true for $m = 1$ , as $a_1 = a_2 = 1$ . Now, suppose that the statement is true for $m = k$ . Then, we have
$a_{2k + 1} + a_{2k + 2} \le a_{2k + 1} + 1 + \frac{a_1 + a_2 + \dots + a_{2k}}{a_{2k + 1}} \le a_1 + a_2 + \dots + a_{2k} + 2 = (2^1) + (2^2) + \dots + (2^k) + 2 = 2^{k + 1}$ We are done.

To finish this, notice that $1 + a_{2m} \le a_{2m - 1} + a_{2m} \le 2^m \Rightarrow a_{2m} \le 2^m - 1$ , we are done.

Remark. I think the hardest problem of this problem is figuring out the main claim and equality case. The main claim comes intuitively after trying to bash several small cases (drawing a diagram tree helps a lot). The main key here is the bounding part, for the bounding to be as strong as possible. The last part when inducting comes naturally (inspired a lot from 2018 A4 somehow) since the inequality focus on one variable $a_{2k + 1}$ and other terms are fixed.

Z K Y

The post below has been deleted. Click to close.

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

1065 posts

Eyed

#16 h Feb 12, 2021, 7:58 PM

Y by

The answer is $2^{1009} - 1$ . The construction is as follows: Let $a_{2k+1} = 1, a_{2k} = 2^{k} - 1$ . It's not hard to check that this works. We will prove this is maximal.

First, let $S_{n} = a_{1} + a_{2} + \ldots + a_{n}$ . I claim $S_{2n-1}\leq 2^{n} - 1$ . We can prove this by induction. If we let our base case be $n = 1$ , we have $S_{1} = 1 \leq 2^{1} - 1 = 1$ . For our inductive step, assume $S_{2n-1}\leq 2^{n} - 1$ , we will prove $S_{2n + 1} \leq 2^{n+1} - 1$ .

First, observe that $a_{2n} | a_{2n} + \ldots + a_{1} \Rightarrow a_{2n} | S_{2n-1}$ . Next, observe that
$a_{2n} | a_{2n} + \ldots + a_{1}, a_{2n+1} + a_{2n} + \ldots a_{2} \Rightarrow a_{2n} | a_{2n+1} - a_{1} = a_{2n+1} - 1$ Thus, $a_{2n+1} \equiv 1\mod a_{2n}$ . Let $r$ be the number such that $a_{2n}r = S_{2n-1}$ , and $k$ be the number such that $a_{2n+1} = ka_{2n} + 1$ . By euclidean algorithm, $\gcd(a_{2n+1}, a_{2n}) = 1$ . We also have
$a_{2n+1} = | a_{2n+1} + a_{2n} + \ldots + a_{1}, a_{2n} + S_{2n-1} = a_{2n}(r+1)$ Since $\gcd(a_{2n+1}, a_{2n}) = 1$ , this means $a_{2n+1} | r+1 \Rightarrow a_{2n+1}\leq r+1$ . Then,
$S_{2n+1} = S_{2n-1} + a_{2n} + a_{2n+1} \leq S_{2n-1} + a_{2n} + \frac{S_{2n-1}}{a_{2n}} + 1 \leq 2S_{2n-1} + 1 \leq 2^{n+1} - 1$ This proves our desired induction.

Now, observe that
$a_{2018} | a_{2018} + a_{2017} + \ldots + a_{1} \Rightarrow a_{2018} | S_{2017}$ This means
$a_{2018}\leq S_{2017} \leq 2^{1009} - 1$

Z K Y

The post below has been deleted. Click to close.

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

572 posts

anser

#17 h Apr 2, 2021, 4:46 PM

Y by

The answer is $2^m - 1$ achievable by the sequence
$a_i = \begin{cases} 1 & i \text{ is odd} \\ 2^{i/2}-1 & i \text{ is even}. \end{cases}$
First, $a_{2m-1} \mid a_{2m} - a_1 = a_{2m} - 1$ , so $\gcd(a_{2m-1}, a_{2m}) = 1$ . Now since $a_{2m-1}, a_{2m} \mid a_1 + \cdots + a_{2m-1}$ , we have
$a_{2m-1}a_{2m} \le a_1 + \cdots + a_{2m-1} \implies a_{2m} \le \frac{a_1 + \cdots + a_{2m-2}}{a_{2m-1}} + 1.$ So
$\begin{align*} a_1 + \cdots + a_{2m} &= (a_1 + \cdots + a_{2m-2}) + a_{2m-1} + \frac{a_1 + \cdots + a_{2m-2}}{a_{2m-1}} + 1\\ &\le 2(a_1 + \cdots + a_{2m-2}) +2. \end{align*}$ Noting that $a_2 = 1$ , we inductively have $2a_{2m} \le a_1 + \cdots + a_{2m} \le 2(2^m - 1)$ , giving $a_{2m}\le 2^m - 1$ .

Z K Y

The post below has been deleted. Click to close.

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

2726 posts

#18 h Jun 20, 2021, 4:41 AM

Y by

In general, we have the upper bound $a_{2m} \leq 2^m - 1$ , where this is achievable by letting $a_{odd} = 1$ and $a_{2k} = 2^k - 1$ : a quick check shows that this sequence does indeed work.

Note that $a_n \mid a_k + \ldots + a_{k + (n-1)}$ and $a_n \mid a_{k + 1} + \ldots + a_{k + n}$ hence $a_n \mid a_{k+n} - a_k$ , always. Note that this means $a_{2k-1} \mid a_{2k} - 1$ for all $k$ . Thus, it also follows that $a_{2k-1}, a_{2k}$ must always be relatively prime. Additionally, since the sum of any consecutive $r$ terms is divisible by $a_r$ , note that $a_{2r}$ divides $a_1 + \ldots + a_{2r}$ and thus $a_1 + \ldots + a_{2r-1}$ , and $a_{2r-1}$ also divides $a_1 + \ldots + a_{2r-1}$ . Thus, we may arrive at the size bound $a_{2r-1}a_{2r} \leq a_1 + \ldots + a_{2r - 1}$ for all positive integers $r$ . We will induct to show that $a_{2r - 1} + a_{2r} \leq 2^r$ for all positive integers $r$ . The base case is easy: note $a_2 \mid a_1 + a_2$ hence $a_2 = 1$ , and $a_1 + a_2 = 2 \leq 2$ . Now, we use strong induction; suppose $a_{2r - 1} + a_{2r} \leq 2^r$ up until $r = k$ . Then, $a_{2k+1}a_{2k+2} \leq (2^1 + \ldots + 2^k) + a_{2k+1} \iff a_{2k+1}(a_{2k+2} - 1) \leq 2(2^k - 1).$ It is known that if positive $ab = c$ , then $a+b$ is maximized when $a$ is as small (but still positive) as possible (in fact, if they are positive integers, then $a + b \leq 1 + c$ ). Hence, if $a_{2k+1}(a_{2k+2} - 1) = P \leq 2(2^k - 1)$ then $a_{2k+1} + (a_{2k+2} - 1) \leq 1 + P \leq 2^{k+1} - 1$ so indeed $a_{2k+1} + a_{2k+2} \leq 2^{k+1}$ , finishing our induction.

This also finishes the problem: if $a_{2r-1} + a_{2r} \leq 2^r$ for all $r$ , then $a_2r \leq 2^r - 1$ for all $r$ .

This post has been edited 1 time. Last edited by jj_ca888, Jun 20, 2021, 4:41 AM

Z K Y

The post below has been deleted. Click to close.

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

121 posts

mijail

#19 h Jan 25, 2022, 5:44 PM

Y by

My answer is $a_{2m}= 2^m-1$ , the example is $a_{2i}=2^i-1, a_{2i-1}=1$ for all $n$ positive integer.

Key claim: For all any positive integer $n$ : $a_{2n}+a_{2n-1} \leq 2^n$
Proof: We have that: $a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}, a_n \mid a_{k+1}+a_{k+2}+\dots+a_{k+n} \implies a_n \mid a_{k+n}-a_k$
We have that $a_1=1$ so $a_n \mid a_{n+1}-1 \implies (a_n,a_{n+1})=1$ , then:
$a_n \mid a_1 + \dots+a_n$ $a_{n+1} \mid a_1+ \dots + a_{n+1} \implies a_{n+1} \mid a_1+ \dots + a_n$ $a_na_{n+1} \mid a_1+ \dots +a_n \implies a_{2n}a_{2n-1} \mid a_1+ \dots +a_{2n-1}$ And now we can prove the key claim with induction: $a_{2n}a_{2n-1} \leq (a_1+ \dots +a_{2n-1})+a_{2n} \leq 2^1+2^2+\dots +2^{n-1} + a_{2n-1}= 2^n-2+a_{2n-1} \implies a_{2n-1}(a_{2n}-1) \leq 2^n-2$ Finally if $a_{2n} \ge 2 \implies a_{2n-1}+(a_{2n}-1)-1 \leq a_{2n-1}(a_{2n}-1) \leq 2^n-2$ this implies the claim.
And if $a_{2n}=1\implies a_{2n-1} \mid a_1 + \dots + a_{2n-2} \implies a_{2n-1} \leq 2^n-2 \implies a_{2n}+a_{2n-1} \leq 2^n-1$

And with this $a_{2n}+a_{2n-1} \leq 2^n \implies a_{2n} \leq 2^n-1$ 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.

108 posts

#20 h May 17, 2023, 8:12 AM

Y by

The answer is $2^m-1$ - do this by considering $a_{2n}=2^i-1$ and $a_{2n-1}=1$ for positive integers $n$ .

Key Claim: $a_n+a_{n+1}\leq a_1+\ldots +a_{n-1}+2=s_{n-1}+2$ .
Proof: If $a_n=1$ then since $a_{n+1}\mid a_1+\ldots + a_n$ we have $a_n+a_{n+1}\leq a_n + s_n=s_{n-1}+2$ .

If $a_{n+1}=1$ then $a_n\mid a_1+\ldots+a_{n-1}$ so $a_n+a_{n+1}\leq s_{n-1}+1\leq s_{n-1}+2$ .

If $a_n,a_{n+1}\neq 1$ then since $a_n\mid a_1+\ldots +a_n$ and $a_2+\ldots +a_{n+1}$ we have $a_{n+1}=ka_n+1$ for some positive integer $k$ . But $a_n$ and $ka_n+1=a_{n+1}\mid s_n$ so $a_n(ka_n+1)\mid s_n$ because $\gcd(a_n,ka_n+1)=1$ . Thus,
$a_n+a_{n+1}=(k+1)a_n+1\leq ka_n^2+1=a_n(ka_n+1)+1-a_n\leq s_n+1-a_n=s_{n-1}+1\leq s_{n-1}+2$ as needed.

Using the claim:
$a_{2m}+a_{2m-1}\leq (a_1+a_2)+\ldots+(a_{2m-3}+a_{2m-2})+2\leq 2+4+\ldots+2^m + 2\leq 2^m-2+2=2^m$ . Thus, $a_{2m}\leq 2^m-a_{2m-1}\leq 2^m-1$ .

This post has been edited 2 times. Last edited by NoctNight, May 17, 2023, 8:29 AM

Z K Y

The post below has been deleted. Click to close.

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

44 posts

#21 h Jun 26, 2023, 11:24 AM

Y by

Here's a solution which classifies which numbers can and can't go to $1$ . Denote $a_n=f(n)$ .

Let $\mathcal{A}$ denote the numbers whose image isn't $1$ and $\mathcal{B}$ the rest.
Claim: If $a\in\mathcal{A}$ , $b\in\mathcal{B}$ and $a<b$ , then $b-a\in\mathcal{B}$ .
Proof. Then $f(a)\mid f(b-a)-1$ and $f(b-a)\mid f(a)-1$ . If neither are $1$ , we get $f(a)<f(b-a)<f(a)$ , absurd.

So if $\mathcal{A}$ has two coprime elements, $\mathcal{B}$ must be finite (linear sums of coprime numbers span $\mathbb{N}$ after some point). Well,
Claim: $\mathcal{B}$ is infinite.
Proof. $f(2)\mid 1$ so $f(2)=1$ . Assume the contrary, and for $f(n)>1$ for $n\ge C$ . Then $f(n-1)\mid f(n)-1\text{ }(\spadesuit)\text{ and }f(n-2)\mid f(n)-1\text{ }(\heartsuit)$ so $f$ is increasing in $[C,+\infty)$ and $f$ is bounded below by some $n-c$ . By the divisibility, $f(n)< (n-k)f(n-1)$ for sufficiently large $n$ depending on $k$ . $f(n+1)\neq f(n)+1$ for all large $n$ we would have a contradiction because the sequence would be $\mathcal{O}(2^n)$ . If $f(n-1)=f(n-2)+1$ , from $(\spadesuit)$ and $(\heartsuit)$ , $f(n-1)(f(n-1)-1)\mid f(n)-1\Rightarrow f(n)>(n-1-c)f(n-1)\Rightarrow n-k>n-1-c$ and choosing $k>c+1$ , we get a contradiction.

Because $2018=2\cdot 1009$ , and if $f(1009)\neq1$ we wouldn't get a maximum, we get $f$ at odds is $1$ and at evens $f(2k)\mid k+f(2)+f(4)+\dots+f(2k-2)\Longrightarrow f(2k)\le 2^k-1$ and equality can hold. Thus, $f(2018)\le\boxed{2^{1009}-1.}$

Z K Y

The post below has been deleted. Click to close.

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

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#22 h Jul 22, 2023, 3:25 AM

Y by

this problem makes me so happy

The answer is $2^m-1$ , achieved by the sequence $1,2^1-1,1,2^2-1,1,2^3-1,\ldots$ . We show that this sequence satisfies the problem conditions. If $n$ is odd, then $a_n=1$ , so $a_n \mid a_k+a_{k+1}+\cdots+a_{k+n-1}$ . If $n$ is even, then let $a_k+a_{k+1}=2^m$ . Notice that $a_{i+2}+a_{i+3}=2(a_i+a_{i+1})$ for all positive integers $i$ , so $a_{k+2i}+a_{k+2i+1}=2^{m+i}$ for all positive integers $i$ , so $a_k+a_{k+1}+\cdots+a_{k+n-1}=2^m+2^{m+1}+\cdots+2^{m+n/2-1}=2^m(2^{n/2}-1)$ is divisible by $a_n=2^{n/2}-1$ .

Now, we show that $a_{2m} \le 2^m-1$ . Let $s_n=a_1+a_2+\cdots+a_n$ for all positive integers $n$ .

Claim: $s_n \le 2s_{n-2}+2$ for all integers $n \ge 3$ .

Proof: We have $a_n \mid s_n$ , so $a_n \mid s_{n-1}$ . We also have $a_{n-1} \mid s_{n-1}$ . Notice that $a_{n-1} \mid s_n-1$ , so $a_{n-1} \mid s_n-1-s_{n-1}=a_n-1$ . Thus, $\gcd(a_{n-1},a_n)=1$ , so $a_n \mid s_{n-1}$ and $a_{n-1} \mid s_{n-1}$ imply $a_{n-1}a_n \mid s_{n-1}$ . Therefore, we have $a_{n-1}a_n \le s_{n-1}$ , or $a_{n-1}(a_n-1) \le s_{n-2}$ . If $a_n=1$ , then $a_{n-1} \le s_{n-2}$ , so $s_n=s_{n-2}+a_n+a_{n-1} \le 2s_{n-2}+1$ , as desired. If $a_n \ne 1$ , then $a_{n-1}+a_n-1 \le s_{n-2}+1$ by smoothing, so $a_{n-1}+a_n \le s_{n-2}+2$ , which means $s_n \le 2s_{n-2}+2$ , as desired. $\square$

We have $a_2=1$ , so $s_2=2$ . By induction using the previous claim, we have $s_{2m} \le 2^{m+1}-2$ . Since $a_{2m} \le s_{2m-1}$ , we have $a_{2m} \le 2^m-1$ . $\square$

This post has been edited 2 times. Last edited by CyclicISLscelesTrapezoid, Sep 5, 2023, 9:24 PM

Z K Y

The post below has been deleted. Click to close.

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

5000 posts

#23 h Aug 8, 2023, 2:37 PM • 1 Y

Y by centslordm

surprising

The answer is $2^m-1$ , achieved by making $a_{2i-1}=1$ and $a_{2i}=2^i-1$ for all $i \geq 1$ , which can be checked to work. In general, note that $a_k \equiv a_{k+n} \pmod{a_n}$ for all positive integers $k,n$ . The following claim is the the main part of the problem.

Claim: We have $a_{2i-1}+a_{2i} \leq 2^i$ for all positive integers $i$ .
Proof: This is by strong induction, with the base case of $i=1$ being clear. For $i \geq 2$ , let $a_1+\cdots+a_{2i-2}=ka_{2i-1}$ . Then, we should have $a_{2i} \equiv a_1=1 \pmod{a_{2i-1}}$ and $a_{2i} \mid a_1+\cdots+a_{2i-1}=(k+1)a_{2i-1}$ . Therefore, we in fact have $a_{2i} \mid k+1$ , so
$a_{2i-1}+a_{2i} \leq a_{2i-1}+k+1 \leq ka_{2i-1}+2,$ where the last inequality is equivalent to $(k-1)(a_{2i-1}-1) \geq 0$ . By summing the inductive hypothesis from $1$ to $i-1$ , we find that $ka_{2i-1} \leq 2^i-2$ , so the desired conclusion follows. $\blacksquare$

To finish, note that for our given value of $m$ , we have $a_{2m} \leq 2^m-a_{2m-1} \leq 2^m-1$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

3784 posts

vsamc

#24 h Jul 27, 2024, 4:56 PM • 2 Y

Y by ihatemath123, centslordm

Solution

Z K Y

The post below has been deleted. Click to close.

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

1466 posts

#25 h Aug 17, 2024, 4:24 AM

Y by

Really nice NT sequence problem i would say.
First note that $a_n \mid a_{n+k}-a_k$ so we have $a_n \mid a_{n+1}-1$ so $\gcd(a_n, a_{n+1})=1$ , also note that $a_2 \mid 1+a_2$ so $a_2=1$ and therefore $a_n \mid a_{n+2}-1$ so $\gcd(a_n, a_{n+2})=1$ as well. Now let $S_n=\sum_{i=1}^{n} a_i$ , then we have $a_n \mid S_n$ but also $a_{n+1} \mid S_{n+1}=S_n+a_{n+1}$ so $a_{n+1} \mid S_n$ which means $a_na_{n+1} \mid S_n$ for all positive integers $n$ .
Now i claim by induction that $S_{2n} \le 2^{n+1}-2$ and $a_{2n} \le 2^n-1$ are both true simultaneously, indeed base case $n=1$ is trivial as $S_2=2$ and $a_2=1$ , now suppose it's true for $n=k$ , we will prove it for $n=k+1$ this way:
$a_{2k+2} \mid \frac{S_{2k+1}}{a_{2k+1}}=1+\frac{S_{2k}}{a_{2k+1}} \implies a_{2k+2} \le 1+S_{2k} \le 2^{k+1}-1$ $a_{2k+2}a_{2k+1} \mid S_{2k+1} \implies a_{2k+1}(a_{2k+2}-1) \le S_{2k} \le 2^{k+1}-2 \implies a_{2k+1}+a_{2k+2} \le 2^{k+1} \implies S_{2k+2}=S_{2k}+a_{2k+1}+a_{2k+2} \le 2^{k+1}-2+2^{k+1}=2^{k+2}-2$ Therefore the induction is complete and our claim is true. Now to achieve equality we let $a_{2i+1}=1$ and $a_{2i}=2^i-1$ for all $i \in \mathbb Z_{>0}$ which trivially works, thus we are done :cool:

:cool:

.

This post has been edited 1 time. Last edited by MathLuis, Aug 22, 2024, 7:26 PM

Z K Y

The post below has been deleted. Click to close.

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

SomeonesPenguin

123 posts

SomeonesPenguin

#26 h Aug 19, 2024, 4:03 PM

Y by

Solution

This post has been edited 1 time. Last edited by SomeonesPenguin, Aug 19, 2024, 4:04 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a