SPUG: Math Geniuses

[Chris Wilkes]

On Thu, Jul 25, 2002 at 01:30:41PM -0700, Orr, Chuck  (NOC) wrote:
> 
>                               I need a unique solution for each of these
> numbers, which is unattainable without more information (that I probably
> can't get.)  

What you're doing is called a "Diophantine Equation" which is usually in
the simple form of
	ax + by = c
See http://mathworld.wolfram.com/DiophantineEquation.html for more info.

However you've got it a little tougher as you have more than 2 variables
on the left side.  You can break it down into simplier equations, ie
  A + 36B + 360C + 3600D + 29600E = 2307012
becomes (since most of the left side is divisiable by 36):
  A + 36Q = 2307012 = 12 * 192251 = 12*(3*64084 - 1) = 36*64084 - 12
solving for the integer Q:
  Q = 64084 - (A+12)/36
For Q to be an integer the A+12/36 needs to be one as well.  Since you
said 0 <= integers <= 36 you find out that A = 24.  Note: this isn't a
constraint in the normal Diophantine equations.

So you continue on from there with A = 24 and you get something like
  B + 10C + 100D + 3600E = 64083
and you continue on from there with the same style of equation:
  B + 10Q = 64083 = 6408*10 + 3
Finding out that B has to be 3,13,23, or 33 to satisfy Q being an
integer.  Its not so easy to continue on as you have 4 potential values
for B, which then leads to 4*4 for C, etc.

How to do this in perl?  To me this looks like a tree where each branch
(ie A=24 being a branch) then has another branch (B = 3,13,23,33) which
will then have more branches.  Eventually you'll get to the end with E
and you'll see if it all adds up to your number.

Maybe a hash like:
  $hash{A}{B}{C}{D}{E} = A + 36B + 360C + 3600D + 29600E
would be the best way to model it.

Its been a long time since I've looked at these equation so I could be
wrong on the easiest way to solve them.  That less than 36 constraint
seems a little contrived to me too, how did that come up?

Chris

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
     POST TO: spug-list at pm.org       PROBLEMS: owner-spug-list at pm.org
      Subscriptions; Email to majordomo at pm.org:  ACTION  LIST  EMAIL
  Replace ACTION by subscribe or unsubscribe, EMAIL by your Email-address
 For daily traffic, use spug-list for LIST ;  for weekly, spug-list-digest
     Seattle Perl Users Group (SPUG) Home Page: http://seattleperl.org