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

Question

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.

Answer 1

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

Answer 2

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;