Thursday, June 23, 2011

Missing digits

Given that 37! = 13763753091226345046315979581abcdefgh0000000, determine, with a minimum of arithmetical effort, the digits a, b, c, d, e, f, g, and h.  No calculators or computers allowed!

1 comment:

  1. Solution:

    Skip restatement of puzzle.Given that 37! = 13763753091226345046315979581abcdefgh0000000, determine, with a minimum of arithmetical effort, the digits a, b, c, d, e, f, g, and h. No calculators or computers allowed!
    Determine the number of trailing zeroes

    Consider the prime factorization of 37!
    We have 37! = 2n × 58 × m, where n greater than or equal to 8 and m is an integer not divisible by 5.
    Hence 37! is divisible by 28 × 58 = 108, but not by 109.

    Therefore 37! ends in precisely eight zeroes, and so h = 0.
    Determine g

    Next we calculate g by means of the following observation: g = 37! / 108 (mod 10.)
    We may divide 37! by 108 = 28 × 58 by dividing each multiple of 5 by all of its factors of 5, as well as removing an additional factor of 28 by striking out 2 = 21, 8 = 23, and 16 = 24.
    Hence g = 3 × 4 × 1 × 6 × 7 × 9 × 2 × 11 × 12 × 13 × 14 × 3 × 17 × 18 × 19 × 4 × 21 × 22 × 23 × 24 × 1 × 26 × 27 × 28 × 29 × 6 × 31 × 32 × 33 × 34 × 7 × 36 × 37 (mod 10.)
    = 3 × 4 × 1 × 6 × 7 × 9 × 2 × 1 × 2 × 3 × 4 × 3 × 7 × 8 × 9 × 4 × 1 × 2 × 3 × 4 × 1 × 6 × 7 × 8 × 9 × 6 × 1 × 2 × 3 × 4 × 7 × 6 × 7 (mod 10.)
    = 3 × 4 × 6 × 7 × 9 × 2 × 2 × 3 × 4 × 3 × 7 × 8 × 9 × 4 × 2 × 3 × 4 × 6 × 7 × 8 × 9 × 6 × 2 × 3 × 4 × 7 × 6 × 7 (mod 10.)

    We may now multiply term-by-term, reducing mod 10 as we go.
    We begin: 3 × 4 = 2 (mod 10), 2 × 6 = 2 (mod 10), 2 × 7 = 4 (mod 10), and so on.

    After 27 such multiplications (mod 10), we obtain g = 4.
    Determine a, b, c, d, e, and f
    We now have 37! = 13763753091226345046315979581abcdef400000000
    = 13,763,753,091,226,345,046,315,979,581,abc,def,400,000,000

    Note that 1001 = 7 × 11 × 13 and 999 = 33 × 37.
    Hence 999999 = 1001 × 999 = 33 × 7 × 11 × 13 × 37, and so 37! is divisible by 999999.

    Further, since (106)n = 1n = 1 (mod 999999), the sum of the digits of 37!, grouped six at a time beginning with the units digit, is congruent to 0 (mod 999999.)
    (If we consider each group of six digits as a single digit, this is the base 106 equivalent of the familiar base 10 test for divisibility by 9.)

    So we have 000000 + (100000d + 10000e + 1000f + 400) + (581000 + 100a + 10b + c) + 315979 + 345046 + 091226 + 763753 + 13 = 0 (mod 999999.)
    Hence 100000d + 10000e + 1000f + 100a + 10b + c = 902580 (mod 999999.)

    Since 0 less than or equal to a, b, c, d, e, f less than or equal to 9, it follows that d = 9, e = 0, f = 2, a = 5, b = 8, c = 0.

    Putting the results together, we have a = 5, b = 8, c = 0, d = 9, e = 0, f = 2, g = 4, h = 0.

    ReplyDelete