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 ?

  • 1
    How far do you have numerical evidence? My quick checks started to slow down already at $197\cdot193\cdot\ldots\cdot 2+1$.2012-10-24
  • 0
    Euclid said if you take any finite set of prime numbers and take their product (actually Euclid said their LCM), and add $1$, the prime factors of the resulting number are not in the finite set you started with. If the finite set you started with is $\{3\}$, then the number you get is $4$, and that's not squarefree. If you start with $\{3,5\}$, you get $16$, which is not squarefree. And with $\{5,7\}$ you get $36$. (But it seems to be conventional today to define "Euclid numbers" by taking the initial set of primes to contain all primes less than some number.)2012-10-24
  • 1
    I haven't thought about it much, but I'd be surprised if there is an algebraic reason for this conjecture to be true. But a pseudo-statistical argument suggests there is a non-zero probability that it could be "randomly" true.2012-10-24
  • 0
    @MichaelHardy : I note that 4 is 2*2 and 2 < 3 , 16 = 4*4 and 4 < 5 and 36 = 6*6 and 6 < 7. So that is far from a counterargument , I dare say the opposite. Also you simply used (x-1)(x+1) = x^2 - 1.2012-10-24
  • 0
    @mick : I thought I was pretty clear that what I wrote was not intended as a "counterargument". What relevance you intend the fact that $6<7$, etc., to have, escapes me.2012-10-24
  • 1
    @mick: Michael wrote an article on Euclid's proof of the infinitude of primes, which is often misrepresented in the literature. I think he was mostly trying to point out that the name "Euclid numbers" given to these numbers today shouldn't be taken to indicate that they figure in Euclid's proof. Also, one might expect any systematic arithmetic property of the Euclid numbers to be shared by the numbers Michael mentioned, so it wasn't a counterexample, but a reason to doubt that there's a systematic reason for your conjecture, even if it, as Hurkyl said it might, turns out to be "randomly" true.2012-10-24
  • 0
    @MichaelHardy : Well $6 < 7$ and $6=3*2$ but $3$ and $2$ are primes smaller than $7$. If you started $2*3*5*7 (+1)$ you would not get 0 mod 6.2012-10-24
  • 0
    As for the name ' Euclid number' It was named after Euclid many years after his death , in resemblance(!) of his proof. Rather than being exaclty part of his proof , or being invented by Euclid himself. Ofcourse a proof involving the Euclid numbers is very similar and works very well to show the infinitude of primes. In fact this is more convincing to young students. And imho it has some beauty.2012-10-24
  • 0
    @Hurkyl: I posted a heuristic calculation of the "probability" -- is this roughly what you had in mind?2012-10-25
  • 0
    @joriki: Yes, that is the approach I had in mind. +1!2012-10-25
  • 1
    On page 525 of Graham, Knuth, Patashnik, Concrete Mathematics, it says no square less than $25\times10^{14}$ divides a Euclid number.2012-10-25
  • 0
    Page 510 of the downloadable version.2012-10-25
  • 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
    What is wrong with this. I said preformatted text, it should keep the columns.2012-10-25
  • 0
    It worked better when I had each line start in the first column.2012-10-25
  • 0
    No complaints with the C++ program. This is anti-numerical discrimination.2012-10-25
  • 0
    Interesting use of the symmetry of `==` -- do you do that to make life more interesting? :-)2012-10-25
  • 0
    @joriki, yes, I feel I have a duty to entertain. However, it is also recommended programming practice in languages where = is assignment while == is equality comparison, since, if one mistakenly types 0 = x the compiler will call attention to the illegal assignment.2012-10-25
  • 0
    That's interesting. On the other hand, an IDE like Eclipse that draws attention to such things without jarring our subject-predicate sensibilities is also an option :-) (+1 by the way)2012-10-25
  • 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