Page 1 of 1
Prime Numbers
Posted: Mon Jan 20, 2014 2:45 am
by swensont
Many years ago I ran across a person that said that he created an algorithm that would quickly determine if a number is a prime. The algorithm was odd and I did not trust it. Recently I remembered it and wrote a short paper on the algorithm, including the rather confusing explanation of the algorithm from the author, Mike Fink. The paper can be found here:
https://sites.google.com/site/svenqhj/
A ZX81 version has been attached to this post as a .p file. I have tested the algorithm for all primes under 1,500 and it works. Thought someone might find this interesting.
Tim Swenson
- mike.p
- (2.01 KiB) Downloaded 247 times
Re: Prime Numbers
Posted: Wed May 14, 2014 11:41 am
by Shaun_B
Thanks for this, I'll have a look after work.
Regards,
Shaun.
Re: Prime Numbers
Posted: Wed May 14, 2014 2:19 pm
by poglad
That's a fascinating web page you've got there Tim! As for the algorithm, I can see why a mathematician would consider it bunkum. After all, postulating a mathematical correspondence between chromosome families and prime numbers isn't far removed from deriving your algorithm from the dimensions of the Great Pyramid of Giza. On the other hand, fractal research revealed a lot of correspondence between mathematics and the natural/biological world. Regardless of the imaginative insight that led Fink to his solution, the resulting algorithm can still be analysed without recourse to the chromosome idea, but not by me I'm afraid!
Re: Prime Numbers
Posted: Wed May 14, 2014 3:30 pm
by 1024MAK
Yeah, okay. I think instead I will go and tune up my flux capacitor
Mark
Re: Prime Numbers
Posted: Wed May 14, 2014 7:50 pm
by Andy Rea
has anybody actually dis-proved it ?
Re: Prime Numbers
Posted: Wed May 14, 2014 10:40 pm
by olofsen
It is a form of "trial division" (
http://en.wikipedia.org/wiki/Trial_division) where the candidate factors are mostly prime when C=0 and with less prime candidates as C increases.
Here is a slightly shifted version of the 24 families. For C=0, the 24 numbers contain all numbers except those that can be divided by 2, 3, and 5; those that can be divided by 7 are still there and marked. For C=1, numbers that can be divided by 11 and 13 appear and so on.
Code: Select all
C 1 2 3 4 5 6 7 8 9 10 11 12
13 14 15 16 17 18 19 20 21 22 23 24
0: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89
7 7
1: 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133,
7 7 11 7
137, 139, 143, 149, 151, 157, 161, 163, 167, 169, 173, 179,
11 7 13
So instead of keeping all primes in memory, there is a short list of candidates, the algorithm becoming less efficient as the number to be tested increases.
Re: Prime Numbers
Posted: Thu May 15, 2014 12:15 am
by poglad
And why are there 24 families, rather than more? Come to that, what does it have to do with chromosomes?
Re: Prime Numbers
Posted: Thu May 15, 2014 9:01 am
by olofsen
There are 24 numbers in the first 90 that are prime or can be divided by 7. Primes 2, 3, and 5 are quickly handled in lines 80 and 82. There would be more ways to construct a candidate list, smaller or larger than 24. A list X with four elements would be 3, 7, 9 and 11, numbers that are prime or can be divided by 3. Change the 24 to 4 in lines 88 (and 96) and the 90 to 10 in line 90 to check.
Re: Prime Numbers
Posted: Thu May 15, 2014 10:57 am
by poglad
Oh I see - so with fewer families, it gets less efficient more quickly, and with more families it would stay efficient for a larger range. The guy who wrote the original article seemed to think that 24 families was some kind of naturally-occurring constant. I suppose for the candidates he chose, it is. But it sounds like there's nothing special about 24 in particular, and his theory of discovering a grand union between mathematics and biochemistry might not necessarily be 100% sound.
