3

I saw movie "the man who knew infinity"

In which ramanujan had formulated a formula to calculate number of prime numbers between a range of numbers

My teacher told me that there exist no program which can generate primes

My friend told me that someone had found a counter example of ramanujan'a formula which was billions of billion

So I want to know that did he really formulated the formula, if yes then what is it and how it works (proof required).

super saiyan
  • 344
  • various computer programs can generate prime numbers - some of them very simple. – Cato Dec 22 '16 at 13:23
  • 2
    Your teacher told you that "there exist no program which can generate primes"??? You can tell him or her, pardon my French, that's a bunch of baloney. – barak manos Dec 22 '16 at 13:23
  • As with regards to "number of prime numbers within a given range": You can approximate the number of primes $\in[x,y]$ as $\frac{y}{\ln(y)}-\frac{x}{\ln(x)}$. There are also tighter bounds. Though I'm not familiar with the historical details, I would guess that Ramanujan had conjectured such tighter bound, which was later refuted explicitly with a counterexample (or possibly more interestingly - refuted by proving that a counterexample existed)... – barak manos Dec 22 '16 at 13:27
  • @barakmanos That really big number too' big for me to realistically care about much? :D – Simply Beautiful Art Dec 22 '16 at 13:29
  • @SimpleArt: I understand each word in your comment, but I am unable to connect them into a meaningful statement. Would you mind rephrasing it? – barak manos Dec 22 '16 at 13:35
  • @barakmanos I just meant the number you are referring to is very big. (though not as big as those crazy numbers like Graham's or TREE3) – Simply Beautiful Art Dec 22 '16 at 13:36
  • @SimpleArt: That's why I have mentioned the possibility of refuting by proving that a counterexample exists. Not sure whether or not you've heard of this "concept" before, but some conjectures in Number Theory have been refuted this way. An explicit counterexample was simply too large, but someone has managed to prove that such counterexample exists. If I'm not mistaken, the most famous such case involves a conjecture by Gauss (which possibly even related directly to the minimum and/or maximum bounds of the prime-counting function). – barak manos Dec 22 '16 at 13:52
  • @barakmanos Yes yes, I know. Just commenting on the largeness of the number being almost unreasonable. – Simply Beautiful Art Dec 22 '16 at 13:57
  • @super saiyan: "ramanujan had formulated a formula to calculate number of prime numbers" : complex analysis was a weak point of Ramanujan before meeting Hardy and this was one of his errors. – Raymond Manzoni Dec 22 '16 at 13:57

1 Answers1

2

This probably isn't Ramanujan's method, but its very simple:

Take each number within the given range. Take the square root of the largest number in this range. If a number is prime, it will not be divisible by any numbers smaller than the square root of this largest number.

Now, take out all the numbers divisible by $2$. Then all the numbers divisible by $3$. Then $5,7,\dots,$ all the way till you reach the square root number. The numbers you have left are prime numbers, and this is easily doable with a computer.

If you are interested in approximations though, consider the prime-counting function. One simple approximation to finding the amount of prime numbers between $x$ and $y$:

$$\frac y{\ln y}-\frac x{\ln x}$$

Better bounds exist in the link above.

Simply Beautiful Art
  • 74,685