%%%%% diofantinita` e decimo problema di Hilbert %%%%%%%%%%%%%%%%%%%%%%% %=======util.pro======================================================== % SEMPLICI ROUTINE DI SERVIZIO: %======================================================================= % la capacita` di generare in successione i numeri naturali, % come anche le tuple di lunghezza prefissata di numeri naturali, e` % un presupposto fondamentale per lo studio della "listabilita`" %----------------------------------------------------------------------- % tuples(Length,Output): % a turno, Output diventa tutte le Length-uple distinte di naturali tuples(0,[]) :- !. % la tupla vuota e` una sola tuples(N,T) :- till(i,K), % il massimo della tupla spazi da 0 a i[rragiungibile] tuples(N,K,T). % le N-uple di naturali aventi per massimo K %------- % tuples(Length,Max,Output): % a turno, Output assume tutte le Length-uple distinte di naturali % (ove Length>0) aventi come massimo Max tuples(1,K,[K]) :- !. % se il massimo della 1-upla deve essere K tuples(N,Kp1,[H|T]) :- % se la lunghezza e` N>1 e il massimo e` Kp1>0 Nm1 is N-1, Kp1>0, K is Kp1-1, tuples(Nm1,Kp1,T), % le (N-1)-uple aventi per massimo Kp1... till(K,H). %..., piu`, in testa, un elemento H non eccedente K tuples(N,K,[K|T]) :- Nm1 is N-1, till(K,H), tuples(Nm1,H,T). % le (N-1)-uple il cui massimo e` al piu` K %------- % till(LimSup,Output): % a turno, Output prende tutti i valori da 0 a LimSup % N.B.: Quando LimSup non e` un naturale, si attiva la generazione % di tutti i naturali till(_,0). % 0 sta in ogni intervallo [..,H] till(H,Q) :- till(H,P), (P == H, !, fail; % ignora il max P fornito da chiamata ricorsiva Q is P+1 ). %======================================================================= % conta le variabili distinte che figurano nell'espressione poliadica X quanteVar(X,O) :- not( not( (qV(X,O), assert(qV(O))) ) ), retract(qV(O)). % qV/2: qV(V,1) :- var(V),!, V='_'. %% versione diadica: %% qV(I,0) :- atomic(I). %% qV(OpPQ,C) :- %% OpPQ =.. [_,P,Q], %% qV(P,CP), %% qV(Q,CQ), %% C is CP+CQ. %% variante poliadica: qV(T,N) :- T =.. [_|Argg], qV(Argg,0,N). % qV/3: qV([],N,N). qV([H|T],N,M) :- qV(H,N0), N1 is N+N0, qV(T,N1,M). %------- % varIn/2 stabilisce se % la variabile a secondo parametro figura nel primo parametro varIn('_',X) :- var(X), !, fail. varIn(V,X) :- var(V), var(X), !. varIn(T,X) :- T =.. [_|Argg], varInArgg(Argg,X), !. varInArgg([H|B],X) :- varIn(H,X); varInArgg(B,X). %=======rudimenti.pro=================================================== % Cenni di aritmetica elementare in Prolog %======================================================================= % il seguente predicato composto/3 cerca di decomporre in due fattori % non banali, che verranno restituiti come secondo e terzo % argomento, il suo primo argomento composto(A,B,C) :- till(A,B0), B is B0+2, (B*B>A, !, fail; 0 is A mod B, C is A // B). % consideriamo due numeri interi A,B, con A>0, B>0 coPrimi(A,B) :- 'MCD'(A,B,1). % A e B sono primi tra loro % massimo comun divisore e minimo comune multiplo: % algoritmo di Euclide per la ricerca del massimo comun divisore 'MCD'(X,0,D) :- iAbs(X, D), !. 'MCD'(X,Y,D) :- R is X mod Y, 'MCD'(Y,R,D). mcm(X,Y,M) :- XY is X*Y, iAbs(XY,AbsXY), 'MCD'(X,Y,D), M is AbsXY // D. % valore assoluto di un numero X: iAbs(X,AbsX) :- (AbsX is X, AbsX>=0; AbsX is -X), !. %----------------------------------------------------------------------- % il seguente predicato Prolog fornira` sempre almeno una scomposizione % del suo parametro, grazie a un celebre risultato di Lagrange del 1772 scomposizLagrange(A) :- scomposizLagrange(A,W,X,Y,Z), !, write(A), write('='), write(W), write('^2+'), write(X), write('^2+'), write(Y), write('^2+'), write(Z), write('^2'). % la clausola che per prima compare qui sotto, ora inibita e degradata % a commento, sarebbe stata sufficiente a specificare la scomposizione % di un numero naturale come somma di quattro quadrati, ma prescegliamo % le altre cinque clausole, in quanto esse meglio riflettono % l'idea-chiave della dimostrazione del teorema di Lagrange: %%scomposizLagrange(N,W,X,Y,Z) :- % naturale N in somma di 4 quadrati %% integer(N), N >= 0, till(N,M), %% tuples(4,M,[W,X,Y,Z]), N is W^2+X^2+Y^2+Z^2. scomposizLagrange(0,0,0,0,0). scomposizLagrange(1,0,0,0,1). scomposizLagrange(2,0,0,1,1). scomposizLagrange(A,W,X,Y,Z) :- composto(A,A1,A2), % se A=A1*A2 ... scomposizLagrange(A1,X1,X2,X3,X4), scomposizLagrange(A2,Y1,Y2,Y3,Y4), % ...allora possiamo sfruttare l'identita` di Eulero: idEulero(X1,X2,X3,X4,Y1,Y2,Y3,Y4,W0,X0,Y0,Z0), iAbs4(W0,X0,Y0,Z0,W,X,Y,Z). scomposizLagrange(A,W,X,Y,Z) :- % clausola per i numeri primi dispari: AA is (A-1) // 2, till(AA,X1), till(AA,X2), 0 is (X1*X1+X2*X2+1) mod A, lagrangeGiuAd1(A,X1,X2,1,0,W0,X0,Y0,Z0), iAbs4(W0,X0,Y0,Z0,W,X,Y,Z). lagrangeGiuAd1(A,X1,X2,X3,X4,Z1,Z2,Z3,Z4) :- B is (X1*X1+X2*X2+X3*X3+X4*X4) // A, ( B==1 -> Z1=X1, Z2=X2, Z3=X3, Z4=X4 ; F is B mod 2, B1 is B-F-1, B0 is 1 - (B-F) // 2, till(B1,YY1), Y1 is YY1+B0, 0 is (Y1-X1) mod B, till(B1,YY2), Y2 is YY2+B0, 0 is (Y2-X2) mod B, till(B1,YY3), Y3 is YY3+B0, 0 is (Y3-X3) mod B, till(B1,YY4), Y4 is YY4+B0, 0 is (Y4-X4) mod B, idEulero(X1,X2,X3,X4,Y1,Y2,Y3,Y4,U1,U2,U3,U4), V1 is U1 // B, V2 is U2 // B, V3 is U3 // B, V4 is U4 // B, lagrangeGiuAd1(A,V1,V2,V3,V4,Z1,Z2,Z3,Z4) ). % identita` di Eulero: idEulero(X1,X2,X3,X4,Y1,Y2,Y3,Y4,W,X,Y,Z) :- %% si ha che %% (X1^2+X2^2+X3^2+X4^2)*(Y1^2+Y2^2+Y3^2+Y4^2) %% = W^2+X^2+Y^2+Z^2, dove... W is X1*Y1+X2*Y2+X3*Y3+X4*Y4, X is X1*Y2-X2*Y1+X3*Y4-X4*Y3, Y is X1*Y3-X3*Y1-X2*Y4+X4*Y2, Z is X1*Y4-X4*Y1+X2*Y3-X3*Y2. % quaterna di valori assoluti: iAbs4(W0,X0,Y0,Z0,W,X,Y,Z) :- iAbs(W0,W), iAbs(X0,X), iAbs(Y0,Y), iAbs(Z0,Z). %=======algebretta.pro================================================== % equazioni diofantee classiche %======================================================================= % Implementazione del teorema cinese del resto % ... ... ... [DA AGGIUNGERE] ... ... ... % Implementazione del metodo di risoluzione di equazioni diofantee % lineari in due incognite % La teoria dice questo: % L'equazione A*X+B*Y=C (con A,B,C interi diversi da 0) % ha soluzione negli interi sse MCD(A,B) divide C. % Le soluzioni sugli interi modulo C sono % X=X0+B1*H, Y=Y0-A1*H % dove H varia sugli interi ed X0,Y0 e` una soluzione qualunque e % dove, posto % D=MCD(A,B), % abbiamo che % A=D*A1, B=D*B1. risolviDiofLin(A*X-B*Y=C) :- B1 is -B, risolviDiofLin(A*X+B1*Y=C). risolviDiofLin(A*X+B*Y=C) :- integer(A), integer(B), integer(C), A \== 0, B \==0, C\==0, 'MCD'(A,B,D), 0 is C mod D, A1 is A // D, B1 is B // D, C1 is C // D, till(i,Yabs), (Y0=Yabs; Y0 is (-Yabs)), 0 is (C1 - B1*Y0) mod A1, !, X0 is (C1-B*Y0) // A1, X=X0+B1*H, Y = Y0-A1*H. %======================================================================= % Risoluzione di equazioni diofantee in una sola variabile: se il % polinomio ha termine noto non nullo, ogni soluzione sara` un % divisore di tale numero; in caso contrario, una soluzione sara` 0, % e prima di cercare le altre si diminuira` il grado del polinomio % dividendolo per la potenza massima possibile dell'incognita. monoVar(Poly=0) :- incognita_noto(Poly,G,K,X), !, var(X), ( K=0 -> riduciPoly( Poly,G,X) ; risolviPoly(Poly,K,X) ). % riduciPoly/3: riduciPoly( _,_,0). % 0 e` soluzione per le equazioni senza termine noto riduciPoly(Poly,G,X) :- riduciPoly(Poly,G,Qoly,K), !, risolviPoly(Qoly,K,X). % riduciPoly/4: riduciPoly(Monom,_,C,C) :- ( var(Monom), C=1; Monom=C*X, var(X) ). riduciPoly(P+Q,G,P0+Q0,C) :- riduciPoly(P,G,P0,C), riduciPoly(Q,G,Q0,C). riduciPoly(P-Q,G,P0-Q0,C) :- riduciPoly(P,G,P0,C), riduciPoly(Q,G,Q0,C). riduciPoly(Poly,G,C*X^H0,K) :- ( Poly=X^H, C=1; Poly=C*X^H ), H0 is H-G, ( H0==0, K=C; true ). % risoluzione immediata di un'equazione Poly=0 dove Poly e` polinomio % in una sola incognita X ed e` dotato di termine noto risolviPoly(Poly,K,X) :- iAbs(K,C), (composto(C,A,B);A=1,B=C), ( X is -B; A\==B, X is -A; X=A; A\==B, X=B ), 0 is Poly. % incognita_noto(Poly,X,K,G): individua la variabile X nel dato % polinomio o, se ve n'e` piu' d'una, assimila tutte le var. fra % loro restituendo poi un'unica incognita X; inoltre individua il % termine noto K e determina (per lo meno quando il termine noto non % e` 0) il grado G del monomio di grado minimo. Il polinomio Poly % deve essere presentato come somma di monomi in cui al piu` uno dei % monomi ha il grado minimo e in cui ogni monomio e` dato nella % forma C*X^H, con C intero (sottinteso se 1), X variabile, ed H % intero positivo incognita_noto(Poly,G,K,X) :- incognita_noto(Poly,_,G,K,X). incognita_noto(X,_,1,_,X) :- var(X), !. incognita_noto(C*X,_,C,_,X) :- var(X), !. incognita_noto(K,_,_,K,_) :- integer(K). incognita_noto(P+Q,G0,G,K,X) :- incognita_noto(P,G0,G1,K,X), incognita_noto(Q,G1,G,K,X). incognita_noto(P-Q,G0,G,K,X) :- incognita_noto(P,G0,G1,K,X), incognita_noto(Q,G1,G,K,X). incognita_noto(X^H,G0,G,K,X) :- incognita_noto(1*X^H,G0,G,K,X). incognita_noto(C*X^H,G0,G,_,X) :- integer(C), C\==0, integer(H), H>0, ( (G0=H; H= G=H; G=G0 ). %======================================================================= % Ecco un classico sistema diofanteo: ternaPitag((X^2+Y^2=Z^2,X>0,Y>=X),[X,Y,Z]). % Stando all'enciclopedia Treccani, % la forma generale di una terna pitagorica e`: % X=K*A*B, Y=(K*(A^2-B^2))/2, Z=(K*(A^2+B^2))/2, % dove A,B sono dispari e primi tra loro. Implementiamo quest'idea: ternaPitagorica(X,Y,Z) :- tuples(3,[K0,A0,B0]), A0>B0, K is K0+1, A is 2*A0+1, B is 2*B0+1, coPrimi(A,B), AQ is A^2, BQ is B^2, X0 is K*A*B, Y0 is(K*(AQ-BQ))/2, Z0 is (K*(AQ+BQ))/2, (X0 X=X0, Y=Y0 ; X=Y0, Y=X0 ), Z=Z0. % N.B.: Se togliessimo il controllo "primiTraLoro(A,B)", troveremmo % ripetute certe terne pitagoriche, fra le quali: % 27, 36, 45; 54, 72, 90; 81, 108, 135; 108, 144, 180 %------- % Un frammento di Eraclito: % % Pitagora, figlio di Mnesarco, si dedico` alla ricerca piu` di tutti % gli altri uomini, e dopo aver raccolto libri su questo argomento % produsse una sapienza sua propria: molte nozioni per formare un'arte % ingannevole. %======================================================================= % Altra classica equazione diofantea: % Siamo interessati a determinare le soluzioni X,Y>=0 di % equazioni del tipo X^2-D*Y^2=1, dove D e` il predecessore di un % quadrato. Seguiamo la trattazione di [Dav73, pagg.239-240] isPellEq(X^2-(_^2-1)*Y^2=1) :- var(X), var(Y). pellEq(X^2-D*Y^2=1) :- var(X), var(Y), integer(D), D>2, A is sqrt(D+1), integer(A), (pellSol(D,0,0,X,Y); till(i,I), J is I+1, pellSol(D,J,I,X,Y)). pellSol(D,J,I,X,Y) :- (I=0;integer(I)), (J=0;integer(J),I2, A is sqrt(D+1), integer(A), pellSol(A,D,J,I,X,Y), !. %------- ausiliario dei precedenti due predicati pellSol(_,_,0,_,1,0). pellSol(A,_,1,_,A,1). pellSol(A,D,J,0,XJ,YJ) :- N is J // 2, pellSol(A,D,N,0,XN,YN), X2N is XN*XN+D*YN*YN, Y2N is 2*XN*YN, (0 is J mod 2 -> XJ=X2N, YJ=Y2N ; XJ is X2N*A+D*Y2N, YJ is A*Y2N+X2N). pellSol(A,D,J,N,XJ,YJ) :- M is J - N, pellSol(A,D,N,0,XN,YN), pellSol(A,D,M,0,XM,YM), XJ is XM*XN+D*YN*YM, YJ is XN*YM+XM*YN. % Nota storica: La forma generale delle equazioni di Pell e` % N*Y^2+1=X^2, % dove non e` richiesto che N sia immediato predecessore di un quadrato. % e ciascuna di esse ammette---come ben aveva visto Fermat---infinite % soluzioni. I primi studi documentati su queste equazioni sono % quelli degli indiani Brahmagupta (628dC) e Bhaskara II (1150 dC). % Brahmagupta scopri` il metodo "samasa" ("composizione") per % ottenere nuove soluzioni da soluzioni note: Se Y=a, X=b ed Y=c, X=d % sono soluzioni per le rispettive equazioni % N*Y^2+C=X^2, % N*Y^2+K=X^2 % (simili ad equazioni di Pell, ma con C, K al posto di 1), allora % Y=b*c+a*d, X=b*d+n*a*c ed Y=b*c-a*d, X=b*d-n*a*c % sono soluzioni per l'equazione % N*Y^2+C*K=X^2. %=======goedelizzaz.pro================================================= % Sintassi, grado, e codifica numerica dei polinomi diofantei %======================================================================= % calcolo del grado G di un polinomio diofanteo P (qui le variabili % del polinomio sono rappresentate con variabili logiche): grado(P,G) :- grd(P+0,G), !. % cavallo da tiro per la ricorsione % :sommare 0 serve a garantire l'esplicitazione del risultato G grd(C,0) :- integer(C). % le costanti hanno grado 0 grd(V,1) :- var(V). % incognite e parametri hanno grado 1 grd(P^N,G*N) :- grd(P,G), integer(N), N >= 0. % :l'esponente si moltiplica per il grado della base grd(P*Q,GP+GQ) :- grd(P,GP), grd(Q,GQ). % :grado di un prodotto di polinomi = somma dei gradi dei fattori grd(P+Q,G) :- grd(P,GP), grd(Q,GQ), (G is GQ, GP =< G; G is GP). % :grado di una somma di polinomi = max dei gradi degli addendi grd(P-Q,G) :- grd(P+Q,G). % :grado differenza di polinomi = max gradi minuendo e sottraendo %----------------------------------------------------------------------- % codifica numerica di un polinomio diofanteo [Dav73, p.260]: % Fissiamo un'enumerazione x_0, x_1, x_2,... % di tutte le variabilli. Ciascun naturale n codifica un polinomio % P_n a coefficienti interi positivi, se stabiliamo che % P_0=1 % P_{3\cdot i+1}=x_i % P_{3\cdot i+2}=P_{\ell(i)}+P_{r(i)} % P_{3\cdot i+3}=P_{\ell(i)}\cdot P_{r(i)} % dove \ell, r sono le proiezioni associate alla funzione % \langle n,m \rangle % di abbinamento di Cantor. % TEST: ?- poly(N,3*x1+x2^2),poly(N,Q),poly(M,Q). % N = 1646903 % Q = (1+ (1+1))*x1+x2*x2 % M = 1646903 natural(N) :- integer(N), N>=0. % Quando uno dei seguenti due predicati triang/2, cantor/3 % viene chiamato, il primo parametro (e nel caso di "cantor" % anche il secondo) puo` essere dato (cioe` istanziato ad un % numero naturale), ed allora l'ultimo parametro viene determinato % o quanto meno controllato; o altrimenti nessuno dei tre parametri % va dato, e in tal caso il predicato si comporta da generatore. % Nel caso di triang/2, e` previsto anche che la chiamata % fornisca come primo parametro N+1 (con N variabile, oppure % N intero >= -1), nel qual caso essa genera (grazie all' ausilio % della triang/3 i numeri triangolari dall'(N+1)esimo in poi. % l'N-simo numero triangolare e`... triang(N,T) :- natural(N), !, T is (N*(N+1)) // 2. % ...la somma T= 1+2+...+N triang(0,0). triang(Np1,TT) :- var(Np1), !, triang(N,T), Np1 is N+1, TT is T+Np1. triang(N+1,T) :- triang(N,T,_). triang(-1,0,0). triang(N,TT,NN) :- triang(N,T) , NN is N+1, TT is T+NN. triang(N,TT,NN) :- triang(N,T,N0), NN is N0+1, TT is T+NN. cantor(L,R,C) :- natural(L), !, LpR is L+R, triang(LpR,T), C is T+R. % La clausola che segue, ora degradata a commento, % sarebbe bastata a completare la definizione di % cantor/3, anche se ne venissero cancellati % (con notevole degrado delle prestazioni) % i sottogoal % F is floor(sqrt(2)*sqrt(C)), till(i,J), N is F+J % Preferiamo la (meno chiara) versione sottostante, perche` essa % concilia le buone prestazioni con l'indipendenza dal predicato till/2 %%cantor(L,R,C) :- %% F is floor(sqrt(2)*sqrt(C)), till(i,J), N is F+J, %% triang(N,T), (T==C -> L=N,R=0; T>C -> R is C-T+N, L is N-1-R), !. cantor(L,R,C) :- F is floor(sqrt(2)*sqrt(C))-1, triang(F,T,N), (T==C -> L=N,R=0; T>C -> R is C-T+N, L is N-1-R), !. % Qui la traduzione poly/2 di un polinomio in numero... poly(N,P) :- natural(N), !, M is N mod 3, (M==0 -> M1=3; M1=M), I is (N-M1) // 3, (N==0 -> P=1; M==1 -> name(I,S), [X] = "x", name(P,[X|S]) ; cantor(L,R,I), poly(L,PL), poly(R,PR), ( M==2 -> P=PL+PR; P=PL*PR )). % ... e qui la traduzione inversa, anch'essa rappresentata % dal predicato poly/2: % Ecco come codificare un intero positivo M: se M=1, la codifica e` 0; % altrimenti spezzo M come floor(M//2)+ceil(M//2), codifico separatam. % le due meta` ottenendo i numeri L ed R (soddisfacenti L=R oppure % triang(L,R)), dei quali formo l'abbinamento C di Cantor, che poi % triplico e infine incremento di 2. poly(N,M) :- natural(M), M>1, Q is M // 2, poly(L,Q), (0 is M mod 2 -> R=L; triang(L,T), R is 3*T+2), cantor(L,R,C), N is 3*C+2. % Altro costrutto derivato trattabile direttam., l'elevamento a potenza. % Per codificare l'elevamento ad M-esima potenza, spezzo M come % floor(M//2)+ceil(M//2), codifico separatamente P^Q (dove % Q=floor(M//2)) e se necessario P^Q*P, infine codifico P^Q*P^Q % oppure P^Q*(P^Q*P). poly(N,P^M) :- natural(M), M>1, Q is M // 2, (Q==1 -> poly(L,P); poly(L,P^Q)), ( 0 is M mod 2 -> R=L ; % Q1 is Q+1, poly(R,P^Q1) poly(J,P), cantor(L,J,K), R is 3*K+3 ), cantor(L,R,C), N is 3*C+3. poly(0,1). poly(N,Xi) :- atom(Xi), name(Xi,[X|S]), [X]="x", name(I,S), integer(I), N is 3*I+1. poly(N,P+Q) :- poly(L,P),poly(R,Q), cantor(L,R,C), N is 3*C+2. poly(N,P*Q) :- poly(L,P),poly(R,Q), cantor(L,R,C), N is 3*C+3. % Il seguente predicato implementa un'idea al momento scollata dal % resto: forse essa permettera` di abbassare i numeri codificanti % polinomio che involgono costrutti secondari quali l' esponenziazione. % spezza/2,3: spezza(1,1). spezza(M,P+Q) :- M>1, R is M mod 2, D is M //2, ( R == 0 -> spezza(D,P), Q=P ; spezza(D,P,Q) ). spezza(1,1,1+1). spezza(M,Q+P,P+S) :- M>1, R is M mod 2, D is M //2, ( R == 0 -> spezza(D,P,S), Q=P ; spezza(D,Q,P), S=P ). %=======diofantei.pro=================================================== % relazioni e funzioni diofantee sui numeri naturali %======================================================================= retrieveRelDiof(P,Q) :- proprDiofantea(P,R), retrieveRelDiof(R,Q). retrieveRelDiof(P,Q) :- retrieveFunDiof(P,Q). retrieveRelDiof([exs(_)|P],Q) :- retrieveRelDiof(P,Q). retrieveRelDiof((P1;P2),(Q1;Q2)) :- retrieveRelDiof(P1,Q1), retrieveRelDiof(P2,Q2). retrieveRelDiof((P1,P2),(Q1,Q2)) :- retrieveRelDiof(P1,Q1), retrieveRelDiof(P2,Q2). retrieveFunDiof(X=Y,X=Y) :- var(X), var(Y). retrieveFunDiof(Y=X,Q) :- var(X), retrieveFunDiof(X=Y,Q). retrieveFunDiof(F=G,(X=Y,Q,T)) :- nonvar(F), retrieveFunDiof(X=F,Q), retrieveFunDiof(Y=G,T). retrieveFunDiof(X=P^N, (X=Y^N,Q)) :- integer(N), N>0, retrieveFunDiof(Y=P,Q). retrieveFunDiof(P,Q) :- funzDiofantea(P,R), retrieveRelDiof(R,Q). retrieveFunDiof(X=P1-P2, (X=Y1-Y2,Q1,Q2)) :- retrieveFunDiof(Y1=P1,Q1), retrieveFunDiof(Y2=P2,Q2). retrieveFunDiof(X=P1+P2, (X=Y1+Y2,Q1,Q2)) :- retrieveFunDiof(Y1=P1,Q1), retrieveFunDiof(Y2=P2,Q2). retrieveFunDiof(X=P1*P2, (X=Y1*Y2,Q1,Q2)) :- retrieveFunDiof(Y1=P1,Q1), retrieveFunDiof(Y2=P2,Q2). retrieveFunDiof(X=N, X=N) :- integer(N). % nelle seguenti clausole definienti proprieta` e funzioni % diofantee, le variabili spaziano sui naturali proprDiofantea( =<(A,B ), _+A=B). % A e` minore o uguale a B proprDiofantea( \=(A,B ), =<(1,A-B)^2). % A e` diverso da B proprDiofantea( <(A,B ), =<(A+1,B)). % A e` minore di B proprDiofantea(comp(A), (X+2)*(_+X+2)=A). % A e` un No. composto proprDiofantea(divid(A,B ), _*A=B). % A e` divisore di B proprDiofantea(nivid(A,B ), =<(1,rem(B,A))). % A non divide B proprDiofantea(congr(A,B,C), rem(A,C)=rem(B,C)). % A = B (mod C) proprDiofantea(coprm(A,B ), 1=gcd(A,B)). % A e B sono primi tra loro proprDiofantea(pitag(A,B,C), ( % A,B,C formano una terna pitagorica fondamentale % (le terne pitagoriche generali sono multiple delle fondamentali) B00,Y>=X),P), insiemeDiofanteo(P=0,_). sys2polyDiof(Sys,Poly) :- sys2polyDiof(Sys,nats,Poly),!. sys2polyDiof(R=S, nats, (P-Q*_-R)^2+(Q-R-_-1)^2) :- nonvar(S), S=rem(P,Q). sys2polyDiof(R=S, nats, (2*R+_-Q)^2+((Q*_-P+R)*(Q*_-P-R))^2) :- nonvar(S), S=arem(P,Q). sys2polyDiof(P=Q,_,P) :- Q==0. sys2polyDiof(P=Q,_,P-Q). sys2polyDiof(P\=Q, nats, R^2-_-1) :- sys2polyDiof(P=Q,_,R). sys2polyDiof(P\=Q, ints, R^2-_^2+_^2+_^2+_^2-1) :- sys2polyDiof(P=Q,_,R). sys2polyDiof(P>=Q, nats, R-_) :- sys2polyDiof(P=Q,_,R). sys2polyDiof(P>=Q, ints, R-_^2+_^2+_^2+_^2) :- sys2polyDiof(P=Q,_,R). sys2polyDiof(P>Q, nats, R-_-1) :- sys2polyDiof(P=Q,_,R). sys2polyDiof(P>Q, ints, R-_^2+_^2+_^2+_^2-1) :- sys2polyDiof(P=Q,_,R). sys2polyDiof(divid(P,Q), nats, P*_-Q). sys2polyDiof((Eq;Fq),_,P*Q) :- sys2polyDiof(Eq,P), sys2polyDiof(Fq,Q). sys2polyDiof((Eq,Fq),omog,P1^GG1+P2^GG2) :- sys2polyDiof(Eq,P1), sys2polyDiof(Fq,P2), grado(P1,G1), G1\==0, GG2 is 2*G1, grado(P2,G2), G2\==0, GG1 is 2*G2. sys2polyDiof((Eq,Fq),_,Psq+Qsq) :- sys2polyDiof(Eq,P), sys2polyDiof(Fq,Q), polySq(P,Psq), polySq(Q,Qsq). polySq(Psq,Psq) :- polySq(Psq). polySq(P,P^2). polySq(P) :- var(P), !, fail. polySq(_^Q) :- Q==2. polySq(Q*Q). polySq(Psq+Qsq) :- polySq(Psq), polySq(Qsq). %======tania.pro======================================================== %======================================================================= % enumeratore generale soluzioni sistemi diofantei risolviDiofanteo(DiofId) :- DiofRetrieve =.. [DiofId,DiofSys,Params], % costruire chiamata... DiofRetrieve, % ...che rintraccia il sistema diofanteo sys2polyDiof(DiofSys,Poly), % convertire sistema in equaz. Poly=0 write('Risolvo '), write(Poly), nl, write(' rispetto alle incognite '), write(Params), nl, insiemeDiofanteo(Poly=0,Params), write(Params), nl, fail. % Ad es.: % ?- risolviDiofanteo(ternaPitag) % ?- risolviDiofanteo(comp) % ?- risolviDiofanteo(alphaSys) %------- valPosPolyDiofanteo(Poly,V) :- % trova tutti i possibili valori % (con naturali al posto delle % incognite) di un polinomio); % esponi i valori positivi quanteVar(Poly,N), % N e` il numero delle incognite tuples(N,T), % genera in seq, tutte le N-uple di naturali istanzia(Poly,T), % sostituiscile alle incognite valuta(Poly,V), % determina il val. corrispondente del polin. V>0. % accettalo se e` positivo % Ad es.: % ?- primiPoly(Poly), valPosPolyDiofanteo(Poly,Pr) %------- generaInsDiof(DiofSys,X0,V) :- % vale solo per i sottoinsiemi diofantei % dei naturali var(X0), % X0 e` il param. del sistema, che % assurge ad incognita, per cui deve varIn(DiofSys,X0), % comparire nel sistema... sys2polyDiof(DiofSys,Poly), % ...sistema che qui viene trasformato quanteVar(Poly,N), % in singolo polinomio... tuples(N,T), % ...che poi, Qoly = (X0+1)*(1-Poly^2)-1, % aggiustato con un "cheap trick",... istanzia(Qoly,T), valuta(Qoly,V), % ...viene valutato in ogni modo... V>=0. % ...per generare i naturali (non % i negativi) che ci interessano %------- % Esempio di utilizzo di "generaInsDiof": composto(C) :- comp(DiofSys,[X]), generaInsDiof(DiofSys,X,C). %======================================================================= % Fornire in input un'equazione diofantea e indicare la lista A dei % suoi parametri: ad es., il goal % ?- insiemeDiofanteo((X^2+Y^2-Z^2)^2+(X-U-1)^2+(Y-X-V)^2=0,A), % A=[X,Y,Z]. % Verranno generate tutte le tuple di valori per A facenti parte % di una soluzione; come caso particolare, l' esempio appena visto % ci fornira` le terne pitagoriche. % Altro esempio: % ?- B=4, insiemeDiofanteo(X^2-B*X*Y+Y^2=1,A),A=[X,Y]. insiemeDiofanteo(EquazDiofantea,Params) :- % equaz. diofantea da risolvere, di cui sono evidenziati i parametri insiemeDiofanteo(EquazDiofantea,Params,_). insiemeDiofanteo(Poly=Qoly,_,Max) :- ( Max=i -> true; true ), quanteVar(Poly-Qoly,N), % conta sia le incognite che i parametri ( N=0 -> T=[]; % caso banale till(Max,K), % il massimo della tupla spazi da 0 a K tuples(N,K,T)), % genera a turno tutte e N-uple di naturali istanzia(Poly-Qoly,T), % sostituisci ogni N-upla alle variabili valuta(Poly,V), % valuta il polin. ove hai sostituito le variabili valuta(Qoly,V). % valuta e accertati che il risultato sia uguale %======================================================================= % istanziazione di variabili presenti nell'espressione diadica X istanzia(X,Sost) :- istanzia(X,Sost,_). % terzo param. dara` sostituendi inutilizzati istanzia(_,[],[]) :- !. istanzia(V,[S|Sost],Sost) :- var(V),!, V=S. % istanzia ad S tutte le occorrenze di V istanzia(I,Sost,Sost) :- integer(I). istanzia(OpPQ,SSost,Sost) :- OpPQ =.. [_,P,Q], % :nel caso dei polinomi, l'operatore Op qui lasciato % anonimo dovra` soddisfare la condizione % (Op== '+' ; Op== '*' ; Op== '^' ; Op == '-') istanzia(P,SSost,Sostt), istanzia(Q,Sostt,Sost). %----------------------------------------------------------------------- % valutazione di un'espressione (es. polinomio o polinomio esponenziale) valuta(V,_) :- % variabile inattesa: si sarebbe dovuto gia` istanziarla var(V), abort. valuta(I,I) :- integer(I). valuta(OpPQ,V) :- OpPQ =.. [Op,P,Q], valuta(P,VP), valuta(Q,VQ), W =.. [Op,VP,VQ], V is W. %=======esemplari.pro=================================================== % sistemi diofantei di particolare interesse %======================================================================= % Banale: il sistema diofanteo che definisce i numeri composti puo` % venire definito come segue: comp((X*Y=C,X>=2,Y>=X),[C]). %----------------------------------------------------------------------- % Condizioni diofantee che caratterizzano l'insieme % { | B >=4 & alpha(B,C,A)} alphaSys((B>=4, U^2-B*U*T+T^2=1, S^2-B*S*R+R^2=1, S>R, divid(U^2,S), V=B*S-2*R, divid(V,W-B), divid(U,W-2), W>2, X^2-W*X*Y+Y^2=1, U>2*A, A=arem(X,V), C=arem(X,U)), [A,B,C]). % Condizioni diofantee che caratterizzano l'insieme % { | Alpha=Beta^U} davis71Sys( % Da [Dav71], pagg.142--144 (U+_-1=V, P+(A-1)*Q=V+_, G=V+_, P^2-(A^2-1)*Q^2=1, H+(A+1)*G=_*(P+(A+1)*Q)^2, H+(A-1)*G=_*(P+(A-1)*Q)^2, H^2-(A^2-1)*G^2=1, M=(H+(A+1)*G)*_+A, M=_*(P+(A-1)*Q)+1, _^2-(M^2-1)*Y^2=1, Y=(_-1)*(P+(A-1)*Q)+U, Y=(_-1)*(H+(A+1)*G)+V, W^2-(A^2-1)*V^2=1, W-V*(Alpha-Beta)=Alpha+(_-1)*(2*Alpha*Beta-Beta^2-1), Alpha+Delta=2*A*Beta-Beta^2-1, Beta+_=Eta, U+_=Eta, A^2-(Eta^2-1)*(Eta-1)^2*Delta^2=1 ), [Alpha,Beta,U]). %----------------------------------------------------------------------- % Condizioni diofantee che caratterizzano l'insieme % { | M=N^K} davis73Sys( % Da [Dav73], pagg.244--247; notare che qui si tratta di... ( % ...interi POSITIVI X^2-(A^2-1)*Y^2=1, U^2-(A^2-1)*V^2=1, S^2-(B^2-1)*T^2=1, V=_*Y^2, B=1+4*_*Y, B=A+_*U, S=X+_*U, T=K+4*(_-1)*Y, Y=K+_-1, (X-Y*(A-N)-M)^2=(_-1)^2*(2*A*N-N^2-1)^2, M+_=2*A*N-N^2-1, W=N+_, W=K+_, A^2-(W^2-1)*(W-1)^2*_^2=1 ), [M,N,K]). %----------------------------------------------------------------------- primiPoly( % polinomio di Jim Jones (University of Calgary, Canada), % che genera i numeri primi (v. [Mat93,pag.55]) (K*2)* (1 -(_*Z+H+J-Q)^2 -((G*K+2*G+K+1)*(H+J)+H-Z)^2 -(2*N+P+Q+Z-E)^2 -(16*(K+1)^3*(K+2)*(N+1)^2+1-_^2)^2 -(E^3*(E+2)*(A+1)^2+1-_^2)^2 -((A^2-1)*Y^2+1-X^2)^2 -(16*_^2*Y^4*(A^2-1)+1-U^2)^2 -(N+L+_-Y)^2 -(((A+U^2*(U^2-A))^2-1)*(N+4*_*Y)^2+1-(X+_*U)^2)^2 -((A^2-1)*L^2+1-M^2)^2 -(Z+P*L*(A-P)+_*(2*A*P-P^2-1)-P*M)^2 -(A*I+K+1-L-I)^2 -(Q+Y*(A-P-1)+_*(2*A*P+2*A-P^2-2*P-2)-X)^2 -(P+L*(A-N-1)+_*(2*A*N+2*A-N^2-2*N-2)-M)^2 ) ). %% TEST: %% ?- primiPoly(P), grado(P,G), quanteVar(P,V). %% ... %% G = 25 %% V = 26 %=======presburger.pro================================================== % aritmetica additiva dei numeri naturali (Presburger, 1929) %======================================================================= termPresburger(Xi) :- atom(Xi), name(Xi,[X|S]), [X]="x", name(I,S), integer(I), I>0. termPresburger(S+T) :- termPresburger(S), termPresburger(T). termPresburger(N*T) :- integer(N), N>0, termPresburger(T). termPresburger(S-T) :- termPresburger(S), termPresburger(T). % :questa e` una pseudo-sottrazione, i % termini negati andrebbero trasposti! atmPresburger(=(S,T)) :- termPresburger(S), termPresburger(T). atmPresburger(<(S,T)) :- termPresburger(S), termPresburger(T). atmPresburger(=<(S,T)) :- termPresburger(S), termPresburger(T). atmPresburger(divid(N,T)) :- natural(N), termPresburger(T). atmPresburger(congr(S,T,N)) :- natural(N), termPresburger(S), termPresburger(T). litPresburger(=(S,T), =(S,T)) :- termPresburger(S), termPresburger(T). litPresburger(\=(S,T), X) :- termPresburger(S), termPresburger(T), ( X = <(S,T) ; X = <(T,S) ). litPresburger(=<(S,T), X) :- termPresburger(S), termPresburger(T), ( X = <(S,T) ; X = =(S,T) ). litPresburger(not(=<(S,T)), <(T,S)) :- termPresburger(S), termPresburger(T). litPresburger(<(S,T), <(S,T)) :- termPresburger(S), termPresburger(T). litPresburger(not(<(S,T)), X) :- termPresburger(S), termPresburger(T), ( X= <(T,S); X = =(T,S) ). litPresburger(divid(0,T),=(0,T)) :- termPresburger(T). litPresburger(divid(1,T),=(0,0)) :- termPresburger(T). litPresburger(divid(N,T),congr(T,0,N)) :- integer(N), N>1, termPresburger(T). litPresburger(nivid(0,T),<(0,T)) :- termPresburger(T). litPresburger(nivid(1,T),=(0,1)) :- termPresburger(T). litPresburger(nivid(N,T),congr(T,I,N)) :- integer(N), N>1, termPresburger(T), Nm2 is N-2, till(Nm2,J), I is J+1. litPresburger(not(divid(N,T)),X) :- litPresburger(nivid(N,T),X). litPresburger(congr(S,T,0),=(0,1)) :- termPresburger(S), termPresburger(T). litPresburger(congr(S,T,1),=(0,0)) :- termPresburger(S), termPresburger(T). litPresburger(congr(S,T,N),congr(S,T,N)) :- integer(N), N>1, termPresburger(S), termPresburger(T). litPresburger(not(congr(S,T,0)),=(0,0)) :- termPresburger(S), termPresburger(T). litPresburger(not(congr(S,T,1)),=(0,1)) :- termPresburger(S), termPresburger(T). litPresburger(not(congr(S,T,N)),congr(S,T+I,N)) :- integer(N), N>1, termPresburger(S), termPresburger(T), Nm2 is N-2, till(Nm2,J), I is J+1. %%% SOLO UN ESORDIO, QUESTO, DA COMPLETARE !!!!!!!!!!!!!!!!!!!! %=======================================================================