heavenlyabyss
Phoenix
Joined: Sep 10, 2011
Posts: 530
|
 Posted: Sun Feb 19, 2012 5:06 am Post subject: |
 |
|
Umm, I would like to see this algorithm explicitly, I would be very fasincated to see it actually.
In my highschool years, I found a book that my dad had that listed prime numbers up to about 10,000 or so, and I became very fascinated with it, trying to find the pattern in the whole. I vehemently disagree with this common conception that is random. I always felt like there must be some underlying chatoic pattern to the primes. I mean, how could be there not be?
I do think an Indian mathematician came up with a pretty good method. I will look up and report on it afterward. |
|
| Back to top |
|
heavenlyabyss
Phoenix
Joined: Sep 10, 2011
Posts: 530
|
| Posted: Sun Feb 19, 2012 5:49 am Post subject: |
|
|
| Okay, the man I am talking about is Ramanujuan. I am having a little trouble sorting through it at the moment, since it is very high math (much higher than what I can understand), but it might be something to look at. |
|
| Back to top |
|
lau
Really nice person to know. :)
Joined: Jun 18, 2006
Age: 64
Posts: 10537
Location: Somerset UK
|
| Posted: Sun Feb 19, 2012 6:33 am Post subject: |
|
|
| Thom_Fuleri wrote: | An interesting snippet - apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n-1.
...
So any prime necessarily much be one of the two remaining options - 6n+1, or 6n+5 (6n-1).
... |
To be a bit more pedantic... (  )
Apart from nothing, all prime numbers can be expressed as n.
Apart from 2, all prime numbers can be expressed as 2n+1.
Apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n+5.
...
This approach generalizes: http://en.wikipedia.org/wiki/Primorial
I'd guess that, if working on numbers with a view to establishing their primality, storing values in base 30030 (2*3*5*7*11*13) would give a quick test that eliminated most composites.
_________________
"Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer |
|
| Back to top |
|
ruveyn
Phoenix
Joined: Sep 22, 2008
Age: 76
Posts: 29296
Location: New Jersey
|
| Posted: Sun Feb 19, 2012 8:41 am Post subject: |
|
|
| Thom_Fuleri wrote: | 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.
. |
The narrows down where to look for primes. But it is not a prime generator. 6*8 + 1 = 7*7
ruveyn |
|
| Back to top |
|
jackmt
Raven
Joined: Dec 14, 2011
Posts: 111
Location: Missoula, MT
|
| Posted: Sun Feb 19, 2012 11:10 am Post subject: |
|
|
| ruveyn wrote: | | Thom_Fuleri wrote: | 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.
. |
The narrows down where to look for primes. But it is not a prime generator. 6*8 + 1 = 7*7
ruveyn |
If my method turns out not to be much, I will demonstrate it here. I am working with someone to explore it further. Fuleri's formulation approaches my simplicity, but is not like my method at all.
Rethinking: Fuleri's equation is beginning to look a lot like an equivalent statement. I'll be back.
Last edited by jackmt on Sun Feb 19, 2012 2:09 pm; edited 1 time in total |
|
| Back to top |
|
b9
whatever..
Joined: Aug 15, 2008
Posts: 8353
Location: australia
|
| Posted: Sun Feb 19, 2012 11:32 am Post subject: |
|
|
i do not have enough time to explore some methods i am interested in.
i would like to make a number pyramid )where 1 is the apex and 2 and 3 are the second row and 4,5,and 6 are the third row etc, and i would like to make the base of the pyramid 1 million numerals or more, and then plot all the prime number positions within that pyramid to see if there is some sort of trigonometrical recursive rule in the positions of the prime number plots in a vectorial sense.
there must be some pattern that can be found in a pyramid of numbers with precalculated (using simple ways) primes highlighted that can yield a law that is true for prediction of other highlightable points not yet assessed using trigonometry.
i have a business to run and dollars to make and a tummy to fill with food, and i have a brain that needs sleep, but soon i will look at the problem further, and i will give up then. |
|
| Back to top |
|
Thom_Fuleri
Phoenix
Joined: Mar 08, 2010
Posts: 801
Location: Leicestershire, UK
|
| Posted: Sun Feb 19, 2012 1:49 pm Post subject: |
|
|
| b9 wrote: | | i would like to make a number pyramid )where 1 is the apex and 2 and 3 are the second row and 4,5,and 6 are the third row etc, and i would like to make the base of the pyramid 1 million numerals or more, and then plot all the prime number positions within that pyramid to see if there is some sort of trigonometrical recursive rule in the positions of the prime number plots in a vectorial sense. |
There isn't. People tend to look at primes in the wrong way - they aren't following a pattern. They are what's left when you take away the pattern. Unfortunately this means we can't predict them!
My little snippet earlier (I didn't invent it, by the way) won't report all prime numbers, but it IS a way you can potentially cut down on the ones to check. Rather than looking at every number up to N, you can simply look at every n and n+2 up to N, where n starts at 5 and goes up by 6 each iteration. That could make things faster.
You can also ignore any even numbers other than 2, of course, but the above suggestion already does. |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1652
|
| Posted: Sun Feb 19, 2012 2:10 pm Post subject: |
|
|
| heavenlyabyss wrote: | | I vehemently disagree with this common conception that is random. |
Nobody believes that the prime numbers are random! They are obviously deterministic.
But they are pseudorandom, in many senses. This isn't just an opinion, it has been proven. |
|
| Back to top |
|
Thom_Fuleri
Phoenix
Joined: Mar 08, 2010
Posts: 801
Location: Leicestershire, UK
|
| Posted: Sun Feb 19, 2012 2:22 pm Post subject: |
|
|
| Declension wrote: | | heavenlyabyss wrote: | | I vehemently disagree with this common conception that is random. |
Nobody believes that the prime numbers are random! They are obviously deterministic.
But they are pseudorandom, in many senses. This isn't just an opinion, it has been proven. |
Technically, they are emergent. That is, they are determined - but the only way to work them out is to go through from the beginning. |
|
| Back to top |
|
Ancalagon
Computer Geek
Joined: Dec 26, 2007
Posts: 2388
|
| Posted: Sun Feb 19, 2012 3:17 pm Post subject: |
|
|
@jackmt: I think I have a pretty good test for your method.
I'm going to abbreviate 1 billion as b.
There are 3 primes between b+100 and b+200, 21 primes between 100 and 200, and 12 between 1100 and 1200. If your method is similar to previously known methods, it will generate closer to 21 or 12 candidates than 3 over the b+100 to b+200 range.
There are approximately n/(ln n) primes less than n, so we can get the approximate number of primes in a range by hi/(ln hi) - lo/(ln lo), which is about 4.59 over 100 integers near a billion. So from b+100 to b+200, we have slightly fewer than expected, but over b to b+100 there are 7 primes, so a few more than expected.
_________________
"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: 1652
|
| Posted: Sun Feb 19, 2012 3:30 pm Post subject: |
|
|
| Thom_Fuleri wrote: | | the only way to work them out is to go through from the beginning. |
I'm not sure what you mean by this. If you mean "it is impossible to check whether a number n is prime without first checking whether all numbers less than n are prime", then it is false.
For example, to check whether 1031 is prime, we might just go through all the numbers from 2 to floor(1031/2), and check whether they are factors of 1031. We don't ever have to check whether 1029 is prime. |
|
| Back to top |
|
ruveyn
Phoenix
Joined: Sep 22, 2008
Age: 76
Posts: 29296
Location: New Jersey
|
| Posted: Sun Feb 19, 2012 5:06 pm Post subject: |
|
|
| Declension wrote: | | Thom_Fuleri wrote: | | the only way to work them out is to go through from the beginning. |
I'm not sure what you mean by this. If you mean "it is impossible to check whether a number n is prime without first checking whether all numbers less than n are prime", then it is false.
For example, to check whether 1031 is prime, we might just go through all the numbers from 2 to floor(1031/2), and check whether they are factors of 1031. We don't ever have to check whether 1029 is prime. |
The range should be from 2 to floor (sqrt (1031)).
ruveyn |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1652
|
| Posted: Sun Feb 19, 2012 5:10 pm Post subject: |
|
|
| ruveyn wrote: | | The range should be from 2 to floor (sqrt (1031)). |
Sure, that's an even cleverer way to do it. But I wasn't trying to give the cleverest possible way, I was just trying to show that it is possible to check whether a number is prime without first checking whether every number below it is prime. |
|
| Back to top |
|
Thom_Fuleri
Phoenix
Joined: Mar 08, 2010
Posts: 801
Location: Leicestershire, UK
|
| Posted: Sun Feb 19, 2012 6:19 pm Post subject: |
|
|
| Declension wrote: | | Thom_Fuleri wrote: | | the only way to work them out is to go through from the beginning. |
I'm not sure what you mean by this. If you mean "it is impossible to check whether a number n is prime without first checking whether all numbers less than n are prime", then it is false.
For example, to check whether 1031 is prime, we might just go through all the numbers from 2 to floor(1031/2), and check whether they are factors of 1031. We don't ever have to check whether 1029 is prime. |
I'm working on the assumption that you are actually looking for all the primes. Testing a single number is straightforward (though if you already have a list of primes below that number, it's a lot quicker). |
|
| Back to top |
|
Declension
Phoenix
Joined: Jan 21, 2012
Posts: 1652
|
| Posted: Sun Feb 19, 2012 6:21 pm Post subject: |
|
|
| Thom_Fuleri wrote: | | I'm working on the assumption that you are actually looking for all the primes. |
I'm trying to understand what you meant by
| Thom_Fuleri wrote: | | the only way to work them out is to go through from the beginning. |
It seems like an interesting thing to say, but I'm not sure what it means. Could you express it more carefully?
The only two readings that I can think of are "In order to find all of the primes from 1 to N, you need to find all of the primes from 1 to N", which is trivial, and "In order to check whether N is a prime, you need to check whether every number below N is a prime", which is false. |
|
| Back to top |
|
  |
Wrong Planet Autism Forum Index
-> Computers, Math, Science, and Technology
|
Previous 1, 2, 3, 4, 5, 6, 7, 8 Next
|
|
|
