number sequence contains every large number

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

number sequence contains every large number

G H J

Reveal topic tags

Number sequence

L

G H BBookmark kLocked kLocked NReply

Source: 2021ChinaTST test3 day1 P2

The post below has been deleted. Click to close.

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

mathematics2003

16 posts

mathematics2003

#1 h Apr 13, 2021, 9:20 AM

Y by

Given distinct positive integer $a_1,a_2,…,a_{2020}$ . For $n \ge 2021$ , $a_n$ is the smallest number different from $a_1,a_2,…,a_{n-1}$ which doesn't divide $a_{n-2020}...a_{n-2}a_{n-1}$ . Proof that every number large enough appears in the sequence.

This post has been edited 2 times. Last edited by mathematics2003, Apr 13, 2021, 1:57 PM

Z K Y

The post below has been deleted. Click to close.

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

442 posts

#2 h Apr 21, 2021, 9:06 AM • 9 Y

Y by Aimingformygoal, Rg230403, enzoP14, mijail, Hoto_Mukai, guptaamitu1, sabkx, Deadline, Phorphyrion

solution with rg230403
This is more of an outline than a proof

Claim: Let $n \in \mathbb{N}$ be sufficiently large, and let $S$ be a set of natural numbers of size $n$ . Then, lcm $(S) > n^{4040}$
This result is pretty intuitive; details left out

Claim: $\frac{a_n}{n}$ is bound by a constant
Proof:
Let us assume that the claim is false for the sake of contradiction.
Call a natural number $t$ good, if $\frac{a_t}t > \frac{a_s}s \forall s<t$ . Pick a sufficiently large good $t$ , such that $\frac{a_t}{t} = r \ge 2$
Let $T = \{1, 2, \dots, a_t \} - \{a_1, a_2, \dots, a_t \}$ . Since $|T| \ge rt - t$ , by our claim, lcm $(T) > ((r-1)t)^{4040} > (rt)^{2020} > a_{t-2020}a_{t-2019}\dots a_{t-1}$ . Since lcm $(T) \nmid a_{t-2020}a_{t-2019}\dots a_{t-1}$ , there was some element of $T$ , which was smaller than $a_t$ , which didn't divide $a_{t-2020}a_{t-2019}\dots a_{t-1}$ . This contradicts the definition of $a_t$ . That element would have been chosen in place of $a_t$ . $\blacksquare$

Now suppose that $\frac{a_n}n$ is bounded by $c$ . Assume for the sake of contradiciton that there is some sufficiently large number $k >> c$ that doesn't appear in the sequence. $k$ has a sufficiently large prime power factor, say $p^\alpha >> c$ . For all $t > k$ , since $k \neq a_t$ , $p^\alpha \mid k \mid a_{t-2020}a_{t-2019}\dots a_{t-1}$ , which means $q = p^{\lceil \frac{\alpha}{2020} \rceil} >> c$ divides one of the terms $a_{t - 2020}, a_{t - 2019}, \dots, a_{t-1}$ . If $a_t$ is divisible by $q$ , call $t$ friendly. Now, for some $n >> k$ , since at least $n$ numbers in $\{1, \dots, k+2020n \}$ , are friendly, one of the numbers $a_1, \dots, a_{k+2020n}$ is at least $qn > kc + 2020cn$ . This contradicts the claim that $\frac{a_n}n$ was bounded by $c$ .

Z K Y

The post below has been deleted. Click to close.

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

luan_shi_yuan_ge

5 posts

luan_shi_yuan_ge

#4 h Oct 8, 2024, 7:00 AM

Y by

p_square wrote:

solution with rg230403
This is more of an outline than a proof

Claim: Let $n \in \mathbb{N}$ be sufficiently large, and let $S$ be a set of natural numbers of size $n$ . Then, lcm $(S) > n^{4040}$
This result is pretty intuitive; details left out

Claim: $\frac{a_n}{n}$ is bound by a constant
Proof:
Let us assume that the claim is false for the sake of contradiction.
Call a natural number $t$ good, if $\frac{a_t}t > \frac{a_s}s \forall s<t$ . Pick a sufficiently large good $t$ , such that $\frac{a_t}{t} = r \ge 2$
Let $T = \{1, 2, \dots, a_t \} - \{a_1, a_2, \dots, a_t \}$ . Since $|T| \ge rt - t$ , by our claim, lcm $(T) > ((r-1)t)^{4040} > (rt)^{2020} > a_{t-2020}a_{t-2019}\dots a_{t-1}$ . Since lcm $(T) \nmid a_{t-2020}a_{t-2019}\dots a_{t-1}$ , there was some element of $T$ , which was smaller than $a_t$ , which didn't divide $a_{t-2020}a_{t-2019}\dots a_{t-1}$ . This contradicts the definition of $a_t$ . That element would have been chosen in place of $a_t$ . $\blacksquare$

Now suppose that $\frac{a_n}n$ is bounded by $c$ . Assume for the sake of contradiciton that there is some sufficiently large number $k >> c$ that doesn't appear in the sequence. $k$ has a sufficiently large prime power factor, say $p^\alpha >> c$ . For all $t > k$ , since $k \neq a_t$ , $p^\alpha \mid k \mid a_{t-2020}a_{t-2019}\dots a_{t-1}$ , which means $q = p^{\lceil \frac{\alpha}{2020} \rceil} >> c$ divides one of the terms $a_{t - 2020}, a_{t - 2019}, \dots, a_{t-1}$ . If $a_t$ is divisible by $q$ , call $t$ friendly. Now, for some $n >> k$ , since at least $n$ numbers in $\{1, \dots, k+2020n \}$ , are friendly, one of the numbers $a_1, \dots, a_{k+2020n}$ is at least $qn > kc + 2020cn$ . This contradicts the claim that $\frac{a_n}n$ was bounded by $c$ .

actually, you have to prove that the prime int. of $k$ is not too big.
By proving that $\frac{a_n}{n}$ is almost less than $1$ ( $1$ plus a function that is smaller than $cn^a$ for some $c$ ( $a>0$ ))you can prove that any int. $p$ is smaller than $2021$

This post has been edited 1 time. Last edited by luan_shi_yuan_ge, Oct 8, 2024, 9:37 AM

Z K Y

The post below has been deleted. Click to close.

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

146 posts

#5 h May 25, 2025, 8:16 PM

Y by

Beautiful Problem :love:

:love:

I'll prove that a number appears in the sequence in it satisfies one of the following:
1) It has a big prime divisor $p$
2) it has a prime divisor $p$ with big exponent. ("bigs" to be defined later)
It is obvious that the set of numbers not satisfying 1 or 2 is finite.

proof of 1): Assume the contrary
claim:every big prime appears in the sequence.
proof:Trivial since if some multiple of $p$ appears, then $p$ should appear.
Observe now that the product $a_{n-2020}...a_{n-2}a_{n-1}$ should remain multiple of $p$ at all times, since otherwise, multiples of $p$ will start to appear.
Motivation
Set $k=2020! +2020$ and notice that $lcm[a_i +1, \dots, a_i + k] > a_{n-2020}...a_{n-2}a_{n-1}$ where $a_i = max{a_{n-2020}...a_{n-2}a_{n-1}}$
So $a_n < a_i + k$ and so the step is bounded. Thus, 2020 steps are also bounded and for big $p$ I can't reach the next multiple of $p$ , contradiction! 1) is proven.
In a similar manner we prove 2):
Take any prime (even 2) and consider a big exponent $k$ . From 1), at least one multiple of $p^k$ appears (times a big prime). So consider the smallest multiple that doesn't appear. Thus, in every 2020 elements, $p^k$ divides $a_{n-2020}...a_{n-2}a_{n-1}$ So for some $i$ , $p^{\frac{k}{2020}}$ divides $a_i$ . But the next multiple of $p^{\frac{k}{2020}}$ is very far away (bounded step due to 1)) and thus it is not reachable in 2020 steps. (take big k). 2) is also proven.
Done!

This post has been edited 2 times. Last edited by sttsmet, May 25, 2025, 8:17 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a