Each of A and B is a tridecimal (base 13) positive integer, where A is formed by writing the digit 4 precisely 666 times and, B is formed by writing the digit 6 precisely 666 times.

Determine the distinct digits that appear in the tridecimal representation of the product A*B.

Note: For an extra challenge, solve this problem using only pencil and paper.

list
   10   cls
   20   for Psn=0 to 665
   30      A=A+4*13^Psn
   40   next
   50   print A
   60   for Psn=0 to 665
   70      B=B+6*13^Psn
   80   next
   90   print B
  100   C=A*B
  105   Rw=40:Cl=79
  110   while C>0
  120     Dig=C @ 13
  130     C=C\13
  135     locate Cl,Rw
  140     print mid("0123456789abc",Dig+1,1)
  145   Cl=Cl-1:if Cl<0 then Cl=79:Rw=Rw-1
  150   wend
  155   locate 0,42
  160   print
OK

finds the product expressed as tridecimal, is

                            2222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
22222222222222222222222222222222222222222222222222222222222222222222222222222222
222222222222222222222222222222222222222222222222222221aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

where a represents ten and b is eleven.

So the distinct digits are 2, 1, A and B.

Partial explanation:

  44444...44444
X 66666...66666

 

In the usual multiplication algorithm, each line of partial product is derived:

4*6 = 24 decimal = 1B tridecimal, so the rightmost digit is B and there's a carry of 1.

The position to the left would also be a B, but the carry makes it a C, and there's still only a carry of 1. So this continues with C's all the way to the left (665 of them), and the final carry gets placed as a solitary 1.

Each successive partial product looks just the same, but offset to the left one position:

             1CCCCC...CCCCCB
            1CCCCC...CCCCCB
           1CCCCC...CCCCCB
          1CCCCC...CCCCCB
        ...  
   1CCCCC...CCCCCB
  1CCCCC...CCCCCB
 1CCCCC...CCCCCB
1CCCCC...CCCCCB

On the rhs, B is carried down to the final position. Then C +  B = A with a carry of 1. Then C+C+B+1 = A with a carry of 2, etc. In tridecimal the C is similar to the 9 in decimal acting like -1 mod the base, and being offset by the increased carry at each successive position.

The last time this works, though is the leftmost column that consists of all C's and a B -- the 666th row, where the B has shifted 665 positions to the left, to be directly under the first C in the first row.  The next column to the left then starts with a 1, has the same number of C's as the previous column, and no B. So compared to what we were expecting, the C has been replaced by a 1, and there is no B. Mod our base, replacing a C with a 1 is like going up 2. Eliminating the B is like going up another 2. Going four up from A (10) mod our base (13) brings us to the 1 that shows up in the middle of the product.

This is the point where I lose track of the carries, in explaining the series of 2's to the left.

       

Posted by Charlie on 2010-08-07 14:41:52