mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-08-20, 12:52   #1
Unregistered
 

22×23×41 Posts
Default What is the significance of prime numbers?

Serious question, I'm just wondering what the big deal is with prime numbers... so they can't be divided.. is there something significant with that?

Also am I correct in the assumption that there is no real formula which can be used to find out all the prime numbers? other than using some math program which simply just attempts to divide the number to figure out if it's prime or not.. and also other than that 2n-1 which only finds primes here and there...... is there a formula out there which will find each and every prime?
  Reply With Quote
Old 2005-08-20, 14:56   #2
lycorn
 
lycorn's Avatar
 
"GIMFS"
Sep 2002
Oeiras, Portugal

11·137 Posts
Default

If there were such formula, the search for Prime Numbers would be meaningless, don´t you think?...
lycorn is offline   Reply With Quote
Old 2005-08-20, 15:14   #3
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

38810 Posts
Default

There is not a formula that will find every prime number, but there is a method. It’s called division. You simply divide your number by every prime lower than it, and if it divides your number is not prime.
The trouble with this approach is that for huge numbers it would take years – even with computers - to prove whether a number is prime or not. Mathematicians have therefore developed a lot of clever techniques for determining whether or not a number MIGHT be prime. They then concentrate their efforts – computer time costs money, after all - on those that might be prime. Numbers of the form (2^n)-1 are called Mersenne numbers, and it can be shown that they MIGHT be prime if, and only if, n is prime. That n is prime does not, however, guarantee that (2^n)-1 will be prime. (2^5)-1 is prime, but (2^11)-1 is not. There are other forms of numbers for which similar rules apply.

As for the usefulness of prime numbers; do you have a mobile phone, or cash point card, or credit card, or have you ever bought anything over the internet? All of these transactions, and many other things you do every day, rely for their security on the simple fact that it is so hard to find prime numbers in a reasonable amount of time. In very simple terms, take any two prime numbers and multiply them together, and you have a security code that can only be broken with those same two original prime numbers. No other combination will work, ever. In part, that is why prime numbers are so useful, so important, and yet so tantalisingly elusive that searching for them would be interesting and satisfying even if they had no use at all.
Numbers is offline   Reply With Quote
Old 2005-08-21, 00:33   #4
99.94
 
99.94's Avatar
 
Dec 2004
The Land of Lost Content

1000100012 Posts
Default

If it is a serious question and if you would like to read further on the subject, try Marcus du Sautoy's book: The Music of the Primes.
99.94 is offline   Reply With Quote
Old 2005-08-21, 00:48   #5
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

154710 Posts
Default

There are plenty of formulas for giving us each and every prime. They are just usually very complicated, and require the computation of all previous primes.

As for the usefulness of prime numbers, one word: cryptography.
Zeta-Flux is offline   Reply With Quote
Old 2005-08-21, 10:05   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

(For the sake of newbies) Regarding an apparent contradiction:

When some folks say there's no formula for finding every prime number, while other folks say there are formulas for every prime number ... they're both right ... sort of.

What's happening is that there are different unstated assumptions in each case. As simple examples, let me offer these slightly-expanded versions:

There's no formula for finding every prime number that requires less work than what we usually think of as the standard nonformulaic methods for finding primes.

There are formulas for computing every prime number but they require that previous primes have already been found and/or offer no overall shortcut in the amount of work required.

Each of those could be stated more rigorously, and there are even more unstated conditions and assumptions that could be added to each. I'll stop here.
cheesehead is offline   Reply With Quote
Old 2005-08-21, 12:27   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Do you mean "formula" or "algorithm" ? They are not the same.
Wacky is offline   Reply With Quote
Old 2005-08-21, 13:08   #8
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default A "formula"?

"If there were such formula, the search for Prime Numbers would be meaningless, don´t you think?... "

NO, I dont think so (and suspect your wink is made knowingly)

As for the suggestion to read "Music of the primes"

More specifically see p199/p200 where there is an explicit formula presented which will generate all primes without missing any at all.

I agree with Wacky that you might also call it an "algorithm" or means for finding primes, as it also generates 0 or negative values which are answers to be ignored. Any positive result is prime.

I quote from du Sautoy:

"But could mathematicians find such a formula? In 1971, Matijasevich devised an explicit method for arriving at such a formula, but he did not follow it through to produce an answer. The first explicit formular to be written out in detail used 26 variables A to Z and was discovered in 1976:"

It is reproduced and I did type it for you but lost the post :-(

However as has been pointed out, to use it would be a lot of work!

So, it may not be of practical use, but I found it interesting to read that such a formula did indeed exist!

As for significance, being prime tells us that a number can't be divided without a remainder. Thus if I had a prime number of (whatever) I could not share them fairly among members of my family or friends (assuming number of people < the prime).

eg if I have 13 footballs, unless there are 1 or 13 people, I will have to start disecting footballs with a knife to share them, and that does tend to ruin them :-)
Peter Nelson is offline   Reply With Quote
Old 2005-08-22, 08:48   #9
lycorn
 
lycorn's Avatar
 
"GIMFS"
Sep 2002
Oeiras, Portugal

11·137 Posts
Default

Quote:
Originally Posted by Unregistered
Also am I correct in the assumption that there is no real formula which can be used to find out all the prime numbers? other than using some math program which simply just attempts to divide the number to figure out if it's prime or not..
The underlined part was the one I was actually answering to. Meaning that if there was a formula (or algorithm) to generate all prime numbers in a comparatively easier way, people wouldn´t be investing time and computer resources in a search activity like GIMPS.
lycorn is offline   Reply With Quote
Old 2005-08-22, 15:23   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts
Default

From the MathWorld page for Formula: "In mathematics, a formula is a fact, rule, or principle that is expressed in terms of mathematical symbols. Examples of formulas include equations, equalities, identities, inequalities, and asymptotic expressions."

What I had in mind when I wrote "formula" was the sort of equation y = f(x) which gives prime values of y for some range of integer values of x. But the originator's question also makes sense when algorithm is substituted for formula.

From the MathWorld page for Algorithm: "A specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. Specific algorithms sometimes also go by the name method, procedure, or technique."

Last fiddled with by cheesehead on 2005-08-22 at 15:24
cheesehead is offline   Reply With Quote
Old 2005-08-22, 16:41   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by cheesehead
From the MathWorld page for Formula: "In mathematics, a formula is a fact, rule, or principle that is expressed in terms of mathematical symbols. Examples of formulas include equations, equalities, identities, inequalities, and asymptotic expressions."

What I had in mind when I wrote "formula" was the sort of equation y = f(x) which gives prime values of y for some range of integer values of x. But the originator's question also makes sense when algorithm is substituted for formula.

From the MathWorld page for Algorithm: "A specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. Specific algorithms sometimes also go by the name method, procedure, or technique."
I have, so far, stayed out of this conversation, because it is generally
lacking in rigor. However, I hope I can clarify and correct some of
the incorrect claims that have been made.

Formulae do exist that will give the n'th prime. However, such formulae
are usually given as summations which require prohibitive calculation.
See, for example, Paulo Ribenboim's "Book of Prime Number Records"

Algorithms do exist for finding the
n'th prime that are much better than finding them all. One applies a
prime *counting* algorithm and then uses binary search.

As for the "algorithm vs. formula" debate, allow me to say that
the difference is often a matter of how much math you know.
Suppose, for example, I state that the answer to some problem is
"y = sin(x)". Most would accept this as a formula because they
*recognize* what sin(x) is, even though to COMPUTE sin(x) requires
an *algorithm*. However, if I said the answer is "y = H(a;b;x)/G(x)"
where H is a hypergeometric function, and G is the gozinta function,
many would not accept this as a "formula" because they do not recognize
the functions. Especially if computing the functions requires a complicated
and expensive algorithm. Both "formula" and "algorithm" are fuzzy
concepts. However, under any reasonable interpretation, expressions
that give the n'th prime as summations involving trig functions and the
(say) factorial function ARE formula.

Furthermore, closed form formulae exist for pi(n), but they are not
elementary; they can be given in terms of contour integrals involving the
zeta function. The most efficient to calculate was given by Odlyzko,
Lagarias et.al. and requires good knowledge of complex function theory.
But the formula itself is simple.

Much of this is hard to explain to newbies because they lack the required
background.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What can you do with 2 prime numbers? VicDiesel Programming 12 2017-04-20 21:16
Prime Numbers Or Not Arxenar Miscellaneous Math 38 2013-06-28 23:26
All odd numbers are prime Citrix Lounge 5 2010-04-05 21:34
Another series of prime numbers ? spkarra Miscellaneous Math 3 2009-12-29 00:23
Prime numbers Unregistered Miscellaneous Math 8 2008-11-09 07:45

All times are UTC. The time now is 21:48.


Sun Nov 28 21:48:38 UTC 2021 up 128 days, 16:17, 0 users, load averages: 1.41, 1.48, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.