Friday, July 8, 2011

A lovely pattern

    1 x 8 + 1 = 9 
   12 x 8 + 1 = 98
  123 x 8 + 1 = 987
 1234 x 8 + 1 = 9876
12345 x 8 + 1 = 98765

The proof is via this reddit comment.

Theorem:

[12...n] x (b-2) + n = [(b-1)(b-2)...(b-n)]  

Notation [12..n] means a number written out as such.

  [12...n] x (b-2) + n
= [12...n] x b - [12...(n-1)n] - [12...n] + n   (1)
= [12...n0] - [12...(n-1)0] - [12...n]          (2)
= [11...10] - [12...n]                          (3)
= [(b-1)(b-2)...(b-n)]                          (4)
  1. a × (b-2) is the same as a × b - a - a.
  2. Multiplying a digit in base b by b shifts it left by 1, so [12…n] × b is [12…n0]. Also note that subtracting n from [12…n] will give you [12…0]. The n-1 was added to clarify.
  3. As a concrete example: 1230-120 = 1110
  4. As a concrete example: 1110-123 = 987

0 comments:

Post a Comment