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

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 and I would like to know it is look logical or not, or a counterexample if it is wrong. So please I would appreciate a review of it.

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 = 5k$, $k\in\mathbb 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 for $n=5k$:

$n=5^2+(5-1)^2=25+16 = 41$ (prime)

$n=5^2 + (5+1)^2=25+36 = 61$ (prime)

and

$n=30^2+(30-1)^2=900+841 = 1741$ (prime)

$n=30^2+(30+1)^2= 900 + 961 = 1861$ (prime)

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

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 function that are generating the above mentioned results, which are $f_1=x^2+(x+1)^2$ and $f_2=x^2+(x-1)^2$, but applied to $x = 5*k$ and there was a great surprise in the results of that study.

The prime number generator algorithm (only generates primes):

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

$f_1(k)=50k^2+10k+1$ and $f_2(k)=50k^2-10k+1$

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

1) (shift $s=1$) Calculated the congruence series $[f_2(k+1) \bmod 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) (shift $s=2$) Then, I did the same calculation of the congruence series but shifting one number to the right, so now I calculated the congruence series $[f_2(k+2) \bmod 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 $s=3$ to $s=50000$ to the right, and always in the congruence series 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 prime 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 congruence series.

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, but no counterexamples are found as well).

So according to the results, it seems possible to generate a list of only prime numbers by calculating $f_2(k+s)$ into a specific 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 $[f_2(k+s) \bmod k]$ congruence series 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,2,3,\ldots$):

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

In the range $S[1..50000], K[1..50000]$, the greatest prime found is $489061$ and the smallest prime is $13$, and they appear unordered along the shifting of $S$.

I did not find any reference in OEIS.

I am trying to understand why it works, but it is very promising. I have written the algorithm with Python code here.

Please if somebody has some ideas about why the algorithm is working (or if there is a counterexample I did not see or I am doing something wrong), please let me know, it looks very interesting.

I wonder if this is new or somehow it was already known, or I am totally wrong. Thank you!

• Your math formatting is horrible, so we will have to start by fixing that ... – String Mar 11 '15 at 10:01
• I gave up half way through - perhaps someone else would like to continue formatting it ... – String Mar 11 '15 at 10:08
• The way the sequence is generated is completely unclear, you should explain it separately. – Yves Daoust Mar 11 '15 at 10:14
• I am a newbie and not very familiar with it, thanks for reviewing it! – iadvd Mar 11 '15 at 10:15
• About the explanation, please the Python code will help to understand it, be aware that English native, I will try to rewrite... Thank you! – iadvd Mar 11 '15 at 10:18

What you are actually doing is finding the factors of $f_2(s)$.

\begin{align} 50(k+s)^2-10(k+s)+1 &= 50k^2 + 100ks + 50s^2 - 10k -10s + 1 \\ &= k(50k + 100s-10) + 50s^2-10s+1 \\ &\equiv 50s^2-10s+1 \bmod k \\ \end{align}

As you increase $k$ you will happen upon the factors of this expression. For example, for $s=9, f_2(s) = 3961 = 17\times 233$, you will find zeroes at $k=17, k=233$ and $k=3961$, and then all larger $k$ will return $3961$.

• again thank you very much for clarifying this. Now I understand, then it is just a trivial brute-force algorithm, because for each value in [1..s] is going through all [1..k] until the first zero is found, and then jumps to the next s. I did not see the forest for the trees. Memo: I will take more care about the math formatting! – iadvd Mar 12 '15 at 2:59
• by the way, thinking of it, due to the properties of the congruences, I think there is a way to enhance the algorithm to find the first root. I will try it. – iadvd Mar 12 '15 at 5:05
• @iadvd Certainly this should simplify your calculation - you don't need to add in k every time :-) – Joffan Mar 12 '15 at 6:32

Did you see the article : A sieve for all primes of the form $x^2 + (x+1)^2$ (Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae, 25. (1998) pp. 39–53 PANAYIOTIS G. TSANGARIS)

• wow! I have no words for this, I did not find that one, references to Fermat, Diophantus, Gauss and Sierpinski... simply awesome. I am trying to enhance my test, so this paper is gold. Thank you! – iadvd Mar 15 '15 at 1:19
• sorry, I apologize...I did not know that only one answer can be accepted, so I have returned the answer to @Joffan, but the link is also very good. – iadvd Mar 15 '15 at 3:19
• I know that you already accepted an answer, I did not want you to change it, it's just useful information for this question, so i good reading! – Elaqqad Mar 15 '15 at 11:46