Prime Numbers

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

Prime Numbers

Post by swensont » Mon Jan 20, 2014 2:45 am

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 123 times

Shaun_B
Posts: 451
Joined: Wed Apr 22, 2009 10:22 am

Re: Prime Numbers

Post by Shaun_B » Wed May 14, 2014 11:41 am

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 » Wed May 14, 2014 2:19 pm

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: 2559
Joined: Mon Sep 26, 2011 10:56 am
Location: Looking forward to summer in Somerset, UK...

Re: Prime Numbers

Post by 1024MAK » Wed May 14, 2014 3:30 pm

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

Mark

User avatar
Andy Rea
Posts: 1546
Joined: Fri May 09, 2008 2:48 pm
Location: notts UK

Re: Prime Numbers

Post by Andy Rea » Wed May 14, 2014 7:50 pm

has anybody actually dis-proved it ?
6 x ZX81, 1 x TS1500 , 1 x +3e, 1 x timex 2040 printer, 1 x timex 2020 cassette deck, siclair printer and some spectrum

olofsen
Posts: 169
Joined: Wed Jan 08, 2014 12:29 pm

Re: Prime Numbers

Post by olofsen » Wed May 14, 2014 10:40 pm

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 » Thu May 15, 2014 12:15 am

And why are there 24 families, rather than more? Come to that, what does it have to do with chromosomes?

olofsen
Posts: 169
Joined: Wed Jan 08, 2014 12:29 pm

Re: Prime Numbers

Post by olofsen » Thu May 15, 2014 9:01 am

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 » Thu May 15, 2014 10:57 am

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