0
   

An efficient way to solve this.

 
 
nphard
 
Reply Sat 10 Dec, 2011 09:52 am
What is an efficient way to solve A^x+B^y+C=Z. If Z is given,where A,B,x,y are less than 2^32 ,C is less than 2^64 and Z is less than 2^8000. All variables are greater than Zero.
NOTE:We are solving for any combination of A,B,C,x,y that fits in.
  • Topic Stats
  • Top Replies
  • Link to this Topic
Type: Question • Score: 0 • Views: 793 • Replies: 9
No top replies

 
raprap
 
  1  
Reply Sat 10 Dec, 2011 09:49 pm
@nphard,
Take the logarithm and treat as linear equation.

A^x+B^y+C=Z

becomes

xLog(A)+yLog(B)=Log(Z-C)

Which is recognized as the standard form of a line.

Caveat--problems arise when C>=Z.

Rap
markr
 
  1  
Reply Sat 10 Dec, 2011 10:11 pm
@raprap,
log(a+b) != log(a) + log(b)
raprap
 
  1  
Reply Sun 11 Dec, 2011 05:53 pm
@markr,
oops. disreguard
0 Replies
 
nphard
 
  1  
Reply Tue 13 Dec, 2011 03:19 am
@nphard,
only Z is given. Am trying to find the right combination to get Z.
markr
 
  1  
Reply Tue 13 Dec, 2011 09:38 am
@nphard,
Do you only need a single solution? Are all variables integers?
0 Replies
 
engineer
 
  1  
Reply Tue 13 Dec, 2011 10:03 am
@nphard,
Are you looking for a computer algorithm or a way to force a solution by hand? Your problem is woefully under specified. If you set A=B=0 and C=Z, that will always work, but if that was ok you wouldn't be here. There has to be something you aren't telling us.
markr
 
  1  
Reply Tue 13 Dec, 2011 12:37 pm
@engineer,
C is constrained to be potentially much smaller than Z. The problem is trivial for small enough Z. It's when Z gets really large that it gets difficult. The problem seems to be to find integer powers of two (up to) 32-bit integers such that their sum is within 2^64 of an arbitrarily large (up to 2^8000) number.
markr
 
  1  
Reply Tue 13 Dec, 2011 09:52 pm
@markr,
For the vast majority of allowable Z values, there will not be a solution. There are fewer than 2.43E43 possible values that can be generated by the left hand side (all valid combinations of A, B, C, x, and y), but there are 1.7E2408 (2^8000) possible values for the right hand side (Z). You've only got a 1 in 7E2364 chance of picking a Z with a solution...
markr
 
  1  
Reply Wed 14 Dec, 2011 12:36 am
@markr,
Assuming Z > 2^64 (otherwise it's trivial) and A^x >= B^y, then

Z > A^x >= (Z - 2^64)/2

If Z is quite large, for each A, there is only one x that satisfies the above inequality (although for A=2, there are potentially two values for x). That narrows the search, but you still have to check 2^32 values for A, and for each A, you need to do a similar thing to find a B^y that gets you within 2^64 of Z.

That's the best I can do.
0 Replies
 
 

Related Topics

Amount of Time - Question by Randy Dandy
logical number sequence riddle - Question by feather
Calc help needed - Question by mjborowsky
HELP! The Product and Quotient Rules - Question by charsha
STRAIGHT LINES - Question by iqrasarguru
Possible Proof of the ABC Conjecture - Discussion by oralloy
Help with a simple math problem? - Question by Anonymous1234567890
How do I do this on a ti 84 calculator? - Question by Anonymous1234567890
 
  1. Forums
  2. » An efficient way to solve this.
Copyright © 2024 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 8.94 seconds on 12/22/2024 at 05:17:52