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.
Problem
Source: 2021ChinaTST test3 day1 P2
Tags: number theory, Number sequence, Divisibility
21.04.2021 12:06
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$.
08.10.2024 10:00
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$