mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2007-07-11, 07:21   #1
shawn
 

176916 Posts
Post there is another way to test the primality of a no

There is another way to test the primality of a no.If n be any number then if (n-1)!+1 is divisible by n then n is a prime number
  Reply With Quote
Old 2007-07-11, 11:37   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

Moved to Misc. Math.

Alex
akruppa is offline   Reply With Quote
Old 2007-07-12, 03:16   #3
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2×5×23 Posts
Default

Quote:
Originally Posted by shawn View Post
if (n-1)!+1 is divisible by n then n is a prime number
Yes, and only if. This is Wilson's Theorem. It's computationally useless.
Jens K Andersen is offline   Reply With Quote
Old 2007-07-12, 15:54   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

983710 Posts
Default

And the 2007 mfgoode Memorial Bronze Medal in Number Theory goes to the Thread Author, "For seminal work in the area of improved algorithmic efficiency in primality testing."

Shawn, PM me your snail-mail address and I'll send you your Medal, and even throw in a free handy-dandy neck-hanger thingie, "just like the Olympic athletes get."

I'm thinking we should award some MMBMNTs retroactively, seeing as the prize was only just established this year and the forum goes back a few years. Nominations for 2006? Bearnol, perhaps?
ewmayer is offline   Reply With Quote
Old 2007-07-17, 10:18   #5
Eivind
 
Feb 2006

3·17 Posts
Default Quick and dirty

Lest just make a quick and dirty survey.

This code

Code:
def f(n):
    a = 1
    for i in range (2,n+1):
        a = a*i
    return a

for i in range (2,3000):
    if (f(i-1)+1)%i == 0:
        print i
Takes about 15 sec. to finish

and this code (can I make the sieve more dirty than this

Code:
for n in range(2, 3000):
    for x in range(2, n):
        if n % x == 0:
            break
    else:
        print n
Takes less than 2 sec.

Yep, new kid on the block, beaten by 2000+ old algorithm.

-Eivind
Eivind is offline   Reply With Quote
Old 2007-07-17, 17:55   #6
mgb
 
"Michael"
Aug 2006
Usually at home

24×5 Posts
Default

Quote:
Originally Posted by shawn View Post
If n be any number then if (n-1)!+1 is divisible by n then n is a prime number
I know this conclusion is true but how did you reach it?
mgb is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
New Mersenne primality test Prime95 Miscellaneous Math 19 2014-08-23 04:18
N-1 primality test Citrix Math 3 2005-09-19 15:06
AKS Primality Test Guilherme Math 2 2004-11-26 05:29
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 09:03.

Mon Nov 30 09:03:13 UTC 2020 up 81 days, 6:14, 3 users, load averages: 1.58, 1.27, 1.15

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.