7
$\begingroup$

Are Euclid numbers squarefree ? An Euclid number is by definition a Primorial number + 1. See http://mathworld.wolfram.com/Primorial.html.

In notation the $n$ th Euclid number is written as $E_n = P_n+1.$

Thus I wonder about $a^2b = E_n$ for positive integer $a,b,n$ and $a>1$.

I was thinking about Korselt's criterion : http://mathworld.wolfram.com/KorseltsCriterion.html and Fermats little.

Im unaware of other techniques for proving the squarefree property apart from more elementary tools as gcd and basic modular aritmetic.

I cannot imagine infinite descent to work here ? Maybe a binomium will help ?

I guess I missed something trivial and have a bad day.

Maybe $a^2b = E_n-2$ is easier ?

  • 0
    Thank you @joriki for pointing out the paper written by Michael Hardy. It was an interesting read. I will have to be careful of how I continue to present Euclid's proof.2015-05-22

2 Answers 2

3

Here's a heuristic argument of the kind that Hurkyl mentioned in a comment that gives a non-zero "probability" for all Euclid numbers to be squarefree.

The "probability" for a large number to be squarefree is

$ \prod_{n=1}^\infty\left(1-\frac1{p_n^2}\right)=\frac6{\pi^2}\;, $

where $p_n$ is the $n$-th prime. The Euclid numbers grow so fast that we can asymptotically take them to be large numbers in the sense that they could potentially be divisible by the squares of all primes. (Any error incurred by this approximation will only cause us to underestimate their "probability" to be squarefree.) However, by construction $E_n$ is not divisible by the first $n$ primes. Thus, the $n$-th prime has $n-1$ chances of its square dividing a Euclid number. That makes the a priori "probability" of all Euclid numbers being squarefree approximately

$ \prod_{n=2}^\infty\left(1-\frac1{p_n^2}\right)^{n-1}\;. $

The first few terms of this product are to be taken with a large lump of salt, but we're not interested in them, only in the asymptotic behaviour and in the part left after Hagen's exploration up to $p_{45}=197$. Given that Hagen found all Euclid numbers up to $n=45$ to be squarefree, every prime now has $45$ fewer chances for its square to divide a Euclid number, so the a posteriori "probability" for all Euclid numbers to be squarefree is

$ \prod_{n=47}^\infty\left(1-\frac1{p_n^2}\right)^{n-46}=\left(\frac{\pi^2}6\prod_{n=1}^{46}\left(1-\frac1{p_n^2}\right)\right)^{46}\prod_{n=47}^\infty\left(1-\frac1{p_n^2}\right)^n\;. $

The corrective factor before the infinite product is only about $1.035$ (computations 1 and 2), so we can focus on the infinite product and approximate it using asymptotic results for large $n$:

$ \begin{align} \prod_{n=47}^\infty\left(1-\frac1{p_n^2}\right)^n &\approx\prod_{n=47}^\infty\left(1-\frac1{(n\log n)^2}\right)^n \\ &\approx\prod_{n=47}^\infty\exp\left(-\frac1{n\log^2 n}\right) \\ &\approx\exp\left(-\int_{47}^\infty\frac1{x\log^2 x}\mathrm dx\right) \\ &=\exp\left(-\frac1{\log47}\right) \\ &\approx0.77\;. \end{align} $

Thus, together with the corrective factor of about $1.035$, there is now only roughly a $1$ in $5$ chance of finding a Euclid number that isn't squarefree even if there's no systematic reason preventing this. From a practical perspective, if there is one to be found, it's unlikely to be found by fully checking further Euclid numbers, which would soon become prohibitively difficult, since even going up to $n=100$ (with $p_n=541$) would only increase the product to $\exp(-1/\log100)\approx0.80$; it might be more efficient to check more numbers at higher $n$ for divisibility by smaller squares, which have a better hit rate.

Of course the same analysis holds for the numbers $P_n-1$.

[Update:]

Given the quote from Concrete Mathematics in Gerry's comment, we know that the square of no prime up to $p_{3000000}\approx5\cdot10^7$ divides a Euclid number; so the remaining chance of finding one that does is only approximately $1-\exp(-1/\log3000000)\approx6.5\%$.

3

Just to try to explain something about mathematics programming. You don't find $1 +P_n$ and hope to factor it. What you do, also exhaustive, is fix a prime $p$ as large as you can stand. Then you keep track of the values of $P_n \pmod {p^2}$ and see if you get $p^2 - 1.$ There is no reason to take $p_n \geq p,$ as that would imply $P_n \equiv 0 \pmod p,$ so for each $p$ this is a finite calculation. The result of this search, instantaneous on the machine, is that no $1 + P_n$ is divisible by the square of any prime smaller than $1625.$

I did this for $p^3 < 2^{32}$ with no luck. But I also took the easier values $\pmod p,$ just to see how often that gave anything. Note that there are repeats for $p = 277, \; 1051, \; 1381.$

EDDDIITTT, Thursday morning: I got this working in GMP, got the prime $p$ up above 1,000,000. So, no $1 + P_n$ is divisible by the square of any prime smaller than $1000000.$ I will make an attempt to paste the C++ program below, see how that goes.

=========================

p           p_n 3           2 7           3 19          17 31           5 59          13 61          41 73          53 97          17 131          89 139          53 149         107 167          43 173          53 181          37 211           7 223          61 271         263 277          17 277          59 307         283 313         239 317          23 331          29 347          19 463         443 467         199 509          13 571          29 601         179 673         659 809         677 827         499 877         677 881         137 953          47 983         463 997         769 1031         937 1033         587 1039          89 1051         211 1051         739 1063          71 1069         523 1109         839 1259         907 1279         811 1283         509 1291         439 1297         769 1361         163 1381         157 1381        1097 1471        1459 1543         127 1579         347 1619        1481 

=========================

=========================

#include  #include  #include  #include  #include  #include  #include  #include  #include  #include  #include   #include  #include   using namespace std;    int PrimeQ(int i) {   if ( i < 0 ) i *= -1;   if ( i <= 3) return 1;   else   {     int boo = 1;     int j = 2;      while (boo && j * j   <= i )     {       if ( i %  j  == 0) boo = 0;       ++j;     }     return boo;   } }  // PrimeQ deterministic and guaranteed, used on a range just once   // File named aa_GMP_trial.cc  //   compile with    //   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx  //  run with  //         ./aa_GMP_trial    //  because my machine needs to be told an executable is in the same directory     //  William C. Jagy     October 2012      int main() {      set Primes;    mpz_class n ;   n = 2;  //   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx      for (unsigned m = 2; m <= 1654321; ++m)     {       {        n = m;        if (PrimeQ(m))         {  Primes.insert(n);        //    cerr << n << endl;        }      }    }        set::iterator iter;     int count = 0;     for(iter = Primes.begin() ;  iter != Primes.end() ; ++iter)     {        mpz_class p = *iter;     //  cout << setw(8) << p;       ++count;    //   if(0 == count % 10) cout << endl;       if (0 == count % 1000) cout <<  "progress   " << p << endl;  //   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx      //   mpz_class target =  p - 1;    //   mpz_class p2 =  p;        mpz_class target = p * p - 1;       mpz_class p2 = p * p;        mpz_class q = 1;       mpz_class product = 1;          set::iterator iter2;        if( p > 2)       {       for(iter2 = Primes.begin() ; q < p &&  iter2 != Primes.end() ; ++iter2)       {          q = *iter2;           product *= q;          product %= (p2);          if ( target == product)            {             cout  << p << setw(12) << q << endl;          }       }  // iter2 for q       } // p > 3       } // iter for p      cout << endl << endl;   //   g++  -o aa_GMP_trial aa_GMP_trial.cc  -lgmp -lgmpxx       return 0 ; }  

========================

  • 0
    @joriki, reasonable point. There was a time ten years ago when I worked at a software firm and began learning such things. I prefer to edit on an ordinary text editor screen. It would be different if I were still employed in software, but now I prefer bare-bones interfaces that I know. It would also be different if the programs ever got very long or were sophisticated in a computer science sense, but all the thought is in the mathematics. Also, to put it briefly, I am not very good at installing things on my home computer.2012-10-25