[Tutor] A recreational math problem for Useless Python

[Danny Yoo]

Hiya everyone,

I've been glancing at Donald Knuth's neat "Selected Papers on Computer
Science" and ran across an interesting problem that he presents.  It
sounds like a lot of fun, and perhaps someone might be interested in
trying their hand at it.  Here's the challenge problem (any mispelings are
due to frantic typing):


"""
"The numbers sqrt(1), sqrt(2), ..., sqrt(50) are to be partitioned into
two parts whose sum is nearly equal; find the best such partition you can,
using less than 10 seconds of computer time.""


For example, it turns out to be possible to find the best partition of the
smaller set of numbers [sqrt(1), sqrt(2), ... sqrt(30)] after only about
one second of computer time; the answer is:

    sqrt(2) + sqrt(6) + sqrt(9) + sqrt(11) + sqrt(12) + sqrt(13) +
    sqrt(14) + sqrt(21) + sqrt(23) + sqrt(24) + sqrt(25) + sqrt(26) +
    sqrt(27) + sqrt(30)

    is approximately equal to

        56.04142 25880 73351 85163 20826

    and:

    sqrt(1) + sqrt(3) + sqrt(4) + sqrt(5) + sqrt(7) + sqrt(8) +
    sqrt(10) + sqrt(15) + sqrt(16) + sqrt(17) + sqrt(18) +
    sqrt(19) + sqrt(20) + sqrt(22) + sqrt(28) + sqrt(29)

    is approximately equal to

        56.04142 26276 19557 30332 11496

Note that the two sums agree to nine significant digits.  The problem with
50 instead of 30 is much more difficult, and it appears hopeless to find
an absolutely optimum partition in only 10 seconds.  This is one of the
beautiful features of Floyd's problem, since it allows for a friendly
competition between the members of the class (with a tie score very
unlikely), and especially because it makes the problem typical of real
life situations.  We are often confronted with problems that cannot be
solved exactly at reasonable cost, so we must do the best we can under
finite limitations... The time restriction encourages us to think, not
merely to compute!
"""