Generatore di numeri primi

[P_1_6]

Generatore di numeri primi

Inserendo al posto di p un numero primo nella forma 12*x+5
se per m=0 oppure n=0 questa ammette soluzioni intere
allora P è primo

$(p+1)/2+24*m*n+6*m+6*n+1=(2*(3*m+n+1))^2$
,
$24*m*n+6*m+6*n+1=3*(3*P-3)/6+1$

[Studente Anonimo]

Questi giorni sono occupato, ci torno sopra quando avrò tempo. Comunque ripeto che quella che hai scritto non è una dimostrazione, sembrano piuttosto righe di codice, ed è molto difficile decifrare di cosa stai parlando.

[P_1_6]

"Martino":Questi giorni sono occupato, ci torno sopra quando avrò tempo. Comunque ripeto che quella che hai scritto non è una dimostrazione, sembrano piuttosto righe di codice, ed è molto difficile decifrare di cosa stai parlando.

grazie

EDIT:
Intanto ho fatto un altro test della congettura fino a $100000$ ed è tutto ok
Lascio il sorgente

#include <stdio.h>
#include <stdlib.h>
#include <math.h>





int main(){
  long long int n,i,mcd,p,q,P=0,fattore,mom;
  long long int V[17402][3];

  n = insert_array(V);   // Inserimento degli elementi nell'array

  mergeSort(V, 0, n-1);  // Chiamata alla funzione merge sort

  for (i=0; P<100000; i++) {
    P=V[i][0];
    P=2*P-1;

    p=V[i][1];
    p=4*p+1;
    q=V[i][2];
    q=4*q+1;
    MCD(p,q,&mcd);
    if ((mcd== 1 )&& ((V[i][0]!=V[i-1][0]) &&  (V[i][0]!=V[i+1][0]))){
        if (P%12==5){
             printf("id**************************%d \n",i);
            printf("primo***********************************%lli \n",P);
           
        }
    printf("\n");
    mom=V[i][0];
    mom =2*mom-1;
    fattore=3;

         while (fattore<=sqrt(mom)){
        if (P%12==5){
        if(mom%fattore==0){
            printf("12*x+5=%lli non è primo \n",P);
            int w;scanf("%d",&w);
            break;
        }
        }
        fattore=fattore+2;
    }

  }
  }
  scanf ("&lli",&i);
  return 0;
}
int MCD (long long int n1,long long int n2 ,long long int * mcd)
 /* calcola il massimo comun divisore di due interi * usando il metodo di
 Euclide */
{
 long long int resto, a, b;
 if(n1<0){n1=0-n1;}
  if(n2<0){n2=0-n2;}

if(n1>=n2){
 a = n1;
 b = n2;
 }else{
 a = n2;
 b = n1;
 }
 while (b > 0) {
 resto = a % b;
 a = b;
 b = resto;
 }

 *mcd=a;
}


// Funzione per l'inserimento degli elementi nell'array
int insert_array(long long int V[17402][3]) {
  long long int n, i=0,a=-113,b=-38,p;
  n=17402;

  while(i<17402) {

     while (a<=112){
     b=-38;
     while (b<=38){
     V[i][0]=36*b*b+18*b+4*a*a+2*a+3;
     V[i][1]=a;
     V[i][2]=b;
     b++;
     i++;
     }
     a++;
     }
  }
  return(n);
}


// Funzione per fondere due sotto-vettori ordinati in un unico vettore ordinato
void merge(long long int a[17402][3], long long int p, long long int q, long long int r) {
  long long int i, j, k=0, b[17402][3];
  i = p;
  j = q+1;

  while (i<=q && j<=r) {
    if (a[i][0]<a[j][0]) {
      b[k][0] = a[i][0];
      b[k][1] = a[i][1];
      b[k][2] = a[i][2];
      i++;
    } else {
      b[k][0] = a[j][0];
      b[k][1] = a[j][1];
      b[k][2] = a[j][2];
      j++;
    }
    k++;
  }
  while (i <= q) {
    b[k][0] = a[i][0];
    b[k][1] = a[i][1];
    b[k][2] = a[i][2];
    i++;
    k++;
  }
  while (j <= r) {
     b[k][0] = a[j][0];
      b[k][1] = a[j][1];
      b[k][2] = a[j][2];
    j++;
    k++;
  }
  for (k=p; k<=r; k++){
    a[k][0] = b[k-p][0];
    a[k][1] = b[k-p][1];
    a[k][2] = b[k-p][2];

    }
  return;
}

// Funzione principale per eseguire il merge sort
int mergeSort(long long int a[17402][3],long long int p,long long int r) {
  long long int q;
  if (p < r) {
    q = (p+r)/2;
    mergeSort(a, p, q);    // Ordina il sotto-vettore sinistro
    mergeSort(a, q+1, r);  // Ordina il sotto-vettore destro
    merge(a, p, q, r);     // Unisci i sotto-vettori ordinati
  }
  return 0;
}

[P_1_6]

Ho capito come si dimostra se la congettura $mcd(4*n+1,4*m+1)!=1$ se è vera o falsa

solve integer $36*m^2+18*m+4*n^2+2*n+3=(12*x+5+1)/2$

guardare le soluzioni nell'immagine



è un lavoro certosino che nei prossimi giorni farò

Osserviamo la prima soluzione

$x=54*c^2+9*c+6*d^2+d$ ; $m=3*c$ ; $n=3*d$

ed il fatto che questa

$36*m^2+18*m+4*n^2+2*n+3=(p+1)/2$

è equivalente a questa

$(3*(4*m+1))^2+(4*n+1)^2=2*p$

quindi

se $2*p$ è diviso da

$(4*m+1)+(4*n+1)$

e da

$(4*m+1)-(4*n+1)$

significa che p non è primo se $mcd(4*n+1,4*m+1)!=1$

e la prima soluzione lo conferma guardate

$2*(12*(54*c^2+9*c+6*d^2+d)+5)/(4*(3*c)+1+4*(3*d)+1)$

$2*(12*(54*c^2+9*c+6*d^2+d)+5)-54*2*c(4*(3*c)+1+4*(3*d)+1)+108*d*(4*(3*c)+1+4*(3*d)+1)=10*(4*3*d+1)^2$

$2*(12*(54*c^2+9*c+6*d^2+d)+5)-12*d*(4*(3*c)+1+4*(3*d)+1)+12*c*(4*(3*c)+1+4*(3*d)+1)=10*(4*3*c+1)^2$

$2*(12*(54*c^2+9*c+6*d^2+d)+5)/(4*(3*c)+1-(4*(3*d)+1))$

$2*(12*(54*c^2+9*c+6*d^2+d)+5)-2*54*c*(4*(3*c)+1-(4*(3*d)+1))-2*54*d*(4*(3*c)+1-(4*(3*d)+1))-18*(4*(3*c)+1-(4*(3*d)+1))=10*(4*3*d+1)^2$

$2*(12*(54*c^2+9*c+6*d^2+d)+5)+12*d*(4*(3*c)+1-(4*(3*d)+1))+12*c*(4*(3*c)+1-(4*(3*d)+1))+2*(4*(3*c)+1-(4*(3*d)+1))=10*(4*3*c+1)^2$

Le altre le provo nei prossimi giorni

EDIT1:

Anche la seconda soluzione lo conferma

$x=54*c^2+9*c+6*d^2+5*d+1$ ; $m=3*c$ ;$n=3*d+1$

$2*(12*(54*c^2+9*c+6*d^2+5*d+1)+5)/(4*(3*c)+1+4*(3*d+1)+1)$

$2*(12*(54*c^2+9*c+6*d^2+5*d+1)+5)-54*2*c*(4*(3*c)+1+4*(3*d+1)+1)+54*2*d*(4*(3*c)+1+4*(3*d+1)+1)+36*(4*(3*c)+1+4*(3*d+1)+1)=10*(4*(3*d+1)+1)^2$

$2*(12*(54*c^2+9*c+6*d^2+5*d+1)+5)-12*d*(4*(3*c)+1+4*(3*d+1)+1)+12*c*(4*(3*c)+1+4*(3*d+1)+1)-4*(4*(3*c)+1+4*(3*d+1)+1)=10*(12*c+1)^2$

$2*(12*(54*c^2+9*c+6*d^2+5*d+1)+5)/(4*(3*c)+1-(4*(3*d+1)+1))$

$2*(12*(54*c^2+9*c+6*d^2+5*d+1)+5)-54*2*c*(4*(3*c)+1-(4*(3*d+1)+1))-2*54*d*(4*(3*c)+1-(4*(3*d+1)+1))-54*(4*(3*c)+1-(4*(3*d+1)+1))==10*(4*(3*d+1)+1)^2$

$2*(12*(54*c^2+9*c+6*d^2+5*d+1)+5)+12*d*(4*(3*c)+1-(4*(3*d+1)+1))+12*c*(4*(3*c)+1-(4*(3*d+1)+1))+6*(4*(3*c)+1-(4*(3*d+1)+1))=10*(12*c+1)^2$

EDIT2:

Anche la terza soluzione lo conferma

$x=54*c^2+45*c+6*d^2+d+9$ ; $m=3*c+1$ ; $n=3*d$

$2*(12*(54*c^2+45*c+6*d^2+d+9)+5)/(4*(3*c+1)+1+4*(3*d)+1)$

$2*(12*(54*c^2+45*c+6*d^2+d+9)+5)-54*2*c*(4*(3*c+1)+1+4*(3*d)+1)+108*d*(4*(3*c+1)+1+4*(3*d)+1)-36*(4*(3*c+1)+1+4*(3*d)+1)=10*(12*d+1)^2$

$2*(12*(54*c^2+45*c+6*d^2+d+9)+5)-12*d*(4*(3*c+1)+1+4*(3*d)+1)+12*c*(4*(3*c+1)+1+4*(3*d)+1)+4*(4*(3*c+1)+1+4*(3*d)+1)=10*(4*(3*c+1)+1)^2$

$2*(12*(54*c^2+45*c+6*d^2+d+9)+5)/(4*(3*c+1)+1-(4*(3*d)+1))$

$2*(12*(54*c^2+45*c+6*d^2+d+9)+5)-108*c*(4*(3*c+1)+1-(4*(3*d)+1))-108*d*(4*(3*c+1)+1-(4*(3*d)+1))-54*(4*(3*c+1)+1-(4*(3*d)+1))=10*(12*d+1)^2$

$2*(12*(54*c^2+45*c+6*d^2+d+9)+5)+12*d*(4*(3*c+1)+1-(4*(3*d)+1))+12*c*(4*(3*c+1)+1-(4*(3*d)+1))+6*(4*(3*c+1)+1-(4*(3*d)+1))=10*(4*(3*c+1)+1)^2$

EDIT3:

Se fossero dimostrate le altre tre soluzioni significherebbe che $mcd(4*n+1,4*m+1,p)!=1$ se $p$ non è primo

[megas_archon]

Niente, non ci si riesce

[axpgn]

Il problema è che lui si impegna veramente tanto ma non si accorge che si trova in un vicolo cieco

[P_1_6]

$36*m^2+18*m+4*n^2+2*n+3=(p+1)/2 $

$p=(72*m^2+36*m+8*n^2+4*n+5)$

$(72*m^2+36*m+8*n^2+4*n+5) mod (4*m+1+4*n+1)$

$(72*m^2+36*m+8*n^2+4*n+5)-18*m*(4*m+1+4*n+1)+18*n*(4*m+1+4*n+1)=5*(4*n+1)^2$

$(72*m^2+36*m+8*n^2+4*n+5)-2*n*(4*m+1+4*n+1)+2*m*(4*m+1+4*n+1)=5*(4*m+1)^2$

$(72*m^2+36*m+8*n^2+4*n+5) mod (4*m+1-(4*n+1))$

$(72*m^2+36*m+8*n^2+4*n+5)-18*m*(4*m+1-(4*n+1))-18*n*(4*m+1-(4*n+1))-9*(4*m+1-(4*n+1))=5*(4*n+1)^2$

$(72*m^2+36*m+8*n^2+4*n+5)+2*n*(4*m+1-(4*n+1))+2*m*(4*m+1-(4*n+1))+1*(4*m+1-(4*n+1))=5*(4*m+1)^2$



solve integer $36*m^2+18*m+4*n^2+2*n+3=(12*x+5+1)/2$

$m$ può assumere tutti i valori

$n$ non può assumere i valori $n mod 3 = 2$


quindi dovrebbe essere possibile creare un generatore di non tutti i numeri primi nella forma $12*x+5$
eliminando $m=0$ ed $n=0$ ed $n mod 3 =2$ ed i numeri ove $mcd(4*n+1,4*m+1)!=1$

Edit: NO NON FUNZIONA questo sopra

[megas_archon]

E' proprio impenetrabile..

[P_1_6]

"megas_archon":E' proprio impenetrabile..

no non funziona

EDIT:
il doppio di un numero primo nella forma 12*x+5 si scrive in modo unico come somma di due quadrati

[megas_archon]

È pazzesco, sembra (è) un dialogo tra sordi

[hydro1]

"P_1_6":
il doppio di un numero primo nella forma 12*x+5 si scrive in modo unico come somma di due quadrati

Si’ questo è ovvio ed è vero più in generale per primi congrui ad 1 modulo 4. Quindi?

[P_1_6]

"hydro":[quote="P_1_6"]
il doppio di un numero primo nella forma 12*x+5 si scrive in modo unico come somma di due quadrati

Si’ questo è ovvio ed è vero più in generale per primi congrui ad 1 modulo 4. Quindi?[/quote]
Quindi la dimostrazione che ho fatto può essere sostituita con quella che dimostra questo fatto

[P_1_6]

Relativamente a questo post non OFFTOPIC

per alcuni numeri fattorizzabili $N=12*x+5=a^2+b^2$

dove conosciamo $a$ e/o $b$ allora la fattorizzazione avviene in tempo polinomiale

esempio $N=221=a^2+b^2=(-11)^2+(-10)^2$

$N=221$
,
$b^2=(d-a-1)*(d+a)$
,
$N=a^2+b^2$
,
$N=p*(2*d-p)$
,
$d=36*m^2+18*m+4*n^2+2*n+3$
,
$a=24*m*n+6*m+6*n+1$
,
$b=2*(3*m+n+1)*(6*m-2*n+1)$
,
$a=-11$

$-> $

$p=13$

Alcuni numeri di questo tipo sono:
$65,221,425,725,1025,1073,1961,2501,3125,...........$

https://www.academia.edu/120768905/Poly ... a_and_or_b

EDIT1:

se $(2*a+1)/3$ è primo non serve conoscere $a$ e\o $b$ perchè sicuramente $n=0$ o $m=0$
,
però se $(2*a+1)/3$ non è primo, può anche verificarsi che $n=0$ o $m=0$

ed un'altra cosa ci sono altri numeri al di fuori di $12*x+5$

[P_1_6]

"P_1_6":ho testato a mano fino a $1001$

ed ho notato che

se $12*x+5$ è primo ci sarà una sola soluzione

se $12*x+5$ non è primo

o non ci sono soluzioni

o ha più di una soluzione

o se ne ha una $(4*n+1)*(4*m+1)=S*T^2$
quest'ultima cosa può significare due cose (avrei bisogno di un campione maggiore)
o $mcd(4*n+1,4*m+1)!=1$
o $(4*n+1)=s*t^2$ o $(4*m+1)=s*t^2$

se sei un programmatore potresti verificare questo?

se la congettura è corretta

allora possiamo cercare in un certo range piccolo quanto vogliamo

esempio

supponiamo di voler vedere se $9929$ è primo

solve $(9929000000000000000001/1000000000000000000+1)/2>36*m^2+18*m+4*n^2+2*n+3>(9928999999999999999999/1000000000000000000+1)/2$

$->$

$-11 <= m <= 11$

$(9929+1)/2=36*m^2+18*m+4*n^2+2*n+3$

la sola soluzione intera in $-11 <= m <= 11$ è $m=-3$ ed $n=34$

$mcd(4*(-3)+1,4*34+1)=1$

quindi $9929$ è primo

abbiamo impiegato 23 passi

non so quanto efficiente possa essere questa cosa però a scopo educativo è interessante

[P_1_6]

Credo la migliore implementazione possibile sia:
- prendo due numeri $min$ e $max$ in input (che sono le estremità dell'intervallo I dove voglio cercare primi)
- creo una matrice $M[(max-min)/12][3]$ e la inizializzo a $0$
- mi calcolo l'intervallo di $m$ e per ogni $m$ mi calcolo l'intervallo di $n$
- quindi per ogni coppia $(m,n)$ nei rispettivi range mi calcolo $P=2*d-1=2*(36*m^2+18*m+4*n^2+2*n+3)-1$
- vado ad incrementare di $1$ , $M[(P-min)/12][0]$ , memorizzo $m$ in $M[(P-min)/12][1]$ , memorizzo $n$ in $M[(P-min)/12][2]$
- quando ho finito scorrerò la matrice e se questo valore $M[0] == 1$ farò $GCD(4*(M[1])+1,4*(M[2])+1)$ e se $MCD ==1$ stamperò $P=min+12*i$


Con questa implementazione impiegherò $(max-min)/12+D+(p+c)*(GCD)$ dove $D$ sono i doppioni e $p$ i numeri primi nell'interavllo e $c$ i numeri che si scrivono in modo unico ma che hanno $mcd!=1$

che ne pensate?

[P_1_6]

Per chi mastica anche informatica

L'ho implementato con la libreria gmp-6.3.0

https://github.com/Piunosei/lepore_sieve_4/tree/main

[P_1_6]

Credo che questo si possa migliorare

"P_1_6":
- mi calcolo l'intervallo di $m$ e per ogni $m$ mi calcolo l'intervallo di $n$

Calcolando direttamente le coppie $(m,n)$ valide risolvendo questa

$(max+1)/2>=36*m^2+18*m+4*n^2+2*n+3>=(min+1)/2$

[P_1_6]

"P_1_6":Per chi mastica anche informatica

L'ho implementato con la libreria gmp-6.3.0

https://github.com/Piunosei/lepore_sieve_4/tree/main

la complessità dell'algorimo che ho scritto è $O(sqrt(max))$ in particolare è $(sqrt(2*max-1)-3)/6*j+a*GCD$ dove $j$ in media è un po più grande di 1 [a certe condizioni], dove $a$ sono i potenziali primi che si scrivono in modo unico e $GCD$ il temo per il calcolo del massimo comun divisore

E' vero il temp dell'algoritmo AKS è $O((log p)^6)$ però per trovarne uno mentre per l'algoritmo che ho scritto io o ne trovi $1$ o $100000$ è sempre O(sqrt(max)) cambia poco [vedi immagini]

Quindi $sqrt(max)
$C>sqrt(max)/[(log max)^6]$ il mio crivello è più veloce di $AKS$

[P_1_6]

"Martino":Questi giorni sono occupato, ci torno sopra quando avrò tempo. Comunque ripeto che quella che hai scritto non è una dimostrazione, sembrano piuttosto righe di codice, ed è molto difficile decifrare di cosa stai parlando.

qui l'ho scritto spero abbastanza bene [aspetto tue nuove]

https://www.academia.edu/121400171/Siev ... y_interval