Sunday, July 27, 2014

The Change Problem and the Gap between Recreational and Serious Mathematics

In a prior post (here) I discussed the change problem: given a dollar, how many ways can you make change using pennies, nickels, dimes, and quarters (and generalize to n cents). Scouring the web I found either programs for it, the answer   (242), and answers like `is the coefficient of x^100 in ... . What I didn't find is a  formula for n cents. So I derived one using recurrences and wrote this up with some other things about the change problem, and I posted it on arXiv. (I have updated the paper many times after comments I got. It is still where it was, but updated, here.)

I then got some very helpful emails pointing me to the vast math literature on this problem. I was not surprised there was such a literature, though I was surprised I hadn't found any of it searching the web.
The literature didn't have my formula, though it had several ways to derive it (some faster than mine).

Why isn't the formula out there? Why couldn't I find the literature?

  1. The formula falls into a space right between recreational and serious math. I use a recurrence  but not a generating function. Recreational math just wants to know the answer for 100, so a program suffices (or some clever by-hand recurrences, which are also in my paper). Serious math people are happy to show that a formula CAN be derived and to refine that in terms of how quickly the coefficients can be found.
  2. There is a gap between recreational and serious math. In particular- the serious people aren't talking to (or posting on websites to) the rec people.
  3. Different terminologies. I was looking for ``change problems'' and ``coin problems'' and things like that when I should have been looking for ``Sylvester Denumerant'' or ''Frobenius problem''
For some areas Google (and other tools) are still not as good as finding someone who knows about your area. My posting on the blog got some people who know stuff's attention, and my posting on arXiv got one more person (who knew A LOT!).  I'm glad they emailed me comments and references so I improved the paper and cited the literature properly. But this seems so haphazard! Google didn't work,  mathstack exchange and other similar sites didn't work (that is where I saw the Rec people post but not get a formula). Is it the case that no matter how good Google gets we'll still need to find people who know stuff? Thats fine if you can, but sometimes you can't.

11 comments:

  1. This is exactly the reason why search will not replace knowledge and learning. It is not always the case that we know what to look for. This is especially the case when we cross over into other fields. It's like making surprising (leap) connections; this is something that people can do and you need to have actual knowledge in order to do it. It's not always enough to have Google (thankfully).

    ReplyDelete
  2. "I improved the paper and sighted the literature properly." Typo, should be "cited".

    Please delete this comment.

    ReplyDelete
    Replies
    1. Fixed, thanks.
      This typo is more interesting than most---the two words sound identical!

      Delete
    2. "mathstack exchange and other similar sights didn't work". Another interesting typo, sights should be sites.

      Delete
    3. Fixed thanks. Less interesting the second time it happens.

      Delete
    4. While we're on the topic, you've got "ALOT" instead of "A LOT" :)

      Delete
  3. Not sure if you tried it, but google scholar can work better than google for something like this. All you need to do is find ONE paper on your topic, and then google scholar can help you find papers citing or cited by that one.

    ReplyDelete
    Replies
    1. I did try it, but I kept getting articles about the Euro! Coins, change, etc. Perhaps I could have tried harder, but this particular problem had that problem--- I didn't know the good key words. If Angela Merkel (who has a PhD in Physics and hence knows some math) had written a paper on the Frobenius problem then maybe that would have worked.

      But you raise an excellent point- I am complaining about the web's failure for the change problem but perhaps this is an outlier given the terminology. It could be worse- you could be looking up HARD CORE BITS- see what you find...

      Delete
  4. For problems like this, you could also have consulted the OEIS (Neal Sloane's Online Encyclopedia of Integer Sequences, https://oeis.org/). Entering the query 1,1,1,1,2,2,2,2,2,4 (first 10 terms) gets you to the math literature.

    ReplyDelete
  5. You should try MathOverflow when Math StackExchange doesn't work.

    ReplyDelete
  6. In the field of music, it's even harder...you know the tune but there is (currently?) no way to search!

    ReplyDelete