## JackNova Primality Test

By Dario Iacampo**This was one of the very first algorithms I wrote (12/2005)**when I started studying programming and C# in particular.

I'm pretty passionate about numbers, in those days I was reading some books about

**prime numbers**and I started searching a different point of view for looking at those numbers.This is one of the observations I stumbled upon: what is represented here is the remainder of the division of a number for increasingly big numbers.

You can see that the function goes rapidly down for certain values, if it goes to zero you have a perfect divisor for your number but often it goes close to zero but doesn't reach it. To be clear,

**if you plot the same function for a prime number you get the same behavior but never get a zero for the reminder funcion**.

I found that the series of what I called 'Likely Divisors' that are numbers where the function falls down, can be calculated like this:

**LDn = LDn-1 - (LDn-1/n)**

but each time you choose a number as the more likely divisor, you have to do this test:

calculate remainder for both the flat result of the division and for the next numer: LD + 1;

then pick the one for whom the reminder is the lower and go ahead

Another thing I tried was converting the entire series of prime numbers in binary, represent zeros as empty balls and ones as filled one to have something like a shade that I can watch trying to see something.

But let's go back to my primality test, here it is the algorithm:

Here it is an example of the execution:

**Insert an integer**

**456789**

**LD_3 -> 152263**

**LD_43 -> 10623**

**LD_129 -> 3541**

**Not a prime number**

The algorithm executes the primality test and prints out divisors when finds them.

Here we have that the third, 43° and 129° he tried are divisors.

What makes me think is the part where I choose which is the better divisor to use to test if it divides my number.

**There should be some interesting property I'm missing...**

In those days I was in University and I shown the algorithm to my math professor, he offered me a couple of theories to look at but that didn't help so much.

I would be glad if anyone of you readers can say if this is an original work or a well known property / rubbish :-)

## Nessun commento :

## Posta un commento