Define a sequence ${{a_n}}_{n\ge1}$ such that $a_1=1$ , $a_2=2$ and $a_{n+1}$ is the smallest positive integer $m$ such that $m$ hasn't yet occurred in the sequence and also $gcd(m,a_n)\neq{1}$. Show that all positive integers occur in the sequence.
Problem
Source: Azerbaijan Math Olympiad Training
Tags: number theory, TST
USJL
05.09.2020 04:31
Here is a more combinatorial way that I'd like to think this problem in. Imagine we have a bucket for each prime $p$, and in the bucket for $p$, we have all multiples of $p$ arranged increasingly from the top to the bottom. Each time when we want to compute the next term, we do the following. We look at which buckets the last term belongs to, remove the last term from all those buckets, and the next term is the smallest number among the numbers at the top of those buckets. We repeatedly do this procedure. With this in mind, we can prove the following. Lemma 1. It suffices to show that any number in the bucket for $2$ appears in the sequence.
If any number in the bucket for $2$ appears, then for any $m\in\mathbb{N}$, we know that we can find $i_1<i_2<\ldots<i_m$ such that $m|a_{i_j}$ for all $1\leq j\leq m$. If none of $a_{i_1},\ldots,a_{i_m}$ is equal to $m$, then by definition, they are all smaller than $m$. This is a contradiction to the assumption that they are distinct.
Lemma 2. If some number in the bucket for $2$ does not appear, then only finitely many even numbers appear.
The proof proceeds similarly as Lemma 1. If infinitely many even numbers appear, then for any even number $2k$ we can find $i_1<\ldots<i_{2k}$ such that $2|a_{i_j}$ for all $1\leq j\leq 2k$. Then with the same argument we can deduce that there exists $1\leq j\leq 2k$ such that $a_{i_j}=2k$. This is a contradiction with the assumption.
Lemma 3. If there are only finitely many even numbers, then $a_n<a_{n+1}$ for finitely many positive integers.
Let $N$ be a positive integer so that $a_{N+1},a_{N+2},\ldots$ are all odd. For each $n\in\mathbb{N}$, let $p(n)$ be the label for the bucket we take $a_{n+1}$ from (note that there might be a tie among the buckets, in which case we choose the bucket with the smallest label). Then we know that $p(n)\geq 3$ for all $n\geq N$. Now if $n> N$ satisfies that $a_n<a_{n+1}$, then we know that $a_{n+1}=p(n)(a_n/p(n)+k)$ for some positive integer $k$. Since both $a_n$ and $a_{n+1}$ are odd, we know that $k\geq 2$. This shows that there is some $i\leq N$ such that $a_i=p(n)(a_n/p(n)+1)=a_n+p(n)$. Therefore, if $S$ is the set of $n>N$ with $a_n<a_{n+1}$, then we can construct a well-defined map $f:S\to [N]$ so that $a_{f(n)}=a_n+p(n)$.
For each $i\in [N]$, we know that if $f(n)=i$ then $a_i=a_n+p(n)$. This shows that $p(n)|a_i$, and so that if $a_i$ has $k$ different prime factors, then there are at most $k$ elements in $S$ that are sent to $i$ by $f$. In particular, any element in $[N]$ is hit by $f$ only finitely many times, which shows that $S$ is a finite set.
Now by Lemma 2. and Lemma 3., we know that if some multiple of $2$ does not appear, then the sequence $a_1,a_2,\ldots$ can only go up for finitely many times. This is a contradiction with that it is an infinite sequence of positive integers. Therefore all multiples of $2$ appear, and by Lemma 1., we are done.
Taha1381
30.10.2020 22:38
This follows by https://artofproblemsolving.com/community/c6h364147p2000378
Iora
04.12.2022 20:45
I claim at at some moment, some variable $a_i$ is divisible by prime $p$, and this is possible infinitely many times. Observe that this solves the problem, hence it is enough to prove our claim. Claim 1. Any prime $p$ can divide by at least one integer $a_i$. This is actually pretty logical, FTSOC, assume that there is some $p$ that none of the integers in sequence are divided by. Then smallest integer that is divisible by $p$ is $p$ itself. If at some point we have arbitrarly bigger $a_j= p_1^{b_1} \cdot p_2^{b_2} \cdot ... \cdot p_k^{b_3}$, such that $p<p_1<p_2<...<p_k$ then we can choose $a_{j+1}= p \cdot p_1$ since it is the smallest possible integer, hence contradiction. $\square$ Note that this also proves all primes occurs in sequence, which is obvious why. Claim 2. Any prime $p$ can divide by infinitely many integers $a_i....a_j$. FTSOC, assume otherwise. Let $p$ be a prime such that it can divide finitely many integers in our sequence. Let the biggest such integer be $a_i$ and let $a_i= p \cdot p_1 \cdot p_2 \cdot ... \cdot p_k$. After arbitrarly bigger time, we will have arbitrarly bigger variable $a_j= q_1 \cdot q_2 \cdot ... \cdot q_m$ then our next smallest integer would be $p \cdot \prod q_i$ where $\prod q_i$ is product of some chosen primes from $a_j$, hence contradiction. $\square$. Note that the product will the minimum possible since by Claim 1. These claims and size reasons are enough to show that any primes occur in the sequence and indeed any product of primes occur in the sequence, hence we are done Remark: IMO this question is very logical and hence my solution is not very rigorous but it has the same ideas as the other solutions so I guess my solution is ok.