Prime Numbers
Prime Numbers
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
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
Re: Prime Numbers
Thanks for this, I'll have a look after work.
Regards,
Shaun.
Regards,
Shaun.
Re: Prime Numbers
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!
- 1024MAK
- Posts: 5118
- Joined: Mon Sep 26, 2011 10:56 am
- Location: Looking forward to summer in Somerset, UK...
Re: Prime Numbers
Yeah, okay. I think instead I will go and tune up my flux capacitor
Mark
Mark
ZX81 Variations
ZX81 Chip Pin-outs
ZX81 Video Transistor Buffer Amp
Standby alert
There are four lights!
Step up to red alert. Sir, are you absolutely sure? It does mean changing the bulb
Looking forward to summer later in the year.
ZX81 Chip Pin-outs
ZX81 Video Transistor Buffer Amp
Standby alert
There are four lights!
Step up to red alert. Sir, are you absolutely sure? It does mean changing the bulb
Looking forward to summer later in the year.
Re: Prime Numbers
has anybody actually dis-proved it ?
what's that Smell.... smells like fresh flux and solder fumes...
Re: Prime Numbers
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.
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.
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
Re: Prime Numbers
And why are there 24 families, rather than more? Come to that, what does it have to do with chromosomes?
Re: Prime Numbers
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.
Last edited by olofsen on Fri May 16, 2014 7:35 pm, edited 2 times in total.
Re: Prime Numbers
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.