7 votos

Son números de Euclides squarefree?

Son números de Euclides squarefree ? Un número de Euclides es, por definición, un Primorial número de + 1. Ver http://mathworld.wolfram.com/Primorial.html.

En la notación de la $n$ th Euclides número se escribe como $E_n = P_n+1.$

Por lo tanto me pregunto acerca de $a^2b = E_n$ por entero positivo $a,b,n$$a>1$.

Yo estaba pensando en Korselt del criterio : http://mathworld.wolfram.com/KorseltsCriterion.html y Fermats poco.

Im conscientes de otras técnicas para la demostración de la squarefree propiedad aparte de las más elementales herramientas como mcd y básico modular aritmetic.

No me imagino a infinito descenso a trabajar aquí ? Tal vez un binomium va a ayudar ?

Supongo que me he perdido algo trivial y que tenga un mal día.

Quizás $a^2b = E_n-2$ es más fácil ?

3voto

JiminyCricket Puntos 143

He aquí un argumento heurístico de la clase que Hurkyl menciona en un comentario que le da un valor distinto de cero "probabilidad" para todos los números de Euclides para ser squarefree.

La "probabilidad" para un gran número de squarefree es

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

donde $p_n$ $n$- ésimo primo. Los números de Euclides crecen tan rápido que podemos asintóticamente llevan a ser grandes números en el sentido de que podrían ser potencialmente divisible por los cuadrados de todos los números primos. (Cualquier error incurrido por esta aproximación sólo hará que nos subestimar su "probabilidad" de ser squarefree.) Sin embargo, por la construcción de $E_n$ no es divisible por el primer $n$ números primos. Por lo tanto, el $n$-th prime ha $n-1$ las posibilidades de su plaza de la división de un número de Euclides. Que hace el a priori de la "probabilidad" de todos los números de Euclides se squarefree aproximadamente

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

Los primeros términos de este producto deben ser tomadas con un gran bulto de sal, pero no estamos interesados en ellos, sólo en el comportamiento asintótico y en la parte izquierda después de Hagen exploración hasta el $p_{45}=197$. Dado que Hagen encontrar todos los números de Euclides a a $n=45$ a ser squarefree, cada primer ahora ha $45$ menos de posibilidades para su plaza para dividir un número de Euclides, por lo que el a posteriori "probabilidad" para todos los números de Euclides para ser squarefree es

$$ \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\;. $$

El factor de corrección antes de que el infinito producto es sólo acerca de la $1.035$ (cálculos 1 y 2), por lo que podemos centrarnos en el infinito del producto y de la aproximación, utilizando asintótica resultados para un gran $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} $$

Por lo tanto, junto con el factor de corrección de alrededor de $1.035$, ahora hay sólo aproximadamente un $1$ $5$ de probabilidad de encontrar un número de Euclides que no squarefree incluso si no hay sistemática de la razón, la prevención de este. Desde un punto de vista práctico, si hay uno que se encuentra, es raro encontrarse mediante la comprobación de más números de Euclides, que pronto sería excesivamente difícil, ya que incluso va a a $n=100$ ( $p_n=541$ ) sólo serviría para aumentar el producto a $\exp(-1/\log100)\approx0.80$; puede ser más eficaz para comprobar con más números en mayor $n$ de divisibilidad por plazas más pequeñas, que tienen una mejor tasa de éxito.

Por supuesto, el mismo análisis es válido para la números de $P_n-1$.

[Actualización:]

Dada la cita de Hormigón Matemáticas en Gerry comentario, sabemos que el cuadrado de ningún primer hasta el $p_{3000000}\approx5\cdot10^7$ se divide en un número de Euclides; por lo que el resto de la probabilidad de encontrar uno que hace es sólo aproximadamente el $1-\exp(-1/\log3000000)\approx6.5\%$.

3voto

Stephan Aßmus Puntos 16

Para tratar de explicar algo acerca de la matemática de la programación. No encuentras $1 +P_n$ y la esperanza de factor. Lo que debe hacer, también es exhaustiva, es fijar un primer $p$ tan grande como usted puede estar parado. A continuación, mantener un registro de los valores de $P_n \pmod {p^2}$ y mira a ver si $p^2 - 1.$ no Hay ninguna razón para tomar $p_n \geq p,$, ya que implicaría $P_n \equiv 0 \pmod p,$ por cada $p$ este es un cálculo finito. El resultado de esta búsqueda instantánea en la máquina, es que no $1 + P_n$ es divisible por el cuadrado de cualquier primer menor que $1625.$

Yo hice esto por $p^3 < 2^{32}$ sin suerte. Pero me llevé también el más fácil de los valores de $\pmod p,$ sólo para ver cómo a menudo que le dio nada. Tenga en cuenta que no se repite para $p = 277, \; 1051, \; 1381.$

EDDDIITTT, el jueves por la mañana: tengo esta trabajando en GMP, consiguió el primer $p$ hasta arriba de 1,000,000. Así, no $1 + P_n$ es divisible por el cuadrado de cualquier primer menor que $1000000.$ voy a hacer un intento de pegar el programa de C++ a continuación, a ver cómo va.

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

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 <iostream>
#include <stdlib.h>
#include <fstream>
#include <strstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>

#include <gmp.h>
#include <gmpxx.h>

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<mpz_class> 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<mpz_class>::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<mpz_class>::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 ;
} 

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X