Me miró, mi programa para mostrar lo positivo de los números primos representado por una forma indefinida es bastante corta. Voy a poner una breve demostración de ejecutar a continuación, el programa completo. El método se debe a John Horton Conway, en el capítulo uno de su pequeño libro de La Sensual Forma Cuadrática. Otro libro fue muy útil con el diagrama ("topograph"), John Stillwell, Elementos de Teoría de los números, especialmente las páginas 38-39, 90-100.
Vale la pena énfasis: a primera vista, el problema de la búsqueda de los números con pequeño valor absoluto representado por una forma cuadrática indefinida parece desordenado, no podemos simplemente enlazadas las variables. Conway topograph método se convierte la imagen a su alrededor; no es un "río" a lo largo de los cuales los valores de la forma de la repetición para siempre. Entonces, cuanto más nos alejamos del río, el más grande de los valores absolutos de conseguir. Un lado del río es de números (primitivo) representados. Resulta ser un conjunto finito de árboles de raíces, donde las raíces son lugares en el río. Los valores de la forma no están en la gráfica de vértices o los bordes, en lugar de los valores en los espacios entre los bordes. Cada espacio en el río tiene un "nivel" de distancia del río, en comparación con los valores a lo largo del mismo río. En cada nivel, se obtiene un valor con el mínimo (valor absoluto) para ese nivel. Una vez que lo hacemos lo suficientemente capas para que mínimo para superar el límite queríamos, hemos terminado. Determinista y definitiva.
jagy@phobeusjunior:~$ g++ -o Conway_Positive_Primes Conway_Positive_Primes.cc -lm
In file included from /usr/include/c++/4.8/backward/strstream:51:0,
from Conway_Positive_Primes.cc:12:
/usr/include/c++/4.8/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp]
#warning \
^
jagy@phobeusjunior:~$ ./Conway_Positive_Primes 1 1 -2 50 13
1 1 -2 original form
square discriminant 9
jagy@phobeusjunior:~$ ./Conway_Positive_Primes 1 1 -3 50 13
1 1 -3 original form
1 3 -1 Lagrange-Gauss reduced
Represented (positive) primes up to 50
3 13 17 23 29 43
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
these are the collection of remainders when dividing by 13
0 3 4 10
Represented (positive) primes up to 50 and value mod 13
1 1 -3 original form
jagy@phobeusjunior:~$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <strstream>
using namespace std;
// this file is named Conway_Positive_Primes.cc
// main writing June 2014
// to compile
// g++ -o Conway_Positive_Primes Conway_Positive_Primes.cc -lm
void insert_primitive_reps(unsigned int a, unsigned int h, unsigned int b, unsigned int M, set<unsigned int> *setPtr)
{
// cout << setw(12) << a << setw(12) << h << setw(12) << b << " insert_primitive_reps" << endl;
if ( a <= M )
{
(*setPtr).insert(a);
if ( b <= M )
{
(*setPtr).insert(b);
if ( a <= M - b && h <= M - a - b)
{
if( a <= M - a - h ) insert_primitive_reps(a, h + 2 * a, a + b + h, M, setPtr);
if( b <= M - b - h ) insert_primitive_reps(a + b + h, h + 2 * b,b, M, setPtr);
// comment: once a+b+h <= M, min(2a+h, 2b+h) <= M
} // if a + b + h
} // if b
} // if a
} // end insert_primitive_rep
int IntSqrt(int i)
{
// cerr << "called intsqrt with " << i << endl;
if ( i <= 0 ) return 0;
else if ( i <= 3) return 1;
else if ( i >= 2147395600) return 46340;
else
{
float r;
r = 1.0 * i;
r = sqrt(r);
int root = (int) ceil(r);
while ( root * root <= i ) ++root;
while ( root * root > i ) --root;
return root ;
}
}
string stringify(int x)
{
ostringstream o;
o << x ;
return o.str();
}
string Factored(unsigned int i)
{
string fac;
fac = " = ";
int p = 2;
unsigned int temp = i;
if (temp < 0 )
{
temp *= -1;
fac += " -1 * ";
}
if ( 1 == temp) fac += " 1 ";
if ( temp > 1)
{
int primefac = 0;
while( temp > 1 && p * p <= temp)
{
if (temp % p == 0)
{
++primefac;
if (primefac > 1) fac += " * ";
fac += stringify( p) ;
temp /= p;
int exponent = 1;
while (temp % p == 0)
{
temp /= p;
++exponent;
} // while p is fac
if ( exponent > 1)
{
fac += "^" ;
fac += stringify( exponent) ;
}
} // if p is factor
++p;
} // while p
if (temp > 1 && primefac >= 1) fac += " * ";
if (temp > 1 ) fac += stringify( temp) ;
} // temp > 1
return fac;
} // Factored
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;
}
}
int main(int argc, char *argv[])
{
if ( argc != 6) cout << "Usage: ./Conway_Positive_Primes A B C Bound Modulus " << endl;
else {
int a,b,c, discr;
int N,M;
a = atoi(argv[1]);
b = atoi(argv[2]);
c = atoi(argv[3]);
M = atoi(argv[4]);
N = atoi(argv[5]);
cout << setw(12) << atoi(argv[1]) << setw(12) << atoi(argv[2]) << setw(12) << atoi(argv[3]) << " original form " << endl << endl;
int d = b * b - 4 * a * c ;
int droot = IntSqrt(d) ;
if ( d <= 0) cout << "nonpositive discriminant " << d << endl << endl;
if (d == droot * droot) cout << "square discriminant " << d << endl << endl;
if (d > 0 && d != droot * droot)
{
int aa,bb,cc;
while ( a <= 0 || c >= 0 || b <= abs(a+c) )
{
int delta, cAbs;
cAbs = c;
if (cAbs < 0) cAbs *= -1;
delta = (b + droot)/( 2 * cAbs) ;
if (c < 0) delta *= -1;
aa = c ; bb = 2 * c * delta - b ; cc = c * delta * delta - b * delta + a ;
a = aa; b = bb; c = cc;
} // while not reduced with a > 0
cout << setw(12) << a << setw(12) << b << setw(12) << c << " Lagrange-Gauss reduced " << endl << endl;
int a_old = a;
int b_old = b;
int c_old = c;
int goon = 1;
set<unsigned int> S;
while (goon )
{
int newval = a+b+c;
if ( newval > 0 )
{
// cout << setw(65) << b + 2 * a << endl;
insert_primitive_reps(a, b + 2 * a,newval ,M, &S); // note ampersand
b+= 2 * c ;
a = newval;
} // newval > 0
else if ( newval < 0 )
{
// cout << setw(5) << -1 * ( b + 2 * c) << endl;
b+= 2 * a ;
c = newval;
} // newval < 0
goon = (a != a_old) || (b != b_old) || (c != c_old) ;
} // while goon
cout << endl << endl << " Represented (positive) primes up to " << M << endl << endl;
set<unsigned int> mods ;
int rount = 0;
set<unsigned int>::iterator iterU;
for(iterU = S.begin() ; iterU != S.end() ; ++iterU)
{
unsigned int p = *iterU;
if ( p > 1 && PrimeQ(p) )
{
cout << setw(6) << p ;
++rount;
if (rount % 10 == 0 ) cout << endl;
// cout << setw(12) << p << setw(12) << p % N << endl ;
mods.insert( p % N);
} // if prime
}
int count = 0;
cout << endl << endl;
cout << "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= " << endl;
cout<< " these are the collection of remainders when dividing by " << N << endl << endl;
for(iterU = mods.begin() ; iterU != mods.end() ; ++iterU )
{
int u = *iterU ;
++count;
{
cout << setw(7) << u ;
if (0 == count % 10) cout << endl;
}
} // for iterU
cout << endl << endl;
cout << endl << endl << " Represented (positive) primes up to " << M << " and value mod " << N << endl << endl;
cout << setw(12) << atoi(argv[1]) << setw(12) << atoi(argv[2]) << setw(12) << atoi(argv[3]) << " original form " << endl << endl;
} // not square
} // else argc
return 0 ;
} // end of program
// g++ -o Conway_Positive_Primes Conway_Positive_Primes.cc -lm
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
0 votos
Representado (positivo) primos, por la forma principal, hasta 5000: 283 293 433 541 569 577 719 787 941 1097 1187 1429 1451 1531 1579 1663 1867 2003 2029 2083 2203 2339 2551 2671 2693 2999 3023 3083 3089 3253 3257 3271 3593 3607 3643 3779 3877 4021 4127 4253 4339 4409 4457 4517 4643 4793 4937