The sequence of positive integers $a_1,a_2,a_3,\dots$ is brazilian if $a_1=1$ and $a_n$ is the least integer greater than $a_{n-1}$ and $a_n$ is coprime with at least half elements of the set $\{a_1,a_2,\dots, a_{n-1}\}$. Is there any odd number which does not belong to the brazilian sequence?
Problem
Source: Brazil EGMO TST 2023 #4
Tags: number theory
GuvercinciHoca
11.11.2022 17:07
The answer is no.
Assume contrary. Let the first odd number which does not belong to sequence be $2l-1$ and let $a_k$ be the last term which is less than $2l-1$.We are going to construct the sequence $S=\{a_1,a_2,\dots, a_{k}\}$ by using the following claims,
Claim.1: $2n\in S$ iff $4n\in S$ for $4n\leq a_k$
Proof: We are going to use induction on $n$. Base case is $n=1$ which is trivial by considering first few terms of the sequence.
Assume above claim is true for $1,2,...,n-1$.
Then let $a_r=2n-1$ and $a_{r+t}=4n-1$
If $a_{r+1}=2n$, the number of elements that are less than $2n$ and coprime with it be $m$. If an odd number $a$ is coprime with $2n$ it also must be coprime with $4n$ infact $a+2n$ must be coprime with $4n$ too.
On the other hand an even number $a\in \{a_1,a_2,...,a_r\}$ iff $2a\in \{a_{r+1},...,a_{r+t}\}$ because of the induction hipothesis.
Thus the number of elements of $S$ that are coprime with $4n$ and less than $4n$ must be $2m$ and $t\leq r$ which finishes the induction.
Claim.2: Only numbers that are less than $2l-1$ and do not belong to $S$ are $3.2^x$ and $9.2^y$.
Proof: First notice that we only need to look at the numbers of the form $2.m$ where $m$ is an odd number. Let $a_i=2m-1$ and $a_{i+1}=2m+1$.
Because of the above claims, we have
$$
1+m+[log_2{m}]\geq i > 2\cdot \varphi(m) \geq 2\cdot m\cdot \frac{2}{3}
$$Which implies
$$
2^{m-3}<m^3 \implies m\leq 13
$$And it can be checked that $(a_2,a_9,a_{12},a_{19},a_{22})=(2,10,14,22,26)$ so the claim is true.
Now the rest is just calculation.
If $3$ does not divide $2l-1$,
$$
2l-1- \varphi(2l-1)> \varphi(2l-1) - [log_2(\frac{2l-1}{3})] -[log_2(\frac{2l-1}{9})]
$$$$
2l-1 + [log_2(\frac{2l-1}{3})] +[log_2(\frac{2l-1}{9})] > 2\cdot \varphi(2l-1)\geq \frac{8(2l-1)}{5}
$$$$
\frac{2l-1}{3} \cdot \frac{2l-1}{9} > 2^{\frac{3(2l-1)}{5}} \implies 2l-1<5
$$contradiction
If $3$ divides $2l-1$,
$$
2l-1- \varphi(2l-1)> \varphi(2l-1) + [log_2(\frac{2l-1}{3})] +[log_2(\frac{2l-1}{9})]
$$Which is more strict inequality thus gonna give us contradiction again.
So our assumption was wrong.
$\square$
jrsbr
13.11.2022 04:10
I am the creator of this problem and actually there are infinitely many odd numbers that do not belong to the sequence. We prove the following lemma: $\textbf{Lemma:}$ Let $\varphi(n)$ be the number of positive integers less than $n$ coprime with $n$. Then, $$\liminf_{n\to\infty}\frac{\varphi(n)}{n}=0,$$or in other words, for all $\epsilon>0$, there exists a positive integer $n$ such that $\frac{\varphi(n)}{n}<\epsilon$. $\textbf{Proof:}$ We can prove using the tangent-line trick that $e^x\geq 1+x$, for $x\in\mathbb{R}$. Now, let $n=p_1p_2\dots p_k$ be the product of $k$ odd primes. Then $$\frac{\varphi(n)}{n}=\prod_{1\leq i\leq k}\frac{p_i-1}{p_i}$$$$\implies\ln\left(\frac{\varphi(n)}{n}\right)=\sum_{1\leq i\leq k}\ln\left(\frac{p_i-1}{p_i}\right)\leq-\sum_{1\leq i\leq k}\frac{1}{p_i},$$and by taking $k\to\infty$, since the harmonic sum of the primes diverges, we get $$\ln\left(\frac{\varphi(n)}{n}\right)\to-\infty\implies\frac{\varphi(n)}{n}\to0,$$as we wanted. $\square$ Now suppose that there are no odd numbers that do not belong to the sequence. Now take an odd integer $n$ such that $$\varphi(n)<\frac{n}{4}.$$See that if all odd numbers smaller than $n$ are in the sequence, then there are $m\geq\frac{n}{2}$ integers before $n$ in the sequence. But if $n$ appears in the sequence, at least $\frac{m}{2}\geq\frac{n}{4}$ integers in the sequence are coprime with $n$, which is a contradiction since there are at less than $\frac{n}{4}$ integers less than $n$ that are coprime with $n$. Thus our hypothesis that all odd numbers appear in the sequence is wrong and we conclude that there are, indeed, odd numbers not belonging to the sequence. We can easily repeat the same argument supposing that only a finite number of odd numbers do not appear in the sequence and arrive at the same contradiction, thus proving that there are an infinite number of odd integers not in the sequence. $\blacksquare$ $\textbf{Ps:}$ Me and the other proposer of this problem checked and the first odd that isn't in the sequence is $15015$