Prime Numbers

Anything Sinclair ZX Basic related; history, development, tips - differences between BASIC on the ZX80 and ZX81
Post Reply
swensont
Posts: 76
Joined: Tue Jan 18, 2011 4:55 am
Location: SF Bay Area
Contact:

Prime Numbers

Post 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 242 times
Shaun_B
Posts: 474
Joined: Wed Apr 22, 2009 10:22 am

Re: Prime Numbers

Post by Shaun_B »

Thanks for this, I'll have a look after work.

Regards,

Shaun.
poglad
Posts: 133
Joined: Mon Mar 24, 2014 3:11 pm
Location: Aberdeen, Scotland

Re: Prime Numbers

Post 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!
User avatar
1024MAK
Posts: 5101
Joined: Mon Sep 26, 2011 10:56 am
Location: Looking forward to summer in Somerset, UK...

Re: Prime Numbers

Post by 1024MAK »

Yeah, okay. I think instead I will go and tune up my flux capacitor :shock:

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.
User avatar
Andy Rea
Posts: 1606
Joined: Fri May 09, 2008 2:48 pm
Location: Planet Earth
Contact:

Re: Prime Numbers

Post by Andy Rea »

has anybody actually dis-proved it ?
what's that Smell.... smells like fresh flux and solder fumes...
olofsen
Posts: 189
Joined: Wed Jan 08, 2014 12:29 pm

Re: Prime Numbers

Post 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.
poglad
Posts: 133
Joined: Mon Mar 24, 2014 3:11 pm
Location: Aberdeen, Scotland

Re: Prime Numbers

Post by poglad »

And why are there 24 families, rather than more? Come to that, what does it have to do with chromosomes?
olofsen
Posts: 189
Joined: Wed Jan 08, 2014 12:29 pm

Re: Prime Numbers

Post 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.
Last edited by olofsen on Fri May 16, 2014 7:35 pm, edited 2 times in total.
poglad
Posts: 133
Joined: Mon Mar 24, 2014 3:11 pm
Location: Aberdeen, Scotland

Re: Prime Numbers

Post 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. :|
Post Reply