Welcome to
Science a GoGo's
Discussion Forums
Please keep your postings on-topic or they will be moved to a galaxy far, far away.
Your use of this forum indicates your agreement to our terms of use.
So that we remain spam-free, please note that all posts by new users are moderated.


The Forums
General Science Talk        Not-Quite-Science        Climate Change Discussion        Physics Forum        Science Fiction

Who's Online Now
0 members (), 181 guests, and 2 robots.
Key: Admin, Global Mod, Mod
Latest Posts
Top Posters(30 Days)
Previous Thread
Next Thread
Print Thread
#4413 11/09/05 09:47 AM
Joined: Oct 2005
Posts: 560
R
RM Offline OP
Superstar
OP Offline
Superstar
R
Joined: Oct 2005
Posts: 560
Who here thinks that humans will never uncover the formula for prime numbers?

.
#4414 11/09/05 10:04 AM
A
Anonymous
Unregistered
Anonymous
Unregistered
A
dont you know?
Prime is a value not equal to product of Primes other than 1.

#4415 11/09/05 11:18 AM
Joined: Oct 2005
Posts: 560
R
RM Offline OP
Superstar
OP Offline
Superstar
R
Joined: Oct 2005
Posts: 560
what I meant was a formula to see if ANY number was prime, without dividing it by every number half-way before it.

#4416 11/09/05 12:05 PM
A
Anonymous
Unregistered
Anonymous
Unregistered
A
There is formula in Quantum Mechanics...

#4417 11/09/05 01:18 PM
Joined: Oct 2005
Posts: 560
R
RM Offline OP
Superstar
OP Offline
Superstar
R
Joined: Oct 2005
Posts: 560
sure there is

#4418 11/09/05 03:14 PM
Joined: Jan 2005
Posts: 375
C
Senior Member
Offline
Senior Member
C
Joined: Jan 2005
Posts: 375
What you want is a function f(n) such that f(n) = 1 if n is prime and zero otherwise. The prescription to try to divide n by all integers up to n^1/2 will do but you want a function that can be calculated faster. There are algorithms that allow you to calculate f(n) in Log(n) steps.

The idea is to use Fermat's theorem. For a fixed integer n, define X Mod n as the remainder you get when you divide X by n. So, e.g. 21 Mod 10 = 1 and 27 Mod 11 = 5. Calculations Mod n satisfy these properties which allow to quickly calculate results for large numbers:

X^r Mod n = (X Mod n )^r

A B Mod n = (A Mod n) (B Mod n)


So, e.g. to calculate 365 Mod 7 start from
10 Mod = 3 . Thus 100 Mod 7 = 3^2 Mod 7 = 2. And 365 Mod 7 = (3*2 + (-1)*3 + 5) Mod 7 = 1.
9 October 2006 will thus be a thursday!

Fermat's theorem gives a necessary condition for n if n is a prime. Consider the sequence of numbers 1, 2, 3, ...,n-1. Multiply these by some integer x smaller than n and take Mod n. Then you obtain the sequence:

x, 2x Mod n,...(n-1) x Mod n.

If n is a prime then there is no way any two different entries in the second sequence can be equal. If the r*-th and the s-th entry are equal then that would mean that (r - s)x is a multiple of n. Because r and s are both smaller than n and x is smaller than n, this is imposible because n is prime. You can't multiply smaller integers than a prime to obtain a multiple of that prime.

Because no two entries of the sequence:

x, 2x Mod n,...(n-1) x Mod n.

are the same and because there are in total n-1 entries all smaller or equal than n, this sequence is just a the original sequence 1, 2, 3, ...n-1, in a different order.

This means that if you multiply all the entries of the sequence it should have the same result as multiplying all the entries of the first sequence. But if you take out a factor x in this multiplication, the multiplication is x^(n-1) times the product of the entries in the original sequence Mod n. Therefore:

x^(n-1) = 1 Mod n if n is prime.

So, if you have some large number n and you calculate 2^(n-1) Mod n and this turns out to be different from 1 then you know that n can't be prime. The reverse is not true, because it can happen that 2^(n-1) Mod n is 1 ''by accident'' even if n is not prime. However this is unlikely if n is very large. But it is possible to give a rigorous proof for primality of any number using a bit more work. E.g. it can be shown that if
2^(n-1) = 1 mod n and if n = h q +1 for q a prime and h smaller than q^2, then n must be prime.

#4419 11/09/05 03:46 PM
Joined: Jan 2005
Posts: 375
C
Senior Member
Offline
Senior Member
C
Joined: Jan 2005
Posts: 375
Example: Is 10403 prime?

To calculate 2^10402 Mod 10403 write 10402 = 2*5201 and 5201 = 1 + 5200. We can write 5200 as 400*13.

Start with 2^(13)= 8192.
Square both sides:

2^(2*13)= 8192^2 = 9514 Mod n

Square again (ommiting the mod n sign):

2^(4*13)= 9514^2 = 10096

We need to raise this to the 100-th power. 100 = 2*2*5*5. To raise to the fifth power you just square it twice and multiply it with the original number:

2^(2*4*13)= 10096^2 = 622

2^(2*2*4*13)= 622^2 = 1973

2^(5*4*13)= 1973 * 10096 = 8066

2^(2*5*4*13)= 8066^2 = 10397

2^(2*2*5*4*13)= 10397^2 = 36

2^(5*5*4*13)= 36*8066=9495

2^(2*5*5*4*13)= 9495^2 = 2627

2^(5200)=2^(400*13)= 2^(2*2*5*5*4*13)= 2627^2 = 3940

2^(5201) = 2*3940 = 7880

Finally, 2^10402 = 7880^2 = 9296

So, we needed just 13 simple operations to find out that 10403 is not prime.

#4420 11/09/05 10:07 PM
Joined: Oct 2004
Posts: 540
U
Superstar
Offline
Superstar
U
Joined: Oct 2004
Posts: 540
For n=1,2,3... prime numbers are generated by

n^2 - n + 41

Was that so hard?


Uncle Al
http://www.mazepath.com/uncleal/
(Toxic URL! Unsafe for children and most mammals)
http://www.mazepath.com/uncleal/qz3.pdf
#4421 11/09/05 10:26 PM
Joined: Oct 2004
Posts: 4,136
D
Megastar
Offline
Megastar
D
Joined: Oct 2004
Posts: 4,136
But not nearly so impresive as a page full of doing it the hard way.


DA Morgan
#4422 11/10/05 02:00 AM
Joined: Oct 2004
Posts: 427
E
Senior Member
Offline
Senior Member
E
Joined: Oct 2004
Posts: 427
Quote:
Originally posted by Uncle Al:
For n=1,2,3... prime numbers are generated by n^2 - n + 41
Let's see..

n=103 n^2-n+41=10547 = 53*199
n=105 n^2-n+41=10961 = 97*113
n=110 n^2-n+41=12031 = 53*227
...

This is what I thought

e wink s

#4423 11/10/05 04:51 AM
A
Anonymous
Unregistered
Anonymous
Unregistered
A
hahah
really there is no clasical formula except the one I gave you at the begining.
All other apporaches are restatement of I said.
In Qunatum World things get solved non-sequentially. Multiple Dimesions get involved in its calculation. Making the solution fast to very fast depending upon the ability to make the ideal mesurement after time T out of ideal experiment P.The Time T is very small as compared classical calculation time t.

#4424 11/10/05 10:55 AM
Joined: Oct 2004
Posts: 427
E
Senior Member
Offline
Senior Member
E
Joined: Oct 2004
Posts: 427
Quote:
Originally posted by dkv:
In Qunatum World things get solved non-sequentially.
So you've fell for this crap, hah.

e confused s

#4425 11/11/05 04:40 AM
A
Anonymous
Unregistered
Anonymous
Unregistered
A
So you've fell for this crap, hah.
REP: No Boss.This is a fact.Things get solved along multiple Dimensions...It a hard reality...
Tomorrow whoever knows how to construct or use such a Device will actually be called a Superior Species.

#4426 11/11/05 06:26 AM
Joined: Oct 2004
Posts: 427
E
Senior Member
Offline
Senior Member
E
Joined: Oct 2004
Posts: 427
Quote:
Originally posted by dkv:
Tomorrow whoever knows how to construct or use such a Device will actually be called a Superior Species.
Are you watching too much of Deeeep Space?

:rolleyes:

#4427 11/11/05 06:48 AM
A
Anonymous
Unregistered
Anonymous
Unregistered
A
The power of such computers are unimaginarily huge.The realizable power of its solvin speed depends on the higher level dimensional understanding of m-theory.Thus more exploration is needed in the m-theory to fullfil and realize the dream of most the effective Qunatum State for doing the calculation.

#4428 11/11/05 11:02 AM
Joined: Oct 2004
Posts: 427
E
Senior Member
Offline
Senior Member
E
Joined: Oct 2004
Posts: 427
Quote:
Originally posted by dkv:
The power of such computers are unimaginarily huge.The realizable power of its solvin speed depends on the higher level dimensional understanding of m-theory.Thus more exploration is needed in the m-theory to fullfil and realize the dream of most the effective Qunatum State for doing the calculation.
Your sense of humor borders insanity - and how we do decide?

E eek s


Link Copied to Clipboard
Newest Members
debbieevans, bkhj, jackk, Johnmattison, RacerGT
865 Registered Users
Sponsor

Science a GoGo's Home Page | Terms of Use | Privacy Policy | Contact UsokÂþ»­¾W
Features | News | Books | Physics | Space | Climate Change | Health | Technology | Natural World

Copyright © 1998 - 2016 Science a GoGo and its licensors. All rights reserved.

Powered by UBB.threads™ PHP Forum Software 7.7.5