All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Too many fours and sixes (Posted on 2010-08-07)
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.

 No Solution Yet Submitted by K Sengupta Rating: 3.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution and partial explanation | Comment 1 of 4
`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   printOK`

finds the product expressed as tridecimal, is

`                            222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222221aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab`

where a represents ten and b is eleven.

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

Partial explanation:

`  44444...44444X 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...CCCCCB1CCCCC...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

 Search: Search body:
Forums (0)