Eratosthenes Sieve
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Let $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $f(n)$ is the smallest composite number that is not divisable by the first $n$ prime numbers. Prove that $f(n)$ is a perfect square for all $n\in\mathbb{N}$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Eratosthenes Sieve
Is $f(n)$ not divisible by any of the first n prime numbers or all of them? I guess any of them.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré
-Henri Poincaré
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Eratosthenes Sieve
Not divisable by all of the first $n$ primes.Mehrab4226 wrote: ↑Tue Dec 22, 2020 12:26 amIs $f(n)$ not divisible by any of the first n prime numbers or all of them? I guess any of them.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Eratosthenes Sieve
Ans:
proof that I am a bad solution writer:
Solution:
Solution:
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré
-Henri Poincaré
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Eratosthenes Sieve
Nice, you won!
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Eratosthenes Sieve
Yeah, but I couldn't explain it that well in my solution. Your's one in the USAMO was exceptional because it actually simplified things and did the proof.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré
-Henri Poincaré
Re: Eratosthenes Sieve
Didn't understand the last part! Explain please.
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Eratosthenes Sieve
I know I am really bad at solution writing especially when they are number theory and combinatorics. I get what the solution is but cannot turn them into words .
Okay let me take a different approach,
Okay let me take a different approach,
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré
-Henri Poincaré
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: Eratosthenes Sieve
We can have a simplier argument, let's assume $f(n)<p_{n+1}^2$. Which implies $\sqrt{f(n)}<p_{n+1}$. It is well known that every composite number $a$ has a divisor $d$ such that $1<d\leq\sqrt{a}$. So, this means $f(n)$ has a divisor $d$ less than $p_{n+1}$ and greater than $1$, but this means $d$ has a prime divisor which is less than $p_{n+1}$, which is not permitted. so this is a contradiction!
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: Eratosthenes Sieve
This is way easier than mine.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré
-Henri Poincaré