Skip to main content

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 [1,2]$$

Similarly  there exist $t_2$ such that $$f(3)-f(2)=f'(t_2), t\in [2,3]$$

and so on,  there exist $t_{n-1}$ such that $$f(n)-f(n)=f'(t_{n-1}), t\in [n-1,n]$$

So $f(n)-f(1)$ tends to infinity as $f'$ is increasing and positive.. 

So $f(n)$ is increasing and diverges!

Tonight I will revise O notation and make notes! Hopefully I can survive!

Sunaina 


Comments

Post a Comment

Popular posts from this blog

Just spam combo problems cause why not

This post is mainly for Rohan Bhaiya. He gave me/EGMO contestants a lot and lots of problems. Here are solutions to a very few of them.  To Rohan Bhaiya: I just wrote the sketch/proofs here cause why not :P. I did a few more extra problems so yeah.  I sort of sorted the problems into different sub-areas, but it's just better to try all of them! I did try some more combo problems outside this but I tried them in my tablet and worked there itself. So latexing was tough. Algorithms  "Just find the algorithm" they said and they died.  References:  Algorithms Pset by Abhay Bestrapalli Algorithms by Cody Johnson Problem1: Suppose the positive integer $n$ is odd. First Al writes the numbers $1, 2,\dots, 2n$ on the blackboard. Then he picks any two numbers $a, b$ erases them, and writes, instead, $|a - b|$. Prove that an odd number will remain at the end.  Proof: Well, we go $\mod 2$. Note that $$|a-b|\equiv a+b\mod 2\implies \text{ the final number is }1+2+\dots ...

My experiences at EGMO, IMOTC and PROMYS experience

Yes, I know. This post should have been posted like 2 months ago. Okay okay, sorry. But yeah, I was just waiting for everything to be over and I was lazy. ( sorry ) You know, the transitioning period from high school to college is very weird. I will join CMI( Chennai Mathematical  Institue) for bsc maths and cs degree. And I am very scared. Like very very scared. No, not about making new friends and all. I don't care about that part because I know a decent amount of CMI people already.  What I am scared of is whether I will be able to handle the coursework and get good grades T_T Anyways, here's my EGMO PDC, EGMO, IMOTC and PROMYS experience. Yes, a lot of stuff. My EGMO experience is a lot and I wrote a lot of details, IMOTC and PROMYS is just a few paras. Oh to those, who don't know me or are reading for the first time. I am Sunaina Pati. I was IND2 at EGMO 2023 which was held in Slovenia. I was also invited to the IMOTC or International Mathematical Olympiad Training Cam...

Geometry ( Finally!!!)

 This is just such an unfair blog.  Like if one goes through this blog, one can notice how dominated  Algebra is!! Like 6 out of 9 blog post is Algebra dominated -_- Where as I am not a fan of Algebra, compared to other genres of Olympiad Math(as of now). And this was just injustice for Synthetic Geo. So this time , go geo!!!!!!!!!!!  These problems are randomly from A Beautiful Journey through Olympiad Geometry.  Also perhaps I will post geo after March, because I am studying combi.  Problem:  Let $ABC$ be an acute triangle where $\angle BAC = 60^{\circ}$. Prove that if the Euler’s line of $\triangle ABC$ intersects $AB$ and $AC$ at $D$ and $E$, respectively, then $\triangle ADE$ is equilateral. Solution:  Since $\angle A=60^{\circ}$ , we get $AH=2R\cos A=R=AO$. So $\angle EHA=\angle DOA.$ Also it's well known that $H$ and $O $ isogonal conjugates.$\angle OAD =\angle EAH.$ By $ASA$ congruence, we get $AE=AD.$ Hence $\triangle ADE$ is equilateral....

IMO 2023 P2

IMO 2023 P2 Well, IMO 2023 Day 1 problems are out and I thought of trying the geometry problem which was P2.  Problem: Let $ABC$ be an acute-angled triangle with $AB < AC$. Let $\Omega$ be the circumcircle of $ABC$. Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$. The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$. The line through $D$ parallel to $BC$ meets line $BE$ at $L$. Denote the circumcircle of triangle $BDL$ by $\omega$. Let $\omega$ meet $\Omega$ again at $P \neq B$. Prove that the line tangent to $\omega$ at $P$ meets line $BS$ on the internal angle bisector of $\angle BAC$. Well, here's my proof, but I would rather call this my rough work tbh. There are comments in the end! Proof Define $A'$ as the antipode of $A$. And redefine $P=A'D\cap (ABC)$. Define $L=SP\cap (PDB)$.  Claim1: $L-B-E$ collinear Proof: Note that $$\angle SCA=\angle SCB-\angle ACB=90-A/2-C.$$ So $$\angle SPA=90-A/2-C\implies \ang...

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 did...

Problems I did this week [Jan8-Jan14]

Yeyy!! I am being so consistent with my posts~~ Here are a few problems I did the past week and yeah INMO going to happen soon :) All the best to everyone who is writing!  I wont be trying any new problems and will simply revise stuffs :) Some problems here are hard. Try them yourself and yeah~~Solutions (with sources) are given at the end! Problems discussed in the blog post Problem1: Let $ABC$ be a triangle whose incircle $\omega$ touches sides $BC, CA, AB$ at $D,E,F$ respectively. Let $H$ be the orthocenter of $DEF$ and let altitude $DH$ intersect $\omega$ again at $P$ and $EF$ intersect $BC$ at $L$. Let the circumcircle of $BPC$ intersect $\omega$ again at $X$. Prove that points $L,D,H,X$ are concyclic. Problem 2: Let $ ABCD$ be a convex quadrangle, $ P$ the intersection of lines $ AB$ and $ CD$, $ Q$ the intersection of lines $ AD$ and $ BC$ and $ O$ the intersection of diagonals $ AC$ and $ BD$. Show that if $ \angle POQ= 90^\circ$ then $ PO$ is the bisector of $ \angle AOD$ ...

Some random problems

  I know, I know. Different font indeed. I have deleted a few of my MSE answers. I felt they weren't that good in quality. And a few questions are from my prev aops account which I have deactivated now. I also have posted 10 IOQM types of problems. These can be used while preparing for IOQM. Problem: Prove that $\dfrac{ab}{c^3}+\dfrac{bc}{a^3}+\dfrac{ca}{b^3}> \dfrac{1}{a}+\dfrac{1}{b}+\dfrac{1}{c}$, where $a,b,c$  are different positive real numbers.  Proof: Note that by AM-GM $$\frac{ab}{c^3}+\frac{bc}{a^3}\ge \frac{2b}{ac}$$ and we also have $$\frac {b}{ac}+\frac{c}{ab}\ge \frac{2}{a}$$. Hence, $$\sum_{cyc}\frac{ab}{c^3}\ge\sum_{cyc}\frac{b}{ac}\ge\sum_{cyc}\frac{1}{a}$$ where everything we got is by applying AM-GM on $2$ terms and then dividing by $2$. USA TST 2007: Triangle $ABC$ which is inscribed in circle $\omega$. The tangent lines to $\omega$ at $B$ and $C$ meet at $T$. Point $S$ lies on ray $BC$ such that $AS$ is perpendicular to $AT$. Points $B_1$ and $C_1...

IOQM Results declared and INMO predictions :-

So IOQM results got declared, and I got selected through regional quota, I was getting 32. So yeah..since I am from Assam, we had regional top 30 cutoff as 15, and girls quota 8. Kind of happy since I got selected, but had I been a bit more concentrated and think less complicated and made less silly mistakes, I think I would have been scored  nicer marks. Also sad because people who deserved more than me couldn't get through because they lived at a competitive state.😔 So for INMO, I am scared as hell, this would be my 3rd attempt, though this year I am way more serious than last 2 years. But this year would be my last year, then I will take JEE/KVPY. So I want to end everything with a happy note 😃  though it seems almost impossible. JiB calculated that nearly 1200 students will give INMO, and only 30 seats 😂.  May the person who deserves to clear INMO, clear INMO. Also I won't be sad if I don't qualify 😂, it just implies there way more hardworking students, and that...

Orders and Primitive roots

 Theory  We know what Fermat's little theorem states. If $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as \[a^{p}\equiv a{\pmod {p}}.\] So, essentially, for every $(a,m)=1$, ${a}^{\phi (m)}\equiv 1 \pmod {m}$. But $\phi (m)$ isn't necessarily the smallest exponent. For example, we know $4^{12}\equiv 1\mod 13$ but so is $4^6$. So, we care about the "smallest" exponent $d$ such that $a^d\equiv 1\mod m$ given $(a,m)=1$.  Orders Given a prime $p$, the order of an integer $a$ modulo $p$, $p\nmid a$, is the smallest positive integer $d$, such that $a^d \equiv 1 \pmod p$. This is denoted $\text{ord}_p(a) = d$. If $p$ is a primes and $p\nmid a$, let $d$ be order of $a$ mod $p$. Then $a^n\equiv 1\pmod p\implies d|n$. Let $n=pd+r, r\ll d$. Which implies $a^r\equiv 1\pmod p.$ But $d$ is the smallest natural number. So $r=0$. So $d|n$. Show that $n$ divid...

New year with a new beginning! And a recap of 2024..and all the best for INMO 2025!

Hi everyone! Happy New Year :)  Thank you so much for 95k+ views!!! How was everyone's 2024? What are everyone's resolutions? ( Do write down in the comment section! And you can come back 1 year later to see if you made them possible!). A Better Mathematician  Well, technically a theoretical computer scientist.  I am so grateful to be allowed to study at CMI where I can interact with so many brilliant professors, access the beautiful library and obviously discuss mathematics ( sometimes non math too ) with the students.    And this year, I want to learn more mathematics and clear my fundamentals. I have become much worse in math actually. And hopefully, read some research papers too :)  And discuss a lot of mathematics with other people.  However, with that whole depressing 2024 year, I have lost a lot of my confidence in mathematics. And to be a better mathematician, I should gain the confidence that I can be a mathematician. And well, I am working on...