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

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 :big grin: :big grin: :big grin:
Bernhard

[QUOTE=bhelmes;472552]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 :big grin: :big grin: :big grin:
Bernhard[/QUOTE]

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.

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

[QUOTE=science_man_88;472555]I think you want your own blogarrhea area for this stuff.[/QUOTE]

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

[QUOTE=science_man_88;472555]
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.[/QUOTE]

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

Greetings from Germany
Bernhard

[QUOTE=bhelmes;472625]I sound interesting, but i did not get the mathematical explication or how to program it.[/QUOTE]

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.

[QUOTE=CRGreathouse;472628]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.[/QUOTE]

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

[QUOTE=CRGreathouse;472628]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.[/QUOTE]

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.

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.

[code]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[/code]

[QUOTE=science_man_88;472631]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.[/QUOTE]

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?

[QUOTE=CRGreathouse;472634]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?[/QUOTE]

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.

[QUOTE=science_man_88;472635]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.[/QUOTE]

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! :smile: