Wednesday, March 11, 2015

A prime number generator algorithm based on x^2+(x-1)^2 that generates only primes.

(I wrote also a question about this in Mathematics Stack Exchange, here)

Update: a senior fellow at the Mathematics Stack Exchange clarified the reason why it works. It is just a trivial brute-force algorithm because for each value in [1..s] the algorithm is going through all f2(k+s) mod k until the first 0 congruent value is found, which turns to be a factor of f2(s) and then jumps to the next s. So basically finds for every f2(k) the first prime number that is a factor of f2(k). I did not see the forest for the trees. I am learning so much from them!

I think I could have found a prime number generator algorithm, but still I am not very sure, maybe this is an already known property of perfect square numbers, maybe not, but it looks amazing, so I wanted to share here the idea and the code.

The Python Code

# Elementary number theory
# -- Modular arithmetic (perfect square numbers)
# --- Computational number theory
# ----- Prime number generator function

# created by David @ Hobbymaths
# http://hobbymaths.blogspot.jp/

#import cProfile

def prime_number_generator():
    from math import floor, log, sqrt
    from gmpy2 import xmpz, c_mod, mul, is_odd, is_prime, add, sub, divexact, set_cache, is_square, digits

    # the execution takes around 50 minutes, depending on the computer
    def printTime():
        import time, datetime
        ts = time.time()
        st = datetime.datetime.fromtimestamp(ts).strftime('%Y-%m-%d %H:%M:%S')
        print(st+"\n")

    printTime()

    testlimit = xmpz(3000000)

    # insert all the f2 values in resfunc
    resfunc = []
    for n in range(1, testlimit):
        resfunc.append(add(sub(mul(50,mul(n,n)),mul(10,n)),1))

    totlist = []
    # shift S
    for s in range (0,50000):
        found = False
        # range K
        for k in range (1,testlimit-s-1):
            if (k!=1) and (resfunc[s+k]%k == 0 ):
                if (is_prime(k)):
                    totlist.append(str(k))
                else:
                    totlist.append("If this message appears the algorythm is wrong")
                found = True
                break
               
        #if not found:
            # if no prime number was found in the current range K[1..k] then append 0 if you want to know which shift s
            # does not find a prime number in the range K
            #totlist.append("0")
           
    mystr=""
    for l in totlist:
        mystr = mystr + l + "\t"

    # Will print the generated prime numbers
    print(mystr)

    printTime()
       
#cProfile.run('prime_number_generator()')
prime_number_generator()

       

1. How did I find it?

While I was studying the properties of perfect square numbers, I came across an observation about how some perfect square numbers were able to generate prime numbers when added to the previous or next perfect square. Specifically only those perfect squares of a natural number n = 5*k / k belongs to N, in other words, those perfect squares ending with "00" or "25", are able to generate prime numbers when added to the previous or next perfect square, and of course that happens only sometimes.

I focused on those who are able to generate two primes, with the previous and next perfect square.

For instance, these two samples:

n=(5*k)

n=(5*5=) 25+ (4*4=) 16(previous) = 41 (prime)
n=(5*5=) 25+ (6*6=) 36(next) = 61 (prime)

n=(30*30=) 900 + (29*29=) 841(previous) = 1741 (prime)
n=(30*30=) 900 + (31*31=) 961(next) = 1861 (prime)

...being the distance between those primes 4*k

Unfortunately, there is not a clear rule why some of the perfect squares only ending with "00" or "25" are able to obtain prime numbers.

For that reason, I wanted to learn more about the functions that are generating the above mentioned results, which are f1=x^2+(x+1)^2 and f2=x^2+(x-1)^2, but applied to x = 5*k and there was a great surprise in the results of that study.

2. The prime number generator algorithm (only generates primes):

First I wrote the same functions replacing x = 5*k:

f1(k)=50k^2+10k+1 and f2(k)=50k^2-10k+1.

I just wanted to know the relationship between k, f1(k) and f2(k), so I started to play with modular arithmetic, it was easier to use first f2, calculating some congruences series in the following way:

1) (shift s=1) Calculated the congruences serie [f2(k+1) mod k] for a range K [1..k], and I found out that there are only two k numbers whose congruence is 0, one of them is k=1 and the other was a prime number, k=41.

2) (shif s=2) Then, I did the same calculation of the congruences serie but shifting one number to the right, so now I calculated the congruences serie [f2(k+2) mod k] for all k, and again the two k numbers congruent with 0 were k=1 and in this case a new prime, k=181.

3) (shift s) I extended the calculation of congruence series shifting up from 3 to s=50000 to the right, and always in the congruences serie associated to the current s, the non trivial (I consider k=1 the trivial solution) k number that is congruent with 0 is always a prime number, when I have been able to find that number in the limits of the range of number K [1..k] I am using for the tests(*).

(*) Sometimes I cannot find the prime number, because, depending on the shift s, the 0 congruent primer number appears later, because it might be very big, and does not appear in my current defined K[1..k] range (of my Python test code) or it would be possible also that for certain s values there is no 0 congruent number in the congruences serie.

My tested range was K[1..50000] and S[1..50000] and it was able to find 40357 prime numbers inside the K range, but for some S values, the prime number still not appears inside the K range (in this test case S=50000 so 50000 - 40357 = 9643 primes are not found for a certain s shift value).

The greater prime found is 489061 and the smaller is 13, and they appear unordered along the shifting of S.

So according to the results, it seems possible to generate a list of only prime numbers by calculating f2(k+s) into a specifig range of K [1..k] and finding the first non trivial 0 congruent k which turns to be a prime number, applying it for a shifting S [1..s] (**). Each [f2(k+s) mod k] congruences serie provides a prime number for the final list of primes (when the prime number which is congruent to 0 is found inside K).

(**)I did not make the setup for f1 because is easier to work with f2.

The generated prime numbers list has repeated elements and the primes appear unordered, but it seems to provide only primes inside the range K[1..k].

The first k elements of the list are (for s=1, s=2, s=3...):

k=41,181,421,761, 1201, 1741, 2381, 3121, 17, 13, 13, 73, 53, 9661, 17, 12641, 14281, etc.

I did not find any reference in OEIS.

I am trying to understand why it works, but it is very promising. Please if somebody has some ideas about why the algorithm is working (or if there is a counterexample I did not see), please let me know.

I wonder if this is new or somehow it was already known, or I am wrong...
David


No comments:

Post a Comment