gcd (f(n), g(n))>1 ?

[bhelmes]

A peaceful evening for all,

if i have to quadratic function f(n) and g(n) with
f(n) =an^2+bn+c and
g(n)=en^2+fn+g and i want to find a t>1 with
t=gcd (f(n), g(n)) for n=1 to n_max

Is there a better way than

for n=1 to n=n_max
if ((gcd (f(n), g(n))>1) print (n)
end_for;

If someone knows a better way, it would be nice to leave a short message.

Greetings from the primes
Bernhard

[science_man_88]

Originally Posted by bhelmes

A peaceful evening for all,

if i have to quadratic function f(n) and g(n) with
f(n) =an^2+bn+c and
g(n)=en^2+fn+g and i want to find a t>1 with
t=gcd (f(n), g(n)) for n=1 to n_max

Is there a better way than

for n=1 to n=n_max
if ((gcd (f(n), g(n))>1) print (n)
end_for;

If someone knows a better way, it would be nice to leave a short message.

Greetings from the primes
Bernhard

I think you want your own blogarrhea area for this stuff. and you can take a general remainder of the two and evaluate that at n and get the gcd possibly quicker using two smaller gcds.

[CRGreathouse]

I think the gcd of f(n) and g(n) must divide the resultant of f and g. Does that help?

[bhelmes]

Originally Posted by science_man_88

I think you want your own blogarrhea area for this stuff.

Would be nice,
i think i will follow the subject of prime distribution concerning quadratic irreducible polynomials

Originally Posted by science_man_88

and you can take a general remainder of the two and evaluate that at n and get the gcd possibly quicker using two smaller gcds.

I sound interesting, but i did not get the mathematical explication or how to program it.


Greetings from Germany
Bernhard

[CRGreathouse]

Originally Posted by bhelmes

I sound interesting, but i did not get the mathematical explication or how to program it.

I think he's just saying you can start with Euclid's algorithm on the pair of polynomials as a start. You can reduce the size of the coefficients or -- if you're lucky -- even the degree without loss of generality.

But I'm not sure how much time you want to spend optimizing this process since probably you'll just have to try a few values to get a common factor, and that should be pretty fast with quadratics unless the coefficients are gigantic.

[bhelmes]

Originally Posted by CRGreathouse

I think he's just saying you can start with Euclid's algorithm on the pair of polynomials as a start. You can reduce the size of the coefficients or -- if you're lucky -- even the degree without loss of generality.

But I'm not sure how much time you want to spend optimizing this process since probably you'll just have to try a few values to get a common factor, and that should be pretty fast with quadratics unless the coefficients are gigantic.

i choose two interesting quadratic function, for m=137 i can calculate up to 10^11 in 500 min on a single core and calculate the two function and make a gcd. I think there should be a speedup possible.

m=137 is the exponent for the mersenne number =
32032215596496435569.5439042183600204290159

Greetings from the primes
Bernhard

[science_man_88]

Originally Posted by CRGreathouse

I think he's just saying you can start with Euclid's algorithm on the pair of polynomials as a start. You can reduce the size of the coefficients or -- if you're lucky -- even the degree without loss of generality.

But I'm not sure how much time you want to spend optimizing this process since probably you'll just have to try a few values to get a common factor, and that should be pretty fast with quadratics unless the coefficients are gigantic.

yeah I was mostly thinking subtraction of coefficients because you can calculate a basic remander of one by the other. Of course, you can use the coefficients to eliminate possible n for overlap, or at very least show if it's odd or even. etc. anyways all this probably wastes more time than needed to do the actual calculations.

[CRGreathouse]

Ah, you're looking for *all* values giving a nontrivial gcd up to some limit? Yes, there are big speedups available. Here's the basic idea; there are lots of optimizations available but I have no time to show them.

commonFactorSmall(f, g, start, end)=
{
  my(v=List(),x=variable(f),y=variable(g));
  for(n=ceil(start),end, if(gcd(subst(f,x,n),subst(g,y,n))>1, listput(v,n)));
  Vec(v);
}

commonFactor(f, g, start, end)=
{
  my(r=polresultant(f,g),u,v,d);
  if(end-start < r, return(commonFactorSmall(f, g, start, end)));
  u=commonFactorSmall(f, g, start, start+r-1);
  v=List(u);
  u=concat(u, u[1]+r);
  d=vector(#v,i,u[i+1]-u[i]);
  forstep(n=u[#u],end,d, listput(v,n));
  Vec(v);
}

\\ Example
P=32*x^2-17*x+4;Q=17*x^2+8*x+6;
v=commonFactor(P,Q,1,10^7);#v

[CRGreathouse]

Originally Posted by science_man_88

yeah I was mostly thinking subtraction of coefficients because you can calculate a basic remander of one by the other. Of course, you can use the coefficients to eliminate possible n for overlap, or at very least show if it's odd or even. etc. anyways all this probably wastes more time than needed to do the actual calculations.

It's definitely a useful thing to do and would speed up calculations. Maybe you'd like to modify my code to use this optimization, and then show how much faster you can make it?

[science_man_88]

Originally Posted by CRGreathouse

It's definitely a useful thing to do and would speed up calculations. Maybe you'd like to modify my code to use this optimization, and then show how much faster you can make it?

a small example 3n^2+5n+4 is always even ; 5n^2+6n+13 is odd if x is even, and even if x is odd. so for t=2 we have that n is odd. With the subtraction we get 2n^2+n+9 which is odd when n is even and even if n is odd.edit: of course we then can continue this and get n^2+4n-5 and then we can get n^2-3n+14 then ( for certain n values at least) 7n-19. etc.

[CRGreathouse]

Originally Posted by science_man_88

a small example 3n^2+5n+4 is always even ; 5n^2+6n+13 is odd if x is even, and even if x is odd. so for t=2 we have that n is odd. With the subtraction we get 2n^2+n+9 which is odd when n is even and even if n is odd.

Take it a little further. A common divisor of 3n^2+5n+4 and 5n^2+6n+13 must divide (5n^2+6n+13) - (3n^2+5n+4) = 2n^2+n+9 but it must also divide (3n^2+5n+4) - (2n^2+n+9) = n^2+4n-5 and also (2n^2+n+9) - 2*(n^2+4n-5) = n^2-3n+14 and so (n^2+4n-5) - (n^2-3n+14) = 7n-19. Now you've reduced one of the quadratics to a linear polynomial without losing or gaining any factors (unless I've been sloppy).

But try to code whatever you do!