Minimize |n-2^x*3^y| over the integer

[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.

[science_man_88]

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.

[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).

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.

[a1call]

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.

[science_man_88]

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).

[a1call]

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.

[axn]

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.

[a1call]

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.

[Batalov]

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 >0, there exist x and y :: |n-2^x*3^y| < , but that is of course for x,y in Z (not for x>=0, y>=0).

[science_man_88]

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.

[science_man_88]

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.