# How many solutions are there to $abc+def=ghi$, where $a,b,\ldots, h,i$ are distinct non-zero digits?

I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination.

-
Programming a computer is quite an easy solution – Hagen von Eitzen May 5 '13 at 17:52
I know, I did this in class on my Ti-84 calculator. I was wondering if it was possible to do it with only pen and paper had I not had my calculator with me. – Quaxton Hale May 5 '13 at 18:01
Some tricks can be used to make it easier; i.e. not filling in the first digit of A or B with 9, since that would make C < A or C < B – Xenon May 5 '13 at 18:01
You wouldn't have to try EVERY combination. There are some you can eliminate as impossible, e.g. if $A>500$ and $B>500$ (to echo @Sim). That cuts down on the computing time somewhat. – Ian Coley May 5 '13 at 18:20
I changed the title - hope it makes things clearer. – Mark Bennet May 5 '13 at 19:57

There are a total of $168$ solutions. Given the number of solutions, the best way out seems to be to write a small program to do this for you. Below are the $168$ triplets without ordering. With ordering there are $2 \times 168 = 336$ such triplets. \begin{array}{c|c|c} \text{First Number} & \text{Second number} & \text{Third number}\\ \hline\\ 124 & 659 & 783 \\ 125 & 739 & 864 \\ 127 & 359 & 486 \\ 127 & 368 & 495 \\ 128 & 367 & 495 \\ 128 & 439 & 567 \\ 129 & 357 & 486 \\ 129 & 438 & 567 \\ 129 & 654 & 783 \\ 129 & 735 & 864 \\ 134 & 658 & 792 \\ 135 & 729 & 864 \\ 138 & 429 & 567 \\ 138 & 654 & 792 \\ 139 & 428 & 567 \\ 139 & 725 & 864 \\ 142 & 596 & 738 \\ 142 & 695 & 837 \\ 143 & 586 & 729 \\ 145 & 692 & 837 \\ 146 & 583 & 729 \\ 146 & 592 & 738 \\ 152 & 487 & 639 \\ 152 & 784 & 936 \\ 154 & 629 & 783 \\ 154 & 638 & 792 \\ 154 & 782 & 936 \\ 157 & 329 & 486 \\ 157 & 482 & 639 \\ 158 & 634 & 792 \\ 159 & 327 & 486 \\ 159 & 624 & 783 \\ 162 & 387 & 549 \\ 162 & 783 & 945 \\ 163 & 782 & 945 \\ 167 & 328 & 495 \\ 167 & 382 & 549 \\ 168 & 327 & 495 \\ 173 & 286 & 459 \\ 173 & 295 & 468 \\ 175 & 293 & 468 \\ 176 & 283 & 459 \\ 182 & 367 & 549 \\ 182 & 394 & 576 \\ 182 & 457 & 639 \\ 182 & 493 & 675 \\ 182 & 754 & 936 \\ 182 & 763 & 945 \\ 183 & 276 & 459 \\ 183 & 492 & 675 \\ 183 & 546 & 729 \\ 183 & 762 & 945 \\ 184 & 392 & 576 \\ 184 & 752 & 936 \\ 186 & 273 & 459 \\ 186 & 543 & 729 \\ 187 & 362 & 549 \\ 187 & 452 & 639 \\ 192 & 384 & 576 \\ 192 & 483 & 675 \\ 192 & 546 & 738 \\ 192 & 645 & 837 \\ 193 & 275 & 468 \\ 193 & 482 & 675 \\ 194 & 382 & 576 \\ 195 & 273 & 468 \\ 195 & 642 & 837 \\ 196 & 542 & 738 \\ 214 & 569 & 783 \\ 214 & 659 & 873 \\ 215 & 478 & 693 \\ 215 & 748 & 963 \\ 216 & 378 & 594 \\ 216 & 738 & 954 \\ 218 & 349 & 567 \\ 218 & 376 & 594 \\ 218 & 439 & 657 \\ 218 & 475 & 693 \\ 218 & 736 & 954 \\ 218 & 745 & 963 \\ 219 & 348 & 567 \\ 219 & 438 & 657 \\ 219 & 564 & 783 \\ 219 & 654 & 873 \\ 234 & 657 & 891 \\ 235 & 746 & 981 \\ 236 & 718 & 954 \\ 236 & 745 & 981 \\ 237 & 654 & 891 \\ 238 & 419 & 657 \\ 238 & 716 & 954 \\ 239 & 418 & 657 \\ 241 & 596 & 837 \\ 243 & 576 & 819 \\ 243 & 675 & 918 \\ 245 & 673 & 918 \\ 245 & 718 & 963 \\ 245 & 736 & 981 \\ 246 & 573 & 819 \\ 246 & 591 & 837 \\ 246 & 735 & 981 \\ 248 & 319 & 567 \\ 248 & 715 & 963 \\ 249 & 318 & 567 \\ 251 & 397 & 648 \\ 254 & 619 & 873 \\ 254 & 637 & 891 \\ 257 & 391 & 648 \\ 257 & 634 & 891 \\ 259 & 614 & 873 \\ 264 & 519 & 783 \\ 269 & 514 & 783 \\ 271 & 593 & 864 \\ 271 & 683 & 954 \\ 273 & 546 & 819 \\ 273 & 591 & 864 \\ 273 & 645 & 918 \\ 273 & 681 & 954 \\ 275 & 418 & 693 \\ 275 & 643 & 918 \\ 276 & 318 & 594 \\ 276 & 543 & 819 \\ 278 & 316 & 594 \\ 278 & 415 & 693 \\ 281 & 394 & 675 \\ 281 & 673 & 954 \\ 283 & 671 & 954 \\ 284 & 391 & 675 \\ 291 & 357 & 648 \\ 291 & 384 & 675 \\ 291 & 546 & 837 \\ 291 & 573 & 864 \\ 293 & 571 & 864 \\ 294 & 381 & 675 \\ 296 & 541 & 837 \\ 297 & 351 & 648 \\ 314 & 658 & 972 \\ 317 & 529 & 846 \\ 317 & 628 & 945 \\ 318 & 627 & 945 \\ 318 & 654 & 972 \\ 319 & 527 & 846 \\ 324 & 567 & 891 \\ 324 & 657 & 981 \\ 327 & 519 & 846 \\ 327 & 564 & 891 \\ 327 & 618 & 945 \\ 327 & 654 & 981 \\ 328 & 617 & 945 \\ 329 & 517 & 846 \\ 341 & 586 & 927 \\ 342 & 576 & 918 \\ 346 & 572 & 918 \\ 346 & 581 & 927 \\ 352 & 467 & 819 \\ 354 & 618 & 972 \\ 354 & 627 & 981 \\ 357 & 462 & 819 \\ 357 & 624 & 981 \\ 358 & 614 & 972 \\ 362 & 457 & 819 \\ 364 & 527 & 891 \\ 367 & 452 & 819 \\ 367 & 524 & 891 \\ 372 & 546 & 918 \\ 376 & 542 & 918 \\ 381 & 546 & 927 \\ 386 & 541 & 927 \end{array} And here is the MATLAB code. (Not the most efficient one. Took 12 seconds to run on my comp to produce this list.)

clear all;
clc;
t=0;
for i=1:9
for j=1:9
for k=1:9
if (j~=i && k~=j && k~=i)
t       =   t+1;
A(t,1)  =   i;
A(t,2)  =   j;
A(t,3)  =   k;
A(t,4)  =   100*i+10*j+k;
end
end
end
end
count   =   0;
for k1=1:t
for k2=1:t
if(isempty(intersect(A(k1,1:3),A(k2,1:3))))
if(A(k1,4)<A(k2,4))
c          =   A(k1,4) + A(k2,4);
rowindex   =   find(A(:,4)==c);
if (~isempty(rowindex))
if(isempty(intersect(A(k1,1:3),A(rowindex,1:3))))
if(isempty(intersect(A(k2,1:3),A(rowindex,1:3))))
count      =   count+1;
B(count,:) =   [A(k1,4),A(k2,4),A(rowindex,4)];
end
end
end
end
end
end
end

-
Thank you! I've never used MatLab before. I got the same number of solutions on my calculator program (10~ minutes to calculate) – Quaxton Hale May 5 '13 at 21:21

Here's some simple and very fast MAGMA code which only tests permutations of $1,\ldots,9$, as opposed to all $9^9$ triplets of $3$-digit combinations. It ran in $3.042$ seconds on my computer.

Z := {@ 1,2,3,4,5,6,7,8,9 @};
S := SymmetricGroup(9);
X := GSet(S,Z);
sol := [];
for s in S do
Y := X^s;
A := Y[1]*100 + Y[2]*10 + Y[3];
B := Y[4]*100 + Y[5]*10 + Y[6];
C := Y[7]*100 + Y[8]*10 + Y[9];
if A + B eq C then
Append(~sol,Y);
end if;
end for;


We can make this faster, actually, by noticing that $g+h+i$ must be exactly equal to $18$. Furthermore, we can use a "carrying" method to rule out certain cases early. The following runs in $1.982$ seconds.

Z := {@ 1,2,3,4,5,6,7,8,9 @};
S := SymmetricGroup(9);
X := GSet(S,Z);
sol := [];
for s in S do
Y := X^s;
if Y[7] + Y[8] + Y[9] eq 18 then
u := Y[3] + Y[6];
if u mod 10 eq Y[9] then
v := Floor(u/10) + Y[2] + Y[5];
if v mod 10 eq Y[8] then
w := Floor(v/10) + Y[1] + Y[4];
if w eq Y[7] then
Append(~sol,Y);
end if;
end if;
end if;
end if;
end for;

-
Thanks! I've never heard of MAGMA before :o – Quaxton Hale May 5 '13 at 21:35
Actually, my MATLAB code doesn't do all the $9^9$ permutations. It first stores the numbers with distinct digits. Anyway, yours check is orders faster. +1. – user17762 May 5 '13 at 21:36
@user17762 Thanks! That sentence was a response not to your MATLAB code but to OP's request for code which "doesn't try every single combination." – Alexander Gruber May 5 '13 at 21:48