Skip to main content

Posts

Problem solving in NT ( day 4 Week 1)

Such a cute problem, although again, swapping the sum is hard.. I should practice more in that area :( Solved with Sidharth and Malay! Problem[2021 China TST 3/2/4] Prove that $$ \sum_{m=1}^n5^{\omega (m)} \le \sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2  \le \sum_{m=1}^n5^{\Omega (m)} .$$ Proof: Note that the middle term can be manipulated and written as $$\sum_{k=1}^n\lfloor \frac{n}{k} \rfloor \tau (k)^2= \sum_{k=1}^{n}\sum_{dk\le n}1 \tau(k)^2=\sum_{m=1}^n\sum_{k|m}\tau(k)^2$$ Since $\tau (k)$ is multiplicative, we get that $\tau(k)^2$ is multiplicative. Hence $F(m)= \sum_{k|a}\tau(k)^2$ is multiplicative too. ( As it's $1* \tau(k)^2$) Now, we begin our claim which proves the problem. Claim: $5^{\omega(a)}\le \sum_{k|a}\tau(k)^2\le 5^{\Omega(a)}$ Proof: Note that these symbols are multiplicative, we just have to check for primes. For primes $p^b$, $$5^{\omega(p^b)}\le \sum_{k|p^b}\tau(k)^2\le 5^{\Omega(p^b)}$$ Or showing $$5 \le \frac{(b+1)(b+2)(2b+3)}{6} \le 5^b$$ which
Recent posts

Big 'O' notation

Yeyy finally! I got time! I am so happy that I am finally going to read the analytic theory! However, I have added some CS stuff. Not sure if they are accurate. I have taken up CS in school so hopefully, it's correct!  Big $O$ notation:  We say $f(x)=O(g(x))$ if there exists $c$ such that $|f(x)|< c(g(x)$ for all $x\ge x_0$. Arithmetic of Big $O$ notation: $O(f(x))+O(g(x))= O(f(x)+g(x))$. Moreover, if $f(x)=O(g(x))\implies O(f(x)+g(x))=O(g(x)) $ $O(f(x))\times O(g(x))= O(f(x)\cdot g(x))$ $O(f(x)) - O(g(x))= O(f(x) +g(x))$ ( Yes, it is "+") $O(\int f(x) dx)=\int O(f(x) dx$ I want to dive into the CS part; it looks pretty nice and attractive :p. Introduction In CS, it is important to measure the efficiency of the algorithm before applying it on a big size of data. The "performance" depends on internal and external factors. Internal factors ( which we care more) specify the algorithm's efficiency in terms of: Time required to run and Space required to run.

Problem solving in NT ( day 3 Week 1)

 OMG Prime number theorem!!! I actually loved it! So today I solved a quite fancy NT problem with other people's help though! Problem : Prove that there exists an interval of the $[n^2,(n+1)^2]$ which contains at least $1000$ primes. Proof 1 : By PNT, if $n$ is large enough $$\pi(n) ~ \frac{n}{\log(n)}$$ So $$f(n)=\pi( {n+1}^2)-\pi( n^2) = \frac{(n+1)^2}{\log({n+1}^2)}- \frac{n^2}{\log(n^2)}$$ $$= \frac{(n+1)^2}{2\log({n+1})}- \frac{n^2}{2\log(n)}$$ Then $$f'(n)= \frac{(2n+2)\log(n+1)-(n+1)}{2[\log(n+1)]^2}-\frac{2n\log(n)-n}{2[\log(n)]^2}$$ $$=\frac{n+1}{\log(n+1)}+\frac{n}{2[\log(n)]^2}- (\frac{n}{\log(n)}+\frac{n+1}{2[\log(n+1)]^2})$$ Take  $$h(x)= \frac{(x)}{\log(x)}, g(x)=\frac{x}{2\log^2(x)}$$ we have basically $$(h(n+1)-h(n))>>>( g(n+1)-g(n)) $$ since $h$ grows faster than $g$ we have  $$h(n+1)-h(n) > (g(n+1)-g(n)$$ for large enough $n$. Infact $f'(n)$ is strictly increasing. Now, by MVT, note that there exist $t_1$ such that $$f(2)-f(1)=f'(t_1), t\in

Problem solving in NT (day 2 week 1)

 Well, I am finally free! It's more like I was busy with classes and covering up the NT4 course, dang it is hard! Finally got hand of convolutions etc! ISL 2002 N3 : Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors. Proof : Now consider $d\mid p_1p_2\ldots p_n$ and $d'\mid p_1p_2\ldots p_n$. Note that there is a prime $p|2^d+1|2^{p_1p_2\cdots p_n}+1$ and $p\nmid 2^{d'}+1$ by zsig for any $d, d'$. Hence there are any $2^n$ distinct such $p$ ( as there are $2^n$ prime factors of $p_1p_2\cdots p_n$). Since there are atleast $2^n$ distinct primes dividing $p_1p_2\cdots p_n \implies $ there are at least $2^{2^n}$ primes factors which is $>>4^n$. The exceptional case doesn't matter here.  [ISL 2000 N4] :Find all triplets of positive integers $ (a,m,n)$ such that $ a^m + 1 \mid (a + 1)^n$ Proof : Except for the exception of the Zsigmondy theorem, there exists $p$ such that $p|a^m+1$ and $p\nm

Problem Solving in NT (Day 1 of Week 1)

Just did two problems, and both were hard! So I think one can excuse me for not solving more, but it's true. I did give less time. I am trying to reduce the amount of time I "waste". I did spend a good amount of time learning the theory, so yey! Excited for today's link episode!!  [Romania TST 7 2009, Problem 3] Show that there are infinitely many pairs of prime numbers $(p,q)$ such that $p\mid 2^{q-1}-1$ and $q\mid 2^{p-1}-1$. Proof: We begin with the lemma,  Lemma: Let $p\mid 2^{2^n}+1$ then $p\equiv 1\pmod  2^{n+2}$ Proof: Note that ord$_p(2)=2^{n+1}$ $$\implies 2^{n+1}|p\implies p\equiv 1\pmod 2^{n+1}\implies p\equiv 1\pmod 8$$ $$\implies 2^{\frac{p-1}{2}}\equiv 1\pmod p\implies 2^{n+1}\mid \frac{p-1}{2}$$ So consider any prime $p$ dividing $2^{2^{n}}+1$ and $q$ to be prime factor of $2^{2^{n+1}}+1$. Then we get that $p\equiv 1 \pmod 2^{n+2}$ and we get that $q\equiv 1\pmod 2^{n+3}$. Note that $$p\mid 2^{n+1}-1\mid 2^{n+3}-1 \mid 2^{q-1}-1$$ Moreover, $$q\mid 2

Announcing the Unofficial TC 2022! ( Month 1 problem solving )

So it's been 1 month since the INMO results were out! So here's my past 1 month's journey into problem-solving.  There hasn't been much in my life, although the Sharygin correspondence round results came out! And I qualified for the final round. I just made the cutoff though. I got 85 marks and the (unofficial) cutoff was 84 marks. I am one of the seven students selected for the final round and the only kid from India in my grade! They, however, are not inviting Indian students in the final round and have asked us to conduct the final round in India if an organization agrees. Monthly reflection: Till May 16, I tried the Awesome Math Application ( which I got accepted into woohoo! And I am taking courses in the second and third season hehe) Then I was completing 108 algebra problems along with MBL problems till June 1 June 1- June 10: Since I was feeling very guilty for not doing enough problems from the Sophie psets, I did a few Sophie psets problems. BTW Thankyou so mu

Solving Random ISLs And Sharygin Solutions! And INMO happened!!

Some of the ISLs I did before INMO :P  [2005 G3]:  Let $ABCD$ be a parallelogram. A variable line $g$ through the vertex $A$ intersects the rays $BC$ and $DC$ at the points $X$ and $Y$, respectively. Let $K$ and $L$ be the $A$-excenters of the triangles $ABX$ and $ADY$. Show that the angle $\measuredangle KCL$ is independent of the line $g$ Solution: Note that $$\Delta LDK \sim \Delta XBK$$ and $$\Delta ADY\sim \Delta XCY.$$ So we have $$\frac{BK}{DY}=\frac{XK}{LY}$$ and $$\frac{DY}{CY}=\frac{AD}{XC}=\frac{AY}{XY}.$$ Hence $$\frac{BK}{CY}=\frac{AD}{XC}\times \frac{XK}{LY}\implies \frac{BK}{BC}=\frac{CY}{XC}\times \frac{XK}{LY}=\frac{AB}{BC}\times \frac{XK}{LY} $$ $$\frac{AB}{LY}\times \frac{XK}{BK}=\frac{AB}{LY}\times \frac{LY}{DY}=\frac{AB}{DL}$$ $$\implies \Delta CBK\sim \Delta LDK$$ And we are done. We get that $$\angle KCL=360-(\angle ACB+\angle DKC+\angle BCK)=\angle DAB/2 +180-\angle DAB=180-\angle DAB/2$$ Motivation: I took a hint on this. I had other angles but I didn't r

Reflecting on past

INMO Scores are out!! I am now a two times INMO awardee :) I got 16|0|1, so 17 in total! Yes, 16 in P1 T_T. I was thinking I would lose marks because of the way I wrote.  Lemme tell ya'll what happened that day but first I should share a few thoughts I had before the exam. My thoughts Honestly, my preparation for INMO was bad. In fact, I should say I didn't work hard at all. As I have said earlier, I had lost all my hopes for INMO and Olympiads as a whole after EGMO TSTs happened.  Art by Jelena Janic EGMO TSTs i.e European Girl's Mathematical Olympiad Team selection Tests 2022.  Literally my thoughts after EGMO TSTs I feel very ashamed to share but I got 1 mark in my EGMO TSTs. Tests in which I literally gave my whole life. I did so many ISLs ( like SO MANY), I mocked EGMO 2021 TST where my score was 28/42 and I perfected Day 2. 1 mark in the TST just showed my true potential. There are way better people than me in olys. A friend even said to me, "If I wouldn't