Subject: Re: Diophantic Equation System Date: 24 Feb 2000 19:53:57 GMT From: israel@math.ubc.ca (Robert Israel) "Thomas Lichtenberg" writes: > I worry about a numerical problem like: > ABCD + EFGH = KLBK > : - + > LL + EFFC = EFDL > = = = > EGA x AH = DGFG > Where every letter represents a single number. You mean each letter is a digit 0 to 9? A single equation of this type is called an alphametic, so I guess this would be a system of alphametics. Since there are only 10! = 3628800 possible assignments of letters to digits, even a brute-force search would be a feasible method, and it's easy to write programs that do a somewhat more intelligent search. I have an alphametic solver applet on the Web at http://www.geocities.com:80/CapeCanaveral/Campus/7705/metic/metic.html. You could make a system into a single equation by e.g. looking at the sum of the squares of the differences of the two sides of the equations: (ABCD+EFGH-KLBK)^2+(LL+EFFC-EFDL)^2+(EGA*AH-DGFG)^2=0. However, a complicated equation such as this might take the applet a long time. Here's a Maple program that will handle a system of alphametics (presented as a set or list of equations): ----------------------- alphametics:= proc(L) `metic/solve`([seq(op(`metic/parse`(expr)),expr=L)],{}, {0,1,2,3,4,5,6,7,8,9}); end; `metic/parse`:= proc(expr) local base,e,n,j; global `metic/forbid`; `metic/forbid`:= {}; e:=collect(`metic/expand`(expr,base),base); n:= degree(e,base); [seq(coeff(e,base,j), j=0..n)] end; `metic/expand`:= proc(expr,b) local L,n,j; global `metic/forbid`; if type(expr,{`+`,`*`,`^`}) then map(`metic/expand`,expr,b) elif type(expr,equation) then map(`metic/expand`,lhs(expr)-rhs(expr),b) elif type(expr,name) then `metic/forbid`:= `metic/forbid` union {substring(expr,1..1)}; n:= length(expr); add(b^(n-j)*substring(expr,j..j),j=1..n); else expr fi end; `metic/solve`:= proc(L,sofar,freedigs) local first,vars,n,nl,p,z,sub,v; global `metic/forbid`; first:= L[1]; nl:= nops(L); vars:= convert(indets(first),list); n:= nops(vars); for p in combinat[permute](freedigs,n) do if not(member(0,p,'z') and member(vars[z],`metic/forbid`)) then sub:= zip((x,y)->(x=y),vars,p); v:= subs(sub,first); if v mod 10 = 0 then if nl=1 then if v = 0 then print([op(sub),op(sofar)]) fi else `metic/solve`(subs(sub,L[2..nl])+[v/10,0\$nl-2], [op(sub),op(sofar)], freedigs minus convert(p,set)); fi fi fi od end; ------------------------- For your system: > alphametics([ABCD+EFGH = KLBK, LL+EFFC=EFDL, EGA*AH=DGFG]); [E = 1, A = 3, L = 2, F = 4, G = 7, C = 0, B = 8, D = 6, H = 9, K = 5] Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2