mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2016-07-09, 22:56   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

86816 Posts
Default 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.
a1call is offline   Reply With Quote
Old 2016-07-09, 23:29   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by a1call View Post
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 is offline   Reply With Quote
Old 2016-07-10, 01:16   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2016-07-10, 01:26   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·269 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
a1call is offline   Reply With Quote
Old 2016-07-10, 01:35   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-07-10, 04:00   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23×269 Posts
Default

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
a1call is offline   Reply With Quote
Old 2016-07-10, 04:29   #7
axn
 
axn's Avatar
 
Jun 2003

141F16 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
axn is offline   Reply With Quote
Old 2016-07-10, 04:47   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·269 Posts
Default

Quote:
Originally Posted by axn View Post
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
a1call is offline   Reply With Quote
Old 2016-07-10, 06:42   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,787 Posts
Default

Quote:
Originally Posted by a1call View Post
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).
Batalov is offline   Reply With Quote
Old 2016-07-10, 11:53   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by a1call View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-07-10, 15:33   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Reply

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 b-1 jasong Miscellaneous Math 5 2016-04-24 03:40
Minimize maximum error Joshua2 Homework Help 10 2011-03-15 13:19
Always an integer. mfgoode Puzzles 18 2007-07-13 18:03
Integer FFT nevarcds Math 4 2004-07-28 19:14
Good way to minimize factoring algoritm twice? HiddenWarrior Math 7 2004-03-10 13:39

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


Tue Oct 26 08:58:00 UTC 2021 up 95 days, 3:26, 0 users, load averages: 1.88, 2.12, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.