mersenneforum.org Minimize |n-2^x*3^y| over the integer
 Register FAQ Search Today's Posts Mark Forums Read

 2016-07-09, 22:56 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22×3×181 Posts Minimize |n-2^x*3^y| over the integer Hi, Is there a way to formulate the solution of minimization of: abs(n-2^x*3^y) Over integers x and y for any given integer n? A numeric example that I found by trial and error is: |6859-2^8*3^3|=53 Thanks in advance.
2016-07-09, 23:29   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by a1call Hi, Is there a way to formulate the solution of minimization of: abs(n-2^x*3^y) Over integers x and y for any given integer n? A numeric example that I found by trial and error is: |6859-2^8*3^3|=53 Thanks in advance.
well in your numerical example we can partially-minimize at the start:

19^3-(2^8*3^3)=53
which allows if rational bases were allowed:

((19/3)^3-2^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.

 2016-07-10, 01:16 #3 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·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 re-expression 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 2016-07-10 at 01:25
2016-07-10, 01:26   #4
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

87C16 Posts

Quote:
 Originally Posted by science_man_88 I just realized you meant solving for x,y sorry brain asleep well we can turn it into : n>=2^x * 3^y re-expression 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).
Thank you for the replies science_man_88,
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 2016-07-10 at 01:31

2016-07-10, 01:35   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by a1call Thank you for the replies science_man_88, 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.
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 2016-07-10 at 01:36

 2016-07-10, 04:00 #6 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 22×3×181 Posts I don't expect there to be a known solution for this. I am just looking for expert-confirmation or authoritative-reference on the subject. Last fiddled with by a1call on 2016-07-10 at 04:01
2016-07-10, 04:29   #7
axn

Jun 2003

120738 Posts

Quote:
 Originally Posted by a1call Thank you for the replies science_man_88, 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.
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.

2016-07-10, 04:47   #8
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

22×3×181 Posts

Quote:
 Originally Posted by axn 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.
Thank you for the reply axn.
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 2016-07-10 at 04:47

2016-07-10, 06:42   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·1,201 Posts

Quote:
 Originally Posted by a1call Thank you for the reply axn. You are correct, however I am not looking for a brute force type of a solution, rather a formulaic one.
Not everything has a formulaic solution. Think about an arbitrary fifth degree equation root, or for example gcd(a,b). Your case is similar to gcd. Or you can compare it to lattice reduction.

Incidentally for any arbitrarily small $\eps$>0, there exist x and y :: |n-2^x*3^y| < $\eps$, but that is of course for x,y in Z (not for x>=0, y>=0).

2016-07-10, 11:53   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by a1call Thank you for the reply axn. 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.
using prime factorization of n we can define it almost exactly as the sum of the x and y values for each prime factor counted with multiplicity.edit: okay it depends on being close to powers to work but it's formulaic in that give something about n we can semi predict x and y.

Last fiddled with by science_man_88 on 2016-07-10 at 12:43

 2016-07-10, 15:33 #11 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·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 2-3 or 4-5}{1 if in range 2-3}{2 if in range 4-5} ; y= floor(log_6(N)) +{0 if r is not in range 3-4} {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 2016-07-10 at 15:33

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Miscellaneous Math 5 2016-04-24 03:40 Joshua2 Homework Help 10 2011-03-15 13:19 mfgoode Puzzles 18 2007-07-13 18:03 nevarcds Math 4 2004-07-28 19:14 HiddenWarrior Math 7 2004-03-10 13:39

All times are UTC. The time now is 08:17.

Sun Nov 28 08:17:36 UTC 2021 up 128 days, 2:46, 0 users, load averages: 1.28, 1.13, 1.09