The Modonacci Puzzle
Solution

Puzzle 1: Prove that M is a rational number. Solution provided by Yuen-Yick Kwan

For any positive index i, denote the i-th Modonacci digit as x and its successors as y and z. The value z depends only on x and y: 

        z = x + y mod 10
There are exactly 100 distinct pairs of digits (x,y) that are possible. Therefore, on or before the time we compute the 103-rd digit, some pair of values (x,y) must have been occurred twice, that is, starting at indices i1 and i2. But that means that the sequences beginning with locations i1 and i2 must be digit for digit identical indefinitely. This in turn implies that, at least by this point, the decimal quantity M has become a recurring decimal, with a period of at most |i2-i1|, and hence M represents a rational number.

Puzzle 2: Write M as P/Q.

Digit by digit calculation shows that M repeats after the 60th digit: 

        M = 0.112358314594370774156178538190998752796516730336954932572910
              112358314594370774156178538190998752796516730336954932572910
              11235831...
so 
        R = 0.112358314594370774156178538190998752796516730336954932572910

        S = 1.000000000000000000000000000000000000000000000000000000000001
              000000000000000000000000000000000000000000000000000000000001
              0000000...

        M = R * S

        10^60*S - S = 10^60

        10^60*R*S - R*S = 10^60*R

        M = R*S = S*10^60 / ( 10^60 - 1 )
          = 112358314594370774156178538190998752796516730336954932572910
          / 999999999999999999999999999999999999999999999999999999999999.

Back to The Modonacci Puzzle.

Last revised on 27 March 2011.