Bilinear Forms in CLP(FD) ?

[j4n bur53]

Dear All,

I wonder if there are CLP(FD) around, that can detect
factoring problems, and maybe divert to specialize
routines that factor numbers.

This simple constraint is:

?- X*Y #= 100.

Labeling could proceed by specialized factoring routines.
The more complex constraint seems to be of the form,
and thus would need some massaging by

the CLP(FD) system:

?- A*X*Y+B*X+C*Y #= D.

Bye

See also:
Lee, E. J. "Amicable Numbers and the Bilinear Diophantine Equation."
http://dx.doi.org/10.1090/S0025-5718-1968-0224543-9

[Ulrich Neumerkel]

j4n bur53 <janb...@fastmail.fm> writes:
>Dear All,
>
>I wonder if there are CLP(FD) around, that can detect
>factoring problems, and maybe divert to specialize
>routines that factor numbers.
>
>This simple constraint is:
>
>?- X*Y #= 100.
>
>Labeling could proceed by specialized factoring routines.

Do you expect:

| ?- X*Y #= 100.
clpz:(X*Y#=100),
clpz:(X in-100\/ -50\/ -25\/ -20\/ -10\/ -5.. -4\/ -2.. -1\/1..2\/4..5\/10\/20\/25\/50\/100),
clpz:(Y in-100\/ -50\/ -25\/ -20\/ -10\/ -5.. -4\/ -2.. -1\/1..2\/4..5\/10\/20\/25\/50\/100).

[burs...@gmail.com]

Thats not labeling, thats domains.
I wouldn't touch the domains.

[burs...@gmail.com]

Maybe a labeling API would be useful...
Where one can hook in special enumerations...

[burs...@gmail.com]

Hi,

There is a proof by Euler, that Formats Last Theorem
FLT is true for n=3. In his proof there is all kind
of reasoning.

At one point he reasons about cubics. Something
along when p^3 = a*b, then a=u^3*c and b=v^3*d
and c*d=w^3. Right?

Anyway: Some extension could also handle multiplication
constraints with exponents. Like for example:

X*Y^2 = 9529569

Because 9529569 = 3^4*7^6, this would give two new
constraints:

N1+2*M1 = 4

N2+2*M2 = 6

And the result would be:

X = 3^N1*7^N2

Y = 3^M1*7^M2

Its like 30-times faster:

?- [X,Y] ins 1..9529569, X*Y^2 #= 9529569, time((label([X,Y]), fail; true)).
% 263,673 inferences, 0.067 CPU in 0.068 seconds (99% CPU, 3917933 Lips)

?- [N1,M1,N2,M2] ins 0..6, N1+2*M1 #= 4, N2+2*M2 #= 6, time((label([N1,M1,N2,M2]), X #= 3^N1*7^N2, Y #= 3^M1*7^M2, fail; true)).
% 5,712 inferences, 0.002 CPU in 0.002 seconds (98% CPU, 2586957 Lips)

Have a Nice day!

P.S.: Here you see that both approaches give the same solutions:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.5.8)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- use_module(library(clpfd)).
true.

?- [X,Y] ins 1..9529569, X*Y^2 #= 9529569, label([X,Y]).
X = 1,
Y = 3087
X = 9,
Y = 1029
X = 49,
Y = 441
X = 81,
Y = 343
X = 441,
Y = 147
X = 2401,
Y = 63
X = 3969,
Y = 49
X = 21609,
Y = 21
X = 117649,
Y = 9
X = 194481,
Y = 7
X = 1058841,
Y = 3
X = 9529569,
Y = 1.

?- [N1,M1,N2,M2] ins 0..6, N1+2*M1 #= 4, N2+2*M2 #= 6, label([N1,M1,N2,M2]), X #= 3^N1*7^N2, Y #= 3^M1*7^M2.
X = 1,
Y = 3087 ;
X = 49,
Y = 441 ;
X = 2401,
Y = 63 ;
X = 117649,
Y = 9 ;
X = 9,
Y = 1029 ;
X = 441,
Y = 147 ;
X = 21609,
Y = 21 ;
X = 1058841,
Y = 3 ;
X = 81,
Y = 343 ;
X = 3969,
Y = 49 ;
X = 194481,
Y = 7 ;
X = 9529569,
Y = 1.

[burs...@gmail.com]

Multiplication constraint, of the form .. = constant,
would be reduced to factoring the constant and
new addition constraints, of the form .. = constant.

Hell, Yeah!

[burs...@gmail.com]

If the CLP(FD) were clever, it would answer:

?- 2*X^3 #= Y^3.

Immediately with the following solution:

X = Y, Y = 0.

Why, and why?

Am Sonntag, 3. September 2017 13:32:57 UTC+2 schrieb j4n bur53: