20160709, 22:56  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
868_{16} Posts 
Minimize n2^x*3^y over the integer
Hi,
Is there a way to formulate the solution of minimization of: abs(n2^x*3^y) Over integers x and y for any given integer n? A numeric example that I found by trial and error is: 68592^8*3^3=53 Thanks in advance. 
20160709, 23:29  #2  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
19^3(2^8*3^3)=53 which allows if rational bases were allowed: ((19/3)^32^8)*3^3 =53 and then: ((19/3)^3(2^(8/9))^9) *3^3=53 and then: ((19/3)^3(2^(16/9))^3)*3^3=53 if you want to reduce to a difference of cubes times a cube. of course this relies on the factorization of n. we also probably have different opinions/ideas about what is minimized though. 

20160710, 01:16  #3 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
I just realized you meant solving for x,y sorry brain asleep well we can turn it into :
n>=2^x * 3^y reexpression of n as a power of 2 is possible ( the power being at most x+log_2(3)*y ) and as a power of 3 ( the power being at most y+log_3(2)*x). edit: okay the >= is not technically true however the part you are subtracting can be turned into one power that you can possibly solve to x and y values on either side of 0 to try and equate to n. Last fiddled with by science_man_88 on 20160710 at 01:25 
20160710, 01:26  #4  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}·269 Posts 
Quote:
I would state it as: n~2^x * 3^y x<=round(log_2(n)) y<=round(log_3(n)) Solving for one power, given the other is trivial. Solving for x & y both unknown is what I would like insight to. Last fiddled with by a1call on 20160710 at 01:31 

20160710, 01:35  #5 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
technically there are two ( or even 3 once you break the >= case down) cases I've only shown one ( partly because I'm not sure I can phrase it).
Last fiddled with by science_man_88 on 20160710 at 01:36 
20160710, 04:00  #6 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}×269 Posts 
I don't expect there to be a known solution for this. I am just looking for expertconfirmation or authoritativereference on the subject.
Last fiddled with by a1call on 20160710 at 04:01 
20160710, 04:29  #7 
Jun 2003
141F_{16} Posts 
In a loop, look for all different powers of 3 from 0..y, and solve for the power of 2. Pick the one with smallest resultant difference. Even for numbers as large as 1000 digits, you'll have to check only about 2000 powers of 3. This is not a computationally difficult problem.

20160710, 04:47  #8  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}·269 Posts 
Quote:
You are correct, however I am not looking for a brute force type of a solution, rather a formulaic one. There can easily be prime related uses which can be computationally taxing. Say if you were to approximate a large factor using powers of a pool of primes. Last fiddled with by a1call on 20160710 at 04:47 

20160710, 06:42  #9  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts 
Quote:
Incidentally for any arbitrarily small >0, there exist x and y :: n2^x*3^y < , but that is of course for x,y in Z (not for x>=0, y>=0). 

20160710, 11:53  #10  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
Last fiddled with by science_man_88 on 20160710 at 12:43 

20160710, 15:33  #11 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
if r=N/(6^(floor(log_6(N)))) then you can say that x=floor(log_6(N))+{ 0 if r is not in ranges 23 or 45}{1 if in range 23}{2 if in range 45} ; y= floor(log_6(N)) +{0 if r is not in range 34} {1 otherwise} with at most one of these increasing one more to cover the value above N that could lead to a lower absolute value.
Last fiddled with by science_man_88 on 20160710 at 15:33 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
k*b^n+/c where b is an integer greater than 2 and c is an integer from 1 to b1  jasong  Miscellaneous Math  5  20160424 03:40 
Minimize maximum error  Joshua2  Homework Help  10  20110315 13:19 
Always an integer.  mfgoode  Puzzles  18  20070713 18:03 
Integer FFT  nevarcds  Math  4  20040728 19:14 
Good way to minimize factoring algoritm twice?  HiddenWarrior  Math  7  20040310 13:39 