Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
 Posted: Wed Feb 15, 2012 8:07 pm Post subject: |
 |
|
| jackmt wrote: | | Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship. |
I don't mean to be rude, but are you sure that you're not becoming a crank?
http://en.wikipedia.org/wiki/Crank_(person)
The idea that you have found a method for generating primes that is better than any method that has ever been found, given that you have not trained as a mathematician, is bordering on "impossible". In fact, I would go even further and say that it actually is impossible. So much work has been put into this problem that any improvement would take at least fifty pages to write down. If your method is written on a couple of pages... there's something wrong with it. There just is.
Comments that you have made seem to indicate that you are no closer to generating primes than you ever were. You have a method that generates numbers that are "either primes or products of primes". That includes every single natural number greater than 1. It's not an achievement at all. |
|
| Back to top |
|
blahblah123
Yellow-bellied Woodpecker
Joined: Jul 25, 2010
Posts: 57
|
| Posted: Wed Feb 15, 2012 8:48 pm Post subject: |
|
|
I found an O(n) time algorithm to generate the first n prime numbers. I've already sent it to the NSA.
C++ code:
| Code: |
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
print_prime(i);
}
return 0;
}
|
This is assuming print_prime(i) runs in O(1) time.
Guys, please don't steal my work. |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Wed Feb 15, 2012 8:52 pm Post subject: |
|
|
| blahblah123 wrote: | | I found an O(n) time algorithm to generate the first n prime numbers. |
Pffft. That's nothing. I just sent the NSA an O(n) algorithm that generates all of the first n natural numbers, not just the primes. Your method has been made redundant. |
|
| Back to top |
|
NeantHumain
Phoenix
![]()
Joined: Jun 25, 2004
Posts: 5119
Location: St. Louis, Missouri
|
| Posted: Wed Feb 15, 2012 11:20 pm Post subject: |
|
|
| blahblah123 wrote: | I found an O(n) time algorithm to generate the first n prime numbers. I've already sent it to the NSA.
C++ code:
| Code: |
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
print_prime(i);
}
return 0;
}
|
This is assuming print_prime(i) runs in O(1) time.
Guys, please don't steal my work. |
How's that going to compile? The function print_prime(int) isn't defined in iostream. In other words, where's the algorithm? |
|
| Back to top |
|
Ancalagon
Computer Geek
Joined: Dec 26, 2007
Posts: 2388
|
| Posted: Thu Feb 16, 2012 12:12 am Post subject: |
|
|
| NeantHumain wrote: | | Ha, anyway if we're talking optimizations, one thing is to substitute an equivalent iterative algorithm in place of the recursive one. The recursive algorithm runs the risk of a stack overflow for larger numbers, not to mention the overhead of calling a function, pushing its arguments onto the stack, etc. |
There is a compiler optimization called tail recursion that would generate the code for the iterative version given the recursive one. I know gcc supports it, although I don't know about other C compilers.
You have to set up your recursion to pass all the information the next iteration needs as arguments, but IIRC you actually did that the first time around.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1656
|
| Posted: Thu Feb 16, 2012 12:17 am Post subject: |
|
|
| NeantHumain wrote: | | How's that going to compile? The function print_prime(int) isn't defined in iostream. In other words, where's the algorithm? |
Geez, tough crowd.
I guess it's always going to be awkward to make such a joke in a community well-known for being bad at understanding subtext... Is it being a jerk to make a non-obvious joke here, knowing that a lot of people won't get it? Or does it help to "train" people to spot jokes? This is something that I have been wondering ever since that "Marxist professor" thread. |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Thu Feb 16, 2012 1:07 am Post subject: |
|
|
| Declension wrote: | | jackmt wrote: | | Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship. |
I don't mean to be rude, but are you sure that you're not becoming a crank?
http://en.wikipedia.org/wiki/Crank_(person)
The idea that you have found a method for generating primes that is better than any method that has ever been found, given that you have not trained as a mathematician, is bordering on "impossible". In fact, I would go even further and say that it actually is impossible. So much work has been put into this problem that any improvement would take at least fifty pages to write down. If your method is written on a couple of pages... there's something wrong with it. There just is.
Comments that you have made seem to indicate that you are no closer to generating primes than you ever were. You have a method that generates numbers that are "either primes or products of primes". That includes every single natural number greater than 1. It's not an achievement at all. |
You may be right, but I don't think so. I'll work on it again and get back to you. |
|
| Back to top |
|
NeantHumain
Phoenix
![]()
Joined: Jun 25, 2004
Posts: 5119
Location: St. Louis, Missouri
|
| Posted: Thu Feb 16, 2012 10:16 am Post subject: |
|
|
| Ancalagon wrote: | | NeantHumain wrote: | | Ha, anyway if we're talking optimizations, one thing is to substitute an equivalent iterative algorithm in place of the recursive one. The recursive algorithm runs the risk of a stack overflow for larger numbers, not to mention the overhead of calling a function, pushing its arguments onto the stack, etc. |
There is a compiler optimization called tail recursion that would generate the code for the iterative version given the recursive one. I know gcc supports it, although I don't know about other C compilers.
You have to set up your recursion to pass all the information the next iteration needs as arguments, but IIRC you actually did that the first time around. |
Well, we're assuming an optimizing compiler, and I know at least the older Microsoft Visual C++ compilers in their "Standard Edition" or "Learning Edition" (perhaps now "Express Edition") did not include an optimizing C or C++ compiler. |
|
| Back to top |
|
Shorttail
Blue Jay
Joined: Feb 04, 2012
Age: 26
Posts: 94
Location: Aarhus, Denmark
|
| Posted: Thu Feb 16, 2012 12:07 pm Post subject: |
|
|
| Declension wrote: | | Pffft. That's nothing. I just sent the NSA an O(n) algorithm that generates all of the first n natural numbers, not just the primes. Your method has been made redundant. |
Thanks. I mean, the NSA says thanks. Of course.
| blahblah123 wrote: | | Guys, please don't steal my work. |
Reminds me of my master code that produces all positive integers in O(n) time.
| jackmt wrote: | | You may be right, but I don't think so. I'll work on it again and get back to you. |
I definitely want to hear how it goes. :3
| Declension wrote: | Geez, tough crowd.
I guess it's always going to be awkward to make such a joke in a community well-known for being bad at understanding subtext... Is it being a jerk to make a non-obvious joke here, knowing that a lot of people won't get it? Or does it help to "train" people to spot jokes? This is something that I have been wondering ever since that "Marxist professor" thread. |
If you want a shoulder pat, try post it on stack overflow. ;3 |
|
| Back to top |
|
Thom_Fuleri
Phoenix
Joined: Mar 08, 2010
Posts: 802
Location: Leicestershire, UK
|
| Posted: Sat Feb 18, 2012 8:00 pm Post subject: Re: Method for generating prime numbers |
|
|
| jackmt wrote: | | I have devised a method for generating prime numbers. Is there one already in existence? |
Since you're not telling us anything about this magical algorithm, we're entirely unable to assess it. But I do have an interesting question. You've already said that it returns both primes and multiples of primes, and these need weeding out - the big question I have is whether it returns ALL the primes in a given range? Or just some of them?
I mean, I think 7420738134811 is a prime number. If it isn't, it's a multiple of one. But I couldn't tell you whether there were any more in the vicinity.
(Actually, aren't all numbers multiples of primes?) |
|
| Back to top |
|
ruveyn
Phoenix
Joined: Sep 22, 2008
Age: 76
Posts: 29326
Location: New Jersey
|
| Posted: Sat Feb 18, 2012 8:30 pm Post subject: |
|
|
Is there a computable function F such that F(n) is the n-th prime?
F(1) = 2
F(2) = 3
F(3) = 5
and so on.
ruveyn |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Sat Feb 18, 2012 9:27 pm Post subject: Re: Method for generating prime numbers |
|
|
| Thom_Fuleri wrote: | | jackmt wrote: | | I have devised a method for generating prime numbers. Is there one already in existence? |
Since you're not telling us anything about this magical algorithm, we're entirely unable to assess it. But I do have an interesting question. You've already said that it returns both primes and multiples of primes, and these need weeding out - the big question I have is whether it returns ALL the primes in a given range? Or just some of them?
I mean, I think 7420738134811 is a prime number. If it isn't, it's a multiple of one. But I couldn't tell you whether there were any more in the vicinity.
(Actually, aren't all numbers multiples of primes?) |
It generates only primes larger than 7, and it appears to generate all such primes. It also appears I was prematurely optimistic about its limited production of products of primes (not multiples of primes). It is producing more than I expected. |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Sat Feb 18, 2012 9:34 pm Post subject: |
|
|
| jackmt wrote: | | Declension wrote: | | jackmt wrote: | | Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship. |
I don't mean to be rude, but are you sure that you're not becoming a crank?
http://en.wikipedia.org/wiki/Crank_(person)
The idea that you have found a method for generating primes that is better than any method that has ever been found, given that you have not trained as a mathematician, is bordering on "impossible". In fact, I would go even further and say that it actually is impossible. So much work has been put into this problem that any improvement would take at least fifty pages to write down. If your method is written on a couple of pages... there's something wrong with it. There just is.
Comments that you have made seem to indicate that you are no closer to generating primes than you ever were. You have a method that generates numbers that are "either primes or products of primes". That includes every single natural number greater than 1. It's not an achievement at all. |
You may be right, but I don't think so. I'll work on it again and get back to you. |
Added 2:18 [oops. I thought I was editing]
I appreciate your skepticism. When I discovered it I was just playing with primes, discovered a set of properties, and imported a little trick I had invented from arithmetic to maintain that set of properties while changing the number. It is really that simple.
I didn't think I had discovered anything great. I thought surely someone else had found the same thing. Same mistake I made with my stolen paper on the Fibonacci sequence. Same method of discovery, as well. "Life is frittered away with detail. Simplify. Simplify." Thoreau
I am not your usual analyst. My methods always seek to simplify the problem, not find a more complex way to solve it. Being an Aspie, I tend to notice patterns, then I exploit them.
I don't know how to write a program to run it, but I think that would be rather simple.
All numbers are primes, sums of primes, or products of primes. My method generates primes greater than 7, and only products of primes larger than 5. More than I anticipated, but fewer than all.
More later.
Last edited by jackmt on Sat Feb 18, 2012 10:26 pm; edited 2 times in total |
|
| Back to top |
|
Ancalagon
Computer Geek
Joined: Dec 26, 2007
Posts: 2388
|
| Posted: Sat Feb 18, 2012 10:08 pm Post subject: |
|
|
| ruveyn wrote: | Is there a computable function F such that F(n) is the n-th prime?
F(1) = 2
F(2) = 3
F(3) = 5
and so on.
ruveyn |
F(n) = if (n=1) then 2 else X(F(n-1)+1)
X(n) = if (P(n) = 1) then n else X(n+1)
P(n) = if (D(n-1, n) = 0) then 1 else 0
D(i, n) = if (i <= 1) then 0 else (if (i | n) then 1 else D(i-1, n))
D(i, n) returns 1 when some number greater than 1 and less than or equal to i divides n.
P(n) returns 1 if n is prime.
X(n) returns the smallest prime equal to or greater than n.
F(n) returns the nth prime number.
Not fast at all, but computable.
_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton |
|
| Back to top |
|
Thom_Fuleri
Phoenix
Joined: Mar 08, 2010
Posts: 802
Location: Leicestershire, UK
|
| Posted: Sun Feb 19, 2012 5:05 am Post subject: |
|
|
An interesting snippet - apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n-1.
A little algebra, however, soon explains why.
6n is not prime (divides by 6!)
6n+2 and 6n+4 (or 6n-2) divide by 2.
6n+3 (or 6n-3) divides by 3.
So any prime necessarily much be one of the two remaining options - 6n+1, or 6n+5 (6n-1). |
|
| Back to top |
|
  |
Wrong Planet Autism Forum Index
-> Computers, Math, Science, and Technology
|
Previous 1, 2, 3, 4, 5, 6, 7, 8 Next
|
|
|
