# Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers?

Our algebra teacher usually gives us a paper of $20-30$ questions for our homework. But each week, he tells us to do all the questions which their number is on a specific form.

For example, last week it was all the questions on the form of $3k+2$ and the week before that it was $3k+1$. I asked my teacher why he always uses the linear form of numbers... Instead of answering, he told me to determine which form of numbers of the new paper should we solve this week.

I wanted to be a little creative, so I used the prime numbers and I told everyone to do numbers on the form of $\lfloor \sqrt{p} \rfloor$ where $p$ is a prime number. At that time, I couldn't understand the smile on our teacher's face.

Everything was O.K., until I decided to do the homework. Then I realized I had made a huge mistake.$\lfloor \sqrt{p} \rfloor$ generated all of the questions of our paper and my classmates wanted to kill me. I went to my teacher to ask him to change the form, but he said he will only do it if I could solve this:

Prove that $\lfloor \sqrt{p} \rfloor$ generates all natural numbers.

What I tried: Suppose there is a $k$ for which there is no prime number $p$ that $\lfloor \sqrt{p} \rfloor=k$. From this we can say there exists two consecutive perfect squares so that there is no prime number between them. So if we prove that for every $x$ there exists a prime number between $x^2$ and $x^2+2x+1$ we are done.

I tried using Bertrand's postulate but it didn't work.

I would appreciate any help from here :)

• +1 for amusing background. Also, you can use \lfloor and \rfloor for the floor function $\lfloor x \rfloor$. Dec 13 '13 at 8:10
• I think it's still a conjecture wether there always is a prime between two consecutive squares. Dec 13 '13 at 8:11
• Thank you, i used them in my question.
– CODE
Dec 13 '13 at 8:12
• Gaps between consecutive primes are unbounded, but I don't know if this is enough to guarantee there is none between consecutive squares. Dec 13 '13 at 8:14
• Really nice story! +1 Jun 20 '14 at 9:44

If we prove that for every x there exists a prime number between $x^2$ and $x^2+2x+1$, we are done.

This is Legendre's conjecture, which remains unsolved. Hence the big smile on your teacher's face.

• Out of curiosity, I remember about a year ago (or perhaps two) that some mathematician had been able to prove that there was in minimum gap in between two primes but I can't find it on internet. Any idea what it was? Apr 27 '14 at 21:35
• @user88595: Was it Yitang Zhang ? Apr 28 '14 at 1:11
• @Lucian : yes that's it cheers Apr 28 '14 at 7:08
• @CODE Now you just need to prove the legendre's conjecture and you're done! It's not the first time this has happened :-P en.wikipedia.org/wiki/George_Dantzig#Mathematical_statistics
– Ant
Jun 6 '14 at 12:59
• @Ant Thanks for reminding me of Dantzig's story Nov 22 '16 at 13:44

Any of the accepted conjectures on sieves and random-like behavior of primes would predict that the chance of finding counterexamples to the conjecture in $(x^2, (x+1)^2)$ decrease rapidly with $x$, since they correspond to random events that are (up to logarithmic factors) $x$ standard deviations from the mean, and probabilities of those are suppressed very rapidly. This makes the computational evidence for the conjecture more reliable than just the fact of checking up to the millions and billions.