Method for generating prime numbers that "almost works"

LifeIn

Well-known member
I learned about this recently from the YouTube channel, Numberphile. You take any prime number and generate a larger prime number by writing the smaller prime number in base 4, then interpreting the resulting expression as a base 10 number. For example,

11 (base 10) = 23 (base 4), and sure enough, 23 (as a base 10 number) is prime, and larger than 11.
13 (base 10) = 31 (base 4), and sure enough, 31 is prime as a base 10 number.
17 (base 10) = 101 (base 4), and 101 is in fact prime as a base 10 number.
19 (base 10) = 103 (base 4), which is prime as a base 10 number.
23 (base 10) = 113 (base 4), which is prime as a base 10 number.
29 (base 10) = 131 (base 4), which is prime as a base 10 number.

This continues to work for 31 (producing 133), and 37 (producing 211).

However it fails at 41 which produces 221 which is not prime. It is not surprising that the method does eventually fail. The only thing that might be a little surprising is why it worked as well as it did all the way up to 37. Primes are not very dense around 211, 133, 131,113, etc. The fact that all these numbers which have no reason to be prime are in fact prime is surprising. So, what is the reason that this method "almost" worked for so many numbers?
 
That's a good question.
Why would one want to employ a prime number generator that almost works? Did Numberphile provide an answer for you?

Checking in Matlab:

Code:
>> q = 41;
>> baseStr = dec2base(q,4);
>> baseStr

baseStr =

221

Code:
>> Z = isprime(221)

Z =

     0

Verified.

__
 
Yes, it was explained like this: Although this method does not guarantee primes, it does guarantee that the numbers so formed are not divisible by 2, 3, or 5. 2 is obvious. 3 is a little trickier. It has to do with the fact that both 10 an 4 are one more than a multiple of 3. Therefore the trick of adding up the digits to check for divisibility by 3 works the same in both bases. Finally, there is 5. In base 5, you only need to look at the last digit. If a number is divisible by 5, the last digit in base 10 is either 5 or 0. If it is 0, then it is also even, which we have already covered. And if it is 5, then it could not have come from a base 4 representation because there is no digit '5' in base 10. Since the method shown covers 2, 3, and 5, that explains why this method works for small primes. For small numbers, the chances are high that if it passes these three tests, it is prime. But of course as numbers get larger, the pool of potential prime divisors gets much bigger and the method fails more and more.
 
Two corrections to what I wrote above that I noticed too late: One is that "In base 5, you only need to look at the last digit." should have been "in base 10 you only need to look at the last digit." The other is that "because there is no digit '5' in base 10." should have been "because there is no digit '5' in base 4"
 
Two corrections to what I wrote above that I noticed too late: One is that "In base 5, you only need to look at the last digit." should have been "in base 10 you only need to look at the last digit." The other is that "because there is no digit '5' in base 10." should have been "because there is no digit '5' in base 4"

Okay - yep

:coffee:?

Many authors have to provide errata about their work -hopefully- before readers catch the mistakes. I've been there and done that too.

___
 
Okay - yep

:coffee:?

Many authors have to provide errata about their work -hopefully- before readers catch the mistakes. I've been there and done that too.

___
Of course, we must all know the method of always generating a prime and that is to take every consecutive prime number, multiply them and then add 1. For example 2*3 + 1 = 7, 2*3*5 +1 = 31 and so forth. This method is used to show that the number of prime numbers is infinite. Because you can always take the last known prime number and multiply all the prime numbers beneath it, add 1 and generate a larger prime number.
 
I learned about this recently from the YouTube channel, Numberphile. You take any prime number and generate a larger prime number by writing the smaller prime number in base 4, then interpreting the resulting expression as a base 10 number. For example,

11 (base 10) = 23 (base 4), and sure enough, 23 (as a base 10 number) is prime, and larger than 11.
13 (base 10) = 31 (base 4), and sure enough, 31 is prime as a base 10 number.
17 (base 10) = 101 (base 4), and 101 is in fact prime as a base 10 number.
19 (base 10) = 103 (base 4), which is prime as a base 10 number.
23 (base 10) = 113 (base 4), which is prime as a base 10 number.
29 (base 10) = 131 (base 4), which is prime as a base 10 number.

This continues to work for 31 (producing 133), and 37 (producing 211).

However it fails at 41 which produces 221 which is not prime. It is not surprising that the method does eventually fail. The only thing that might be a little surprising is why it worked as well as it did all the way up to 37. Primes are not very dense around 211, 133, 131,113, etc. The fact that all these numbers which have no reason to be prime are in fact prime is surprising. So, what is the reason that this method "almost" worked for so many numbers?
Euler came up with a quadratic - n^2 + n + 41 - that generates primes all the way up to n = 39, and there are others that go a lot further?.
 
Why is the function stop generating primes at n = 56?

___
The question isn't why it should stop at n=56. The question is why should it have worked as long as it did. I wonder how people come up with these formulas. I couldn't be by random guessing at coefficients because the vast majority of them will fail much sooner than than. From the size of the coefficients, I would guess it is beyond the reach of an exhaustive search of combinations of coefficients, even for modern supercomputers. They must have leveraged some theory to reduce the search to something reasonable. Finding one prime by random guessing is feasible. It is done all the time in RSA encryption. But finding 56 primes from one guess of a combination of coefficients is unimaginably harder.
 
The question isn't why it should stop at n=56. The question is why should it have worked as long as it did. I wonder how people come up with these formulas. I couldn't be by random guessing at coefficients because the vast majority of them will fail much sooner than than. From the size of the coefficients, I would guess it is beyond the reach of an exhaustive search of combinations of coefficients, even for modern supercomputers. They must have leveraged some theory to reduce the search to something reasonable. Finding one prime by random guessing is feasible. It is done all the time in RSA encryption. But finding 56 primes from one guess of a combination of coefficients is unimaginably harder.

Some are born gifted is specific fields of knowledge. Euler is a very good example.

If I remember correctly, Euler's father was busy with his books accounting for daily business, and his son noticed some errors that were not readily evident by visual inspection. Soon afterward people from the region recognized that his son's talent was extraordinary. In physics, hypotheses are generated from observations and then applying mathematics in order to understand and even predict natural phenomena and this technique is a standard procedure that has worked since Galileo.

Euler certainly made complex mathematics a lot easier.


___
 
Last edited:
The question isn't why it should stop at n=56. The question is why should it have worked as long as it did. I wonder how people come up with these formulas. I couldn't be by random guessing at coefficients because the vast majority of them will fail much sooner than than. From the size of the coefficients, I would guess it is beyond the reach of an exhaustive search of combinations of coefficients, even for modern supercomputers. They must have leveraged some theory to reduce the search to something reasonable. Finding one prime by random guessing is feasible. It is done all the time in RSA encryption. But finding 56 primes from one guess of a combination of coefficients is unimaginably harder.
Coming up with the formula would be fairly easy. For a polynomial up to n^5, there are six coefficients, so it is a matter of solving six simultaneous equations derived from plugging in n=1 to n=6. This can be done by matrix reduction, which is certainly tedious, but doable. Then you test again other values of n to see how good it is.

And as you say, the question is why should it have worked as long as it did.
 
Coming up with the formula would be fairly easy. For a polynomial up to n^5, there are six coefficients, so it is a matter of solving six simultaneous equations derived from plugging in n=1 to n=6. This can be done by matrix reduction, which is certainly tedious, but doable. Then you test again other values of n to see how good it is.

And as you say, the question is why should it have worked as long as it did.

Even Excel works where a number of regression models (linear, polynomial, exponential) are available, and it supplies a goodness-of-fit (R-squared) tool to determine if the model is good enough.

___
 
Back
Top