Re: What puzzles me, discovery ignored

On Sep 7, 10:12 pm, Enrico <ungerne...@xxxxxxx> wrote:
On Sep 7, 11:58 am, Mark Murray <w.h.o...@xxxxxxxxxxx> wrote:





Enrico wrote:
I've got a couple of Excel speadsheets that will let you plug in
numbers and see what happens. You will need to have the Greatest
Common Divisor function GCD(X, Y) working - can't remember if GCD
came with the original Excel package or with one of those mysterious
"Add-Ins"

Yikes! :-) I don't do Excel.

It would be safer to receive a text - only explanation. I can pull
comments off the spreadsheets and organize them a bit to the point
where you should be able to try your own calculations. This will
take a few days - I'll have to remove variable name conflicts between
my stuff and JSH's

I can email the text-only stuff or post it here.
Let me know which one you want.

Text is vastly preferable. Please do both, if that is OK?

If your reply-to: is set, may I email you my real email address?

My intention is to code the work as (probably) C++, and then give
it a hammering (pun intended). C++ means I can then trivially modify
the code if I need to start using bignums by using operator
overloading.

There is another constraint that can be used to
limit the choices for x and y.
Ah, useful!

The constraint is: (2*x + 1) divides (2*y +1)^2 -1

Does James mention that anywhere?

Also - I'm more interested in the Diophantine solutions than in
factoring. Does James actually have a general solution, or is
your decryption of his work focussing on factorisation?

M
--
Mark Murray

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

If your reply-to: is set, may I email you my real email address?

I got one from James, so it should be working.

The constraint is: (2*x + 1) divides (2*y +1)^2 -1

Does James mention that anywhere?

No. James' factorization method relates to forms like:

    P^2 - D*Q^2 = R^2

where D is an odd number to be factored.
My method involved the dot (scalar) product of a pair of vectors,
each of which contain 3 terms, any one of which can be calculated
from the other two. I found a way to convert them to the Pell - like
form above, but its not too obvious.

Also - I'm more interested in the Diophantine solutions than in
factoring. Does James actually have a general solution, or is
your decryption of his work focussing on factorisation?

I've been assuming that it's general because I can start with a
factorization, generate two equations of the form:

a x2 + b xy + c y2 + dx + ey + f = 0

and see that James' method correctly solves each for (x+y)

There are probably equations that I cannot generate from a
factorization, but have solutions. I haven't looked into this.
James mentions a solution existence check, so I have some reason
to think his solution is general. (I have not proved this!)

I'll write up a procedure to let you generate the pairs of
diophantine equations and see James' solution method work.
I expect to have it ready to post sometime tomorrow.

                              Enrico- Hide quoted text -

- Show quoted text -

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

Mark - Check this with numeric values before you start writing
long C programs. Its mostly cut and paste from a functioning
spead***, but there's always the chance of mistyping during
editing or commenting.


Example: Factorization, 2 variable diophantine equations, Pell
equations

A=7
B=18
C=23
X=15
Y=19
Z=12

R=2*A*C - B^2 = -2
S = A*X + B*Y + C*Z = 723
D = S^2 + R = 723^2 - 2 = 522727 = 463 * 1129

Two Pell - like equations can be written:

r(v)^2 -D*s(v)^2 = t(v)^2
(S*X + C)^2 - D*X^2 = (Y*C + X*B)^2
10868^2 - 522727 * 15^2 = 707^2
GCD(ABS(r(v)+t(v)),ABS(D)) = 463
GCD(ABS(r(v)-t(v)),ABS(D)) = 1129
Take the GDC of these two and divide out
any common factor to get the factors of D
463 * 1129 = 522727 = D

r(v)^2 -D*s(v)^2 = t(v)^2
(S*Z + A)^2 - D*Z^2 = (Y*A + Z*B)^2
8683^2 - 522727 * 12^2 = 349^2
GCD(ABS(r(v)-t(v)),ABS(D)) = 463
GCD(ABS(r(v)+t(v)),ABS(D)) = 1129
Take the GDC of these two and divide out
any common factor to get the factors of D
463 * 1129 = 522727 = D

James goes on about rational solutions to the Pell Equation.
Rational solutions for the Pell Equation with D can be
gotten by dividing out t(v)^2 from r(v)^2 - D*s(v)^2 = t(v)^2

James uses Pell - like equations written as:
r(v)^2 - D*s(v)^2 = t(v)^2
I have attempted to duplicate this below:

The following two transform pairs on (A, B, C) and (X, Y, Z)
use quadratic functions of v and
preserve the values of D, S, 2*X*Z - Y^2, and 2*A*C - B^2
while changing the values in the Pell Equation

Using the example above,
U(0) = (X, Y, Z) = (15,19,12)
T(0) = (A, B, C) = (7,18,23)

let v = -1 (Domain is integers)

First pair:

Z <= Z
Y <= -2*Z*v + Y
X <= 2*Z*v^2 - 2*Y*v + X

C <= 2*A*v^2 + 2*B*v + C
B <= 2*A*v + B
A <= A

U(-1) = (77,43,12)
T(-1) = (7, 4 1)

Second pair:

Z <= 2*X*v^2 - 2*Y*v + Z
Y <= -2*X*v + Y
X <= X

C <= C
B <= 2*C*v + B
A <= 2*C*v^2 + 2*B*v + A

U(-1) = (15, 49, 80)
T(-1) = (17, -28, 23)

Notice that the dot product of U(v) and T(v) remains unchanged
You can take your starting values of U and T and apply one of the
transforms with any integer value of v, then apply the other transform
to the result with a new value of v, then go back to the first
transform
with yet another value of v, etc - alternating transforms and using
any
value of v each time and stopping at the end of any transform.

The factorizations will remain unchanged,
but the Pell - like equations will change.



Part 2 - Using (X, Y, Z) and (A, B, C) to generate equations
of the form c1*x^2 + c2*x*y+ c3*y^2 + c4 + c5*x + c6*y = 0
and showing James' method giving correct solutions as (x + y)

Note: X ,Y, Z, A, B, C are different variables than x, y, z, a, b, c

Problem - Factor D^2 + R = 723 ^ 2 - 2
Surrogate is (A + B) ^ 2 - (B ^ 2 - 2 * A * C) = 25 ^ 2 - 2

(Surrogate is small, has the same form as D^2 + R, namely R =
-2)


You can use the transform pairs to pump it up if you want.
The factors of the surrogate are A and 2*(B + C) + A

A=7
B=18
C=23

X, Y, Z values are unknown and are to be found such that
S = A*X + B*Y + C*Z = 723

X is odd
Y is odd
Z is a multiple of 4

Y ^ 2 - 2 * X * Z = 1

Define new variables x, y, z
x = (X - 1) / 2
y = (Y - 1) /2
z = Z / 4

Use A, B, C, and S to set up a diophantine equation to find x and y

4*A*x^2+4*B*x*y+2*C*y^2+2*(2*A+B-S)*x+2*(B+C)*y+A+B-S = 0
28*x^2 + 72*x*y +46*y^2 - 1382*x + 82*y - 698 = 0
Dividing out the 2's gives

14*x^2 + 36*x*y + 23*y^2 -691*x + 41*y - 349 = 0

c1 = 14
c2 = 36
c3 = 23
c4 = -349
c5 = -691
c6 = 41

James' solution method uses the variable names A, B, C, and S,
so I will assign new values for them:

A = (c2 - 2c1)^2 + 4c1(c2 - c1 - c3)
B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3)
C = (c6 - c5)^2 + 4c4(c2 - c1 - c3).

A(x+y)^2 + B(x+y) -S^2 + C = 0

rearrage terms:

A(x+y)^2 + B(x+y) + C = S^2

A = 8
B = 14476
C = 537220

x+y = 16 gives S = 878

by trial and error, find that x = 7 and y = 9 give

X = 2 * x + 1 = 15
Y = 2 * y + 1 = 19
Z = (Y^2 -1) / 2*X = 12

Using the original values for A, B, C = 7, 18, 23 redefine
S:
S = A*X + B*Y + C*Z = 723
and the factorization is done as in the example at the beginning
using

(S*X + C)^2 - D*X^2 = (Y*C + X*B)^2
or
(S*Z + A)^2 - D*Z^2 = (Y*A + Z*B)^2


A second diophantine equation can be set up to find y and z
using the original values:
A=7
B=18
C=23
S = 723

32*C*z^2+16*B*z*y+4*A*y^2+8*(B-S)*z+4*A*y+0 = 0
Divide out the common factor 4:
8*C*z^2+4*B*z*y+A*y^2+2*(B-S)*z+A*y = 0

184*z^2 + 72*z*y + 7*y^2 - 1410*z +7*y = 0

c1 = 184
c2 = 72
c3 = 7
c4 = 0
c5 = -1410
c6 = 7

James' solution method uses the variable names A, B, C, and S,
so I will assign new values for them:

A = (c2 - 2c1)^2 + 4c1(c2 - c1 - c3)
B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3)
C = (c6 - c5)^2 + 4c4(c2 - c1 - c3).

A(z+y)^2 + B(z+y) -S^2 + C = 0

rearrage terms:

A(z+y)^2 + B(z+y) + C = S^2

A = 32
B = -167704
C = 2007889

z + y = 12 gives S = 7

by trial and error, find that z = 3 and y = 9 give

Z = 4 * z = 12
Y = 2 * y + 1 = 19
X = (Y^2 - 1) / (2*Z) = 15

Which are the same values of X, Y, and Z found the first time.

One important thing I have not checked is the question of
have many solutions exist for each these diophantine equations.



Enrico
.

Loading