Problems & Puzzles: Conjectures

Conjecture 65. Non-Euclidean primes

Luis Rodríguez sent the following conjecture:

Call 'Euclidean Primes' those of the form: P = 2.p.q.r...+ 1 or -1 .

Call  'Non-Euclidean primes' those that in both forms there is at least a factor raised to a power >1 . Ex. : 127 = 2x3^2x7 + 1 =  2^7  - 1

For this last type of primes I say that the relation:

[Numb. of  Non-euclidean ] / [Numb of primes ] is  less than  N, when N---> infinite, is = 1/4 .

Example: There are 9592 primes < 100000 and 2381 Non_Euclidean . 2381/9592 = 0.248

The first Non-Euclidean are: 17,19,53,89,97,127,149,151,163,197,199,233,241,251.

Q1.- There is any explanation of that property?

Q2.- The presence of so many twin primes is a mere coincidence?

Contribution came only from J. K. Andersen & Farideh Firoozbakht.

***

Andersen wrote:

Q1. Let q be a random odd prime. Exactly one of q-1 and q+1 is divisible by 2^2.
Call the other n. Suppose n is a random even number not divisible by 4.
If n is divisible by p^2 for an odd prime p then q is a non-Euclidean prime.
Let p be an odd prime much smaller than n.
p does not divide q, so n has p^2-p possible values modulo p^2.
The expected chance that p^2 does not divide n is 1-1/(p^2-p).
In the limit for large q, the expected chance that n does not have any squared factor is the product of 1-1/(p^2-p) over all odd primes p.
The similar product C over all primes including 2 is called Artin's constant.
C = 0.3739558136192...
The product over odd primes is 2*C, since 1-1/(p^2-p) = 1/2 for p=2.
So the expected chance of a random large prime being Euclidean is 2*C,
and of being non-Euclidean is 1-2*C = 0.2520883727615...

Counts of non-Euclidean primes, all primes and the ratio for 10^5 to 10^11.
10^5: 2421 / 9592 = 0.2523978315
10^6: 19812 / 78498 = 0.2523885958
10^7: 167489 / 664579 = 0.2520227091
10^8: 1452678 / 5761455 = 0.2521373507
10^9: 12817966 / 50847534 = 0.2520862860
10^10: 114713084 / 455052511 = 0.2520875750
10^11: 1038117249 / 4118054813 = 0.2520892256

It comes close to the expected 1-2*C. I guess it converges to 1-2*C.

Q2. Suppose q and q+2 are random twin primes.
2^2 divides either q-1 or q+1. If it divides q-1 then it also divides q+3.
In that case only the single number q+1 needs an odd squared factor in
order for both q and q+2 to be non-Euclidean. That possibility increases
the expected chance that a twin prime pair will be non-Euclidean.

The chance that two random primes below 10^8 will both be non-Euclidean
is only 0.2521373507^2 = 0.0635732436.
There are 440312 twin prime pairs below 10^8. 94081 of them are both
non-Euclidean. The ratio is 94081/440312 = 0.21366.
2^2 divides q-1 for 91741 of the 94081 pairs.
The first 3 of the other 2340 pairs have q = 6959, 7547, 51059

***

Fardieh wrote:

According to the definition 2 is neither Euclidean nor Non_Euclidean.

So the definition should change a bit.

I think we can improve the definition in this way:

A prime p is Euclidean if |mu(p-1)| + |mu(p+1)| > 0 and is Non_Euclidean
if it isn't Euclidean, where "mu" is the Mobius function.
Note that according to the definition a prime p is Non_Euclidean if,
mu(p-1) = mu(p+1) = 0.

Note that we have following four cases.

1. mu(p-1) = 0 & mu(p+1) = 0 ( p is Non_Euclidean )
2. mu(p-1) = 0 & |mu(p+1)| = 1 ( p is Euclidean )
3. |mu(p-1)| = 1 & mu(p+1) = 0 ( p is Euclidean )
4. |mu(p-1)| = 1 & |mu(p+1)| = 1 ( p is Euclidean, only one solution p = 2 )

For the case 4 there exist only one solution p=2 , because between every two
consecutive even numbers 4 divides one of them. So if p is an odd prime at least
one of the p-1 or p+1 is not square-free, namely mu(p-1)*mu(p+1) = 0.

I think the limit should be greater than 1/4, because of following table.

m number of Non_Euclidean primes between first m primes
--------------------------------------------------------------------------------
1000000 252055
--------------------------------------------------------------------------------
2000000 252042
--------------------------------------------------------------------------------3000000 252159
--------------------------------------------------------------------------------4000000 252404
--------------------------------------------------------------------------------5000000 252161
--------------------------------------------------------------------------------6000000 252047
--------------------------------------------------------------------------------7000000 252209
--------------------------------------------------------------------------------8000000 251896
--------------------------------------------------------------------------------9000000 252051
--------------------------------------------------------------------------------10000000 252407
--------------------------------------------------------------------------------

So number of of Non_Euclidean primes between the first 10^7 primes is 2521431
and 2521431/10^7 ~ 0.252

***

 Records   |  Conjectures  |  Problems  |  Puzzles