mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2009-01-04, 07:58   #1
dilip_1bhowmik
 

22×971 Posts
Default New Prime-Finding Algorithm Discovered! L00K HERE!

Hi! guys , I wanna say something on PRIMES . I have found an Algorithm , which can create an endless list , I mean an infinite list of prime numbers . Not a prank friends, I really mean it . Can anyone tell me how to publish the same in GIMPS?
  Reply With Quote
Old 2009-01-05, 05:43   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23×1,171 Posts
Default

Quote:
Originally Posted by dilip_1bhowmik View Post
Hi! guys , I wanna say something on PRIMES . I have found an Algorithm , which can create an endless list , I mean an infinite list of prime numbers . Not a prank friends, I really mean it . Can anyone tell me how to publish the same in GIMPS?
Start a new thread here. Explain your algorithm.
Uncwilly is online now   Reply With Quote
Old 2009-01-05, 18:21   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22×192 Posts
Default

found this funny pic:
Attached Thumbnails
Click image for larger version

Name:	pic27753_1.gif
Views:	95
Size:	3.1 KB
ID:	3137  
R. Gerbicz is offline   Reply With Quote
Old 2009-01-05, 19:13   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175616 Posts
Default

Quote:
Originally Posted by dilip_1bhowmik View Post
Hi! guys , I wanna say something on PRIMES . I have found an Algorithm , which can create an endless list , I mean an infinite list of prime numbers .
I have one too:
Code:
infinite_list_of_primes=[];
for(n=2, infinity,
  factorial = prod(k=1, n - 1, k);
  if (factorial % n == n - 1,
    infinite_list_of_primes = concat(infinite_list_of_primes, n);
  );
);
It takes only O(n^3 log n) operations to find the first pi(n) primes!

Last fiddled with by CRGreathouse on 2009-01-05 at 19:16
CRGreathouse is online now   Reply With Quote
Old 2009-01-05, 19:35   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×53×73 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I have one too:
Code:
infinite_list_of_primes=[];
for(n=2, infinity,
  factorial = prod(k=1, n - 1, k);
  if (factorial % n == n - 1,
    infinite_list_of_primes = concat(infinite_list_of_primes, n);
  );
);
It takes only O(n^3 log n) operations to find the first pi(n) primes!
Oh sure, but Mr. Blowfly's superDuper soon-to-be-unpublished prime-finding algo can find them all - all infinity of them - in finite time. Beat that, Mr. My-House-Is-So-Huge-It-Puts-Yours-To-Shame.

Now, if you managed to get your own algo's work estimate down to a more-manageable O(oo3 log log oo), I might be more impressed...
ewmayer is online now   Reply With Quote
Old 2009-01-05, 20:26   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·29·103 Posts
Wink

Here's an optimization:
Code:
infinite_list_of_primes=[2];
for(n=3, infinity,
  factorial = 6 * prod(k=4, n - 1, k);
  if (factorial % n == n - 1,
    infinite_list_of_primes = concat(infinite_list_of_primes, n);
  );
);
This saves one iteration, plus two multiplications per iteration!
CRGreathouse is online now   Reply With Quote
Old 2009-01-06, 14:01   #7
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by dilip_1bhowmik View Post
Hi! guys , I wanna say something on PRIMES . I have found an Algorithm , which can create an endless list , I mean an infinite list of prime numbers . Not a prank friends, I really mean it . Can anyone tell me how to publish the same in GIMPS?
Well, if you do the Sieve of Eratosthenes for eternity, you will get an infinitely long list of prime numbers.
10metreh is offline   Reply With Quote
Old 2009-01-06, 14:46   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·29·103 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Well, if you do the Sieve of Eratosthenes for eternity, you will get an infinitely long list of prime numbers.
Yeah, but can you get the SoE published in GIMPS?
CRGreathouse is online now   Reply With Quote
Old 2009-01-06, 16:34   #9
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yeah, but can you get the SoE published in GIMPS?
It was only a joke.
10metreh is offline   Reply With Quote
Old 2009-01-06, 17:05   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
It takes only O(n^3 log n) operations to find the first pi(n) primes!
My code finds all primes too!!!!11!

Code:
unsigned long
nthprime(unsigned long n)
{
  unsigned long i = 1, p = 2;
  while (1)
    {
      while (i < n && p % nthprime(i) != 0UL)
        i++;
      if (i == n)
        return p;
      p++; i = 1;
    }
}
Alex
akruppa is offline   Reply With Quote
Old 2009-01-06, 18:08   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·29·103 Posts
Default

Quote:
Originally Posted by akruppa View Post
My code finds all primes too!!!!11!
Truly, I take off my hat for your accomplishment. Is this actually a proof that PRIMES is in EXP? Possibly even E?

Last fiddled with by CRGreathouse on 2009-01-06 at 18:09
CRGreathouse is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Endorsement Prime Numbers finding algorithm marouane Computer Science & Computational Number Theory 18 2017-11-06 15:41
pari-algorithm for finding Gaussian integer bases devarajkandadai Software 0 2017-07-11 05:42
OEIS - (2^n-5)/3 - n odd - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 10 2015-09-01 18:07
OEIS - 2^n-5 - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 13 2015-09-01 13:09
OEIS - A050414 - 2^n-3 - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 16 2015-08-31 02:32

All times are UTC. The time now is 04:05.

Thu Mar 4 04:05:44 UTC 2021 up 91 days, 17 mins, 1 user, load averages: 3.07, 2.08, 1.67

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.