Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Interview question: find solution to x! + y! + z! = x * y * z

    • 7 Comments

    I stumbled on hmlee's algorithm chart quite by chance.  A lot of good questions in there.

    Question 53 caught my eye as a mathematician.

    Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC (where ABS is a three digit numbers, not A * B * C). Find A, B, and C that satisfies this equation.

    Interesting. But I'd like to modify the question a little.

    Q53': Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = A * B * C.
    Find A, B, and C that satisfies this equation.

    Astute readers will notice that A, B, and C are interchangeable.  Nonetheless there is a unique solution (modulo swapping A, B, and C.)

    I'm much less interested in the answer to this question (I know the answer) than I am in the quality of the program used to find the answer.  (I tried finding the answer by hunt-and-peck, then gave up and wrote a program - I find the program to be more interesting than the answer.)  Try to find the solution as efficiently as possible (without cheating.)

    I'll post my program later.

    If you see a fact, try to see it as intuitively as possible.

    I suspect that the following even more general problem has the same unique solution, which would be very interesting indeed.  This is the kind of thing where programs fail, and the mathematical mind becomes necessary again:

    Q53'': Say you have three integers that are >= 0. You have the equation: A! + B! + C! = A * B * C.
    Find A, B, and C that satisfies this equation.

  • Matthew van Eerde's web log

    Solution: x! + y! + z! = x * y * z

    • 0 Comments
    Last time I discussed the fact that there is a single, unique, solution to the formula x ! + y ! + z ! = x * y * z, where x, y, and z are non-negative integers.  I asked for a computer program to find the solution given that x, y, and z are all <= 9 but I wondered aloud whether the solution was unique without that constraint.

    The part where a computer can't help is the uniqueness.  Here is a mathematical proof that there are no solutions if any of x, y, or z are >= 6:

    Assume without loss of generality that x >= y => z.  The following two inequalities hold trivially, since we're dealing with non-negative numbers:

    x ! + y ! + z ! > x !
    x * y * z <= x 3

    Here's where 6 comes in:

    Lemma: for x >= 6, x ! > x 3 (proof momentarily.)

    If this lemma were true, then we'd be done... for x >= 6,

    x ! + y ! + z ! > x ! > x 3 >= x * y * z

    So a search for solutions for x ! + y ! + z ! = x * y * z can be restricted to 5 >= x >= y >= z.  This is computationally feasible.
    By inspection, there is a unique solution (see later in this post.)

    Proof of lemma: first, look at values of x ! and x 3 for x = 0 through 7:

    0! = 1 > 0 = 03
    1! = 1 = 1 = 13
    2! = 2 < 8 = 23
    3! = 6 < 27 = 33
    4! = 24 < 64 = 43
    5! = 120 < 125 = 53
    6! = 720 > 216 = 63
    7! = 5040 > 343 = 73


    It's not immediately clear how to progress.  The key idea, as often in geometric-ish progressions: look at successive ratios.  The initial 0 messes things up a bit, so we'll start with x = 1.

    On the left, numbers advance by a factor of:

    (x + 1)! / x ! = x + 1

    Note this ratio gets bigger and bigger.

    On the right, numbers advance by a factor of

    (x + 1)3 / x 3 = ((x + 1) / x)3 = (1 + (1 / x))3
    Note this rate of increase actually gets smaller.

    The crossover point - where x ! stops losing ground and begins to catch up - is x = 3;

    1 + 1 = 2 < 8 = (1 + (1/1))3
    2 + 1 = 3 < 3.375 = (1 + (1/2))3
    3 + 1 = 4 > 2.370370... = (1 + (1/3))3

    By x = 6, the lost ground has been made up, and x ! never looks back. QED.

    By the proof above, it only remains to look at the finite number of cases where x, y, and z are all <= 5.  Here they all are: note that in addition to the unique solution for the equality

    x ! + y ! + z ! = x * y * z

    there are only four solutions to the inequality

    x ! + y ! + z ! < x * y * z

    All of the other cases have

    x ! + y ! + z ! > x * y * z.

    0! + 0! + 0!
    = 3 > 0 =
    0 * 0 * 0
     
    1! + 0! + 0!
    = 3 > 0 =
    1 * 0 * 0
    1! + 1! + 0!
    = 3 > 0 =
    1 * 1 * 0
    1! + 1! + 1!
    = 3 > 1 =
    1 * 1 * 1
     
    2! + 0! + 0!
    = 4 > 0 =
    2 * 0 * 0
    2! + 1! + 0!
    = 4 > 0 =
    2 * 1 * 0
    2! + 1! + 1!
    = 4 > 2 =
    2 * 1 * 1
    2! + 2! + 0!
    = 5 > 0 =
    2 * 2 * 0
    2! + 2! + 1!
    = 5 > 4 =
    2 * 2 * 1
    2! + 2! + 2!
    = 6 < 8 =
    2 * 2 * 2
     
    3! + 0! + 0!
    = 8 > 0 =
    3 * 0 * 0
    3! + 1! + 0!
    = 8 > 0 =
    3 * 1 * 0
    3! + 1! + 1!
    = 8 > 3 =
    3 * 1 * 1
    3! + 2! + 0!
    = 9 > 0 =
    3 * 2 * 0
    3! + 2! + 1!
    = 9 > 6 =
    3 * 2 * 1
    3! + 2! + 2!
    = 10 < 12 =
    3 * 2 * 2
    3! + 3! + 0!
    = 13 > 0 =
    3 * 3 * 0
    3! + 3! + 1!
    = 13 > 9 =
    3 * 3 * 1
    3! + 3! + 2!
    = 14 < 18 =
    3 * 3 * 2
    3! + 3! + 3!
    = 18 < 27 =
    3 * 3 * 3
     
    4! + 0! + 0!
    = 26 > 0 =
    4 * 0 * 0
    4! + 1! + 0!
    = 26 > 0 =
    4 * 1 * 0
    4! + 1! + 1!
    = 26 > 4 =
    4 * 1 * 1
    4! + 2! + 0!
    = 27 > 0 =
    4 * 2 * 0
    4! + 2! + 1!
    = 27 > 8 =
    4 * 2 * 1
    4! + 2! + 2!
    = 28 > 16 =
    4 * 2 * 2
    4! + 3! + 0!
    = 31 > 0 =
    4 * 3 * 0
    4! + 3! + 1!
    = 31 > 12 =
    4 * 3 * 1
    4! + 3! + 2!
    = 32 > 24 =
    4 * 3 * 2
    4! + 3! + 3!
    = 36 = 36 =
    4 * 3 * 3
    4! + 4! + 0!
    = 49 > 0 =
    4 * 4 * 0
    4! + 4! + 1!
    = 49 > 16 =
    4 * 4 * 1
    4! + 4! + 2!
    = 50 > 32 =
    4 * 4 * 2
    4! + 4! + 3!
    = 54 > 48 =
    4 * 4 * 3
    4! + 4! + 4!
    = 72 > 64 =
    4 * 4 * 4
     
    5! + 0! + 0!
    = 122 > 0 =
    5 * 0 * 0
    5! + 1! + 0!
    = 122 > 0 =
    5 * 1 * 0
    5! + 1! + 1!
    = 122 > 5 =
    5 * 1 * 1
    5! + 2! + 0!
    = 123 > 0 =
    5 * 2 * 0
    5! + 2! + 1!
    = 123 > 10 =
    5 * 2 * 1
    5! + 2! + 2!
    = 124 > 20 =
    5 * 2 * 2
    5! + 3! + 0!
    = 127 > 0 =
    5 * 3 * 0
    5! + 3! + 1!
    = 127 > 15 =
    5 * 3 * 1
    5! + 3! + 2!
    = 128 > 30 =
    5 * 3 * 2
    5! + 3! + 3!
    = 132 > 45 =
    5 * 3 * 3
    5! + 4! + 0!
    = 145 > 0 =
    5 * 4 * 0
    5! + 4! + 1!
    = 145 > 20 =
    5 * 4 * 1
    5! + 4! + 2!
    = 146 > 40 =
    5 * 4 * 2
    5! + 4! + 3!
    = 150 > 60 =
    5 * 4 * 3
    5! + 4! + 4!
    = 168 > 80 =
    5 * 4 * 4
    5! + 5! + 0!
    = 241 > 0 =
    5 * 5 * 0
    5! + 5! + 1!
    = 241 > 25 =
    5 * 5 * 1
    5! + 5! + 2!
    = 242 > 50 =
    5 * 5 * 2
    5! + 5! + 3!
    = 246 > 75 =
    5 * 5 * 3
    5! + 5! + 4!
    = 264 > 100 =
    5 * 5 * 4
    5! + 5! + 5!
    = 360 > 125 =
    5 * 5 * 5

    Here's the program I used to check the cases for x, y, z <= 9.  I used perl.  Note the similarity to Zbyszek's solution.

    use strict;

    # initialize table of factorials with 0! = 1
    my @fac_table = (1);

    # loop executes 10 times
    # interesting fact - solution remains unique even if you use higher bases
    # (e.g., change 9 to 15 for hex)
    for my $i (0 .. 9) {
    $fac_table[$i + 1] = ($i + 1) * $fac_table[$i];

    # loop executes 1 + 2 + ... + 9 + 10 = 55 times
    for my $j (0 .. $i) {

    # inner loop executes
    # 1 +
    # 1 + 2 +
    # ...
    # 1 + 2 + ... + 9 +
    # 1 + 2 + ... + 9 + 10 times
    #
    # Here's how I counted that up:
    # if $i, $j, and $k are all different,
    # there are (10 choose 3) = 10 * 9 * 8 / 1 * 2 * 3 = 120 ways
    # if $i, $j, and $k are all the same,
    # there are 10 ways
    # if $i and $k are different, but $j is the same as one or the other,
    # there are (10 choose 2) ways to pick $i and $k = 10 * 9 / 1 * 2 = 45 ways
    # and two choices in each of these for $j so there are 90 ways
    # total = 120 + 10 + 90 = 220 iterations
    # (verified with a loop counter)
    for my $k (0 .. $j) {
    # note $i >= $j >= $k

    if ($fac_table[$i] + $fac_table[$j] + $fac_table[$k] == $i * $j * $k) {
    print qq($i! + $j! + $k! == $i * $j * $k\n);
    }
    }
    }
    }

    A cute little exercise.

  • Matthew van Eerde's web log

    The largest prime ever - you saw it here first

    • 0 Comments

    The GIMPS project says they've found the largest prime number ever, but they're keeping quiet about what it is until they've verified it (they expect to be done in a couple of weeks.)

    Pshaw.  I can tell you right now what their prime number is.

    Since I'm a computer scientist I'll write it down in binary.

    GIMPS' LARGEST PRIME NUMBER IS (scroll down / highlight to view:)

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    0b
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    ...
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111
    111111111111111111111111111111111111111111111111

    EDIT: On Saturday 9/6 another prime was found.  They're also keeping mum about what this one is.  But I know this one too...

    EDIT2: Every new Mersenne prime also means a new perfect number is discovered; counting these two new Mersenne primes, there are now 46 known perfect numbers, all of them even.  (It is conjectured, but not proven, that all perfect numbers are even.)  To go from a Mersenne prime (which is of the form 0b111...11, where there are a prime number of 1's) to its corresponding perfect number, tack on one fewer number of 0's onto the end of the number: e.g., 0b11 (3, the first Mersenne prime) becomes 0b110 (6, the first perfect number;) 0b111 (7, the second Mersenne prime) becomes 0b11100 (28, the second perfect number) etc. (The proof that such numbers are perfect is simple; there is a more complicated proof that all even perfect numbers are of this form.)

    EDIT: I can now reveal that the number of 1s is 43,112,609.

Page 1 of 1 (3 items)

August, 2008