Hacker News Reader

Comment by iamcreasy | Hacker News Reader

How about the prime number problem. It's simple enough to understand.

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. There are infinitely many primes, as demonstrated by Euclid around 300 BC. There is no known simple formula that separates prime numbers from composite numbers."

View on HN

There are many such formulas, such as Willan's 1964 simple formula for the nth prime. But they are basically all hiding a sieve, Wilson's theorem, the prime count function, or some other calculation. That is, none of them are at all practical, and most offer no insight.

I'd recommend perusing "Formulas for Primes" by Underwood Dudley, 1983. Free online link: http://www.maa.org/programs/faculty-and-departments/classroo...

Finding primes is a P problem though, so I'd consider it a "solved problem". There's no equation that generates nothing but primes, is that what you meant?

Yes, kind of.

Where are you quoting this from? It's ill-defined / ambiguous as you're stating it. I'm a professional number theorist and I don't understand what your question is actually asking. Thanks!

https://en.wikipedia.org/wiki/Prime_number please improve the article :-)

I quoted it from Wikipedia. The problem is the last line. There is no known simple formula to identify prime numbers.

Could you provide more clarification on what's wrong?

What is a "simple formula"? I have no idea what "simple formula" means. In math reseacrch everything must be 100% precise and well defined.

I think they mean something a great deal faster than just dividing by each number to check.

AKS is a primality check in polynomial time, IE much faster than trial division. It's not "simple" for certain values of simple, but it's only 5 major steps.

You are correct, but I wrote it in context of the posted article.

I think they meant there's no equation that generates nothing but primes.

Reply on news.ycombinator.com