Out of town
Dave Colwell
tomorrow. Looking forward on the calendar, the next meeting would
fall in the Friday after Thanksgiving. Would everyone be interested
in offsetting the meeting rotation by having a meeting on November
20? Following the bi-weekly schedule, that puts other meetings on
12/4 and 12/18. Someone please take discussion notes tomorrow and
post to the forum.
Thanks & see you soon,
Dave
Michael Krajnak
More then glad to take notes tomorrow.
Mike
Grant Rettke
Are we sticking on this schedule then?
smantix
backlogged on the current project and taking time off for book club
would be extremely bad form. I hope things are going well.
I have been able to keep up some recreational reading, having recently
finished David Leavitt's _The Indian Clerk_, a fictional account of
G.H.Hardy, the Indian prodigy Ramanujan, and the Cambridge milieu
during the Great War. Hardy told part of the same story himself in his
_A Mathematician's Apology_.
In one episode from Leavitt's book, Ramanujan tells Hardy about a
puzzle he found in the newspaper. A soldier is trying to recall an
address in a neighborhood destroyed by war. All the houses were
numbered sequentially beginning with one. The number of the house in
question was such that the sum of the address numbers to one side of
the house equalled the sum of those on the other side. The soldier
could not remember exactly how many houses there were, but the number
was more than 50 and less than 500.
I played around with this puzzle a bit. To give you a feel for the
problem, 6 of 8 gives a low-valued solution: 1+2+3+4+5 = 7+8. Recall
that the sum of the integers from 1 to n is given by n*(n+1) / 2. A
little bit of algebra will get you to m^2 = n*(n+1) / 2, where m is
the number of the house of interest and n the number of the last house
on the block.
Now it's simple to write a program to solve this--either in original
form or the reduced form above. (Interestingly there is only one
solution in the given range.) And it's no surprise that a genius like
Ramanujan would have the answer. But here's the gotcha: the soldier
said he took the problem to his parson, who worked it out with pencil
and paper. Moreover, the puzzle was published in a popular newspaper
and meant to be solved by the general public.
I have kicked this one around a good deal and I don't see how to work
it without computational aids. Am I dense? Was British "maths"
education at the turn of the 19th century that much better than
today's? Is Leavitt pulling a fast one (the problem did not really
appear in a popular newspaper)?
If any of you can enlighten me, I'd appreciate it. Happy Holidays!
Dave Colwell
best I can come up with is a solution that requires up to 354 addition
operations and nearly as many comparison operations (about 320) to
determine if a summed value is a perfect square. By hand (is a
calculator allowed?), I think I could solve the problem in well under
2 hours.
I'll try to prove myself later tonight or tomorrow.
We've missed seeing you at book club. I hope your project is
successful and wraps up soon!
Dave
smantix
Hamming, as I am prone to do: the purpose of computing, whether manual
or automated, is insight, not numbers.
It may well be that the parson solved the problem with a brute-force
approach. People of that era certainly did much more calculation
mentally and manually than we with our electronic crutches do. If so,
I'm content with writing a bit of code to do the heavy lifting.
I was looking for a little of that insight, asking for a different
approach to the problem. So here's an idea: instead of trying to solve
for m and n, what if we consider the difference between them, say k =
n - m? The search space for n is 450 (500 - 50), but for k it's
smaller. At n = 50, m is roughly 35 and k, 15. (From the original
equation, m is roughly (n^2/2)^1/2 or n / (2^1/2) or .707*n.) At the
upper bound, k is about 150. So the solution space for k is less than
1/3 of that for n.
It's a possibility anyway. Other ideas are welcome.
Dave Colwell
motivated to reduce the amount of computation. After failing to find
a way to "descend" on the solution, I started trying to reduce my
algorithm to the least necessary computations. So, the best I could
muster was based on your claim that "m^2 = n*(n+1) / 2". By
iteratively adding to the sum of values up to n, all I'd need to do is
determine if the current sum is a perfect square. I got some tips on
discovering a perfect square from http://mathforum.org/library/drmath/view/61878.html,
but figure I'd also use a calculator for the set values not filtered
by these tricks.
I must admit that when I had some free time (about 10:00 pm last
night) I wasn't in the mood to do arithmetic :)
smantix
programmer / mathematician par excellence! But if you insist on manual
solution, hear me out on k = n - m. Anything that reduces the solution
space saves effort.
Substituting n = m+k into the original reduction gives: m^2 = (m+k)*(m+
(k+1)) / 2. A bit of futzing will get you to: m^2 - (2k - 1)*m - k*(k
+1) = 0. In terms of the standard quadratic equation a*x^2 + b*x + c:
a = 1, b = -(2k-1) and c = -k*(k+1). m must be integer, therefore the
discriminant in the quadratic formula (b^2 -4ac) must (minimally) be a
perfect square. Substituting and simplifying, 8k^2 + 8k + 1 must be a
perfect square, where 35 < k < (about) 150.
If you're tackling this by hand, this approach should help.