Author |
Topic: power of 3 close to power of 2 (Read 249 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
power of 3 close to power of 2
« on: Jul 11th, 2022, 12:08pm » |
 Quote  Modify
|
How close can a power of 3 get to a power of 2, but still be smaller than that?
3^0 = 2^0 (this is really "close", although not smaller, and anyway too trivial)
3^1 = 2^2 - 1 (this is a unique pair, easy to prove that it cannot happen again)
3^1 = 2^3 - 5 (although it is a bit of cheat, as 3 is closer to 4 than to 8 ) and
3^3 = 2^5 - 5.
It can easily be proved that the difference must be at least 5 (other than the cases above). I only found this 27 = 32 - 5 one (or with the cheat 3 = 8 - 5, two) example of -5.
What I do not know:
- can 5 occur again in higher powers? Seems not, but could not prove.
- if not, 7 is the next number possible and it also exists (9 = 16-7), but again, can it occur more times?
- if not, does every number occur only once, or are there numbers that occur multiple, maybe infinite times?
- does every 6k +/- 1 occur once (3k and 2k numbers cannot occur for obvious reasons)?
- can there be some formulas for the minimum/maximum of this difference as a function of the power?
Also, slightly different is, what is the maximum of 3^n/2^m (as a ratio and < 1)?
First thought would be that sometimes 3^n will get "close enough" to 2^m, so that the ratio will be more than 1-e for any small positive e, but I am not even sure of this:
3^n/2^m = 1 - e
n * log2(3) - m = log2(1-e)
log2(3) - m/n = log2(1-e)/n
Although m/n can be any close to log2(3), it is not sure that when is a "close" m/n above or below log2(3) (only m/n > log2(3) matters), and whether this upper m/n rational approximation of log2(3) (i.e. the left side, that can surely be more than any small negative number and still be negative) is "significantly better" than the guaranteed 1/n.
If m/n - log2(3) > A/n for every n (where A is a fixed number), log2(1-e) < A and so e > 1 - 2^A, meaning that e cannot be arbitrarily small.
With other words, e can only get small if m/n can be a "significantly better" approximation (i.e. no A exist), but I cannot prove that it is the case or not.
|
|
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: power of 3 close to power of 2
« Reply #1 on: Jul 12th, 2022, 5:49am » |
Quote Modify
|
on Jul 11th, 2022, 12:08pm, jollytall wrote:Although m/n can be any close to log2(3), it is not sure that when is a "close" m/n above or below log2(3) (only m/n > log2(3) matters), and whether this upper m/n rational approximation of log2(3) (i.e. the left side, that can surely be more than any small negative number and still be negative) is "significantly better" than the guaranteed 1/n.
If m/n - log2(3) > A/n for every n (where A is a fixed number), log2(1-e) < A and so e > 1 - 2^A, meaning that e cannot be arbitrarily small.
With other words, e can only get small if m/n can be a "significantly better" approximation (i.e. no A exist), but I cannot prove that it is the case or not. |
|
Do you get anywhere looking for the best approximation across denominators in [n,2n]?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: power of 3 close to power of 2
« Reply #2 on: Jul 12th, 2022, 9:29am » |
Quote Modify
|
Thanks, but no, I don't. Maybe some more hint would help.
What I tried:
let L = log2(3) (or actually it is the same for any other irrational L)
|L*n - m| < e = 1/E has always a solution for every E (or e), and n < E.
|L - m/n| < 1/En. If m/n > L we are done. The problem is if the approximation is on the wrong side.
Then I can find an n' = n*z where En<n'<2En. Let also m' = m*z.
With a well selected o
0 < (m'+o)/n' - L < 1/En. Almost good, but the problem is that on the right side I have n and not n'.
(m'+o)/n' - L < 1/En = z/En', i.e. instead of 1/E I get z/E. If n is small (i.e. a small m/n gives a good approximation on the wrong side) then z is large and z/E is not anywhere close to 1/E. It theoretically can still happen (I don't think it) that z/E > A for every E (where A is above, a fixed limit of the best approximation).
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: power of 3 close to power of 2
« Reply #3 on: Jul 13th, 2022, 5:58am » |
Quote Modify
|
Thinking more about it, if you go from n to n+1, the denominator will either remain m, or become m+1. The former will decrease your value by m/n(n+1); the latter increase by (n-m)/n(n+1).
If you approximate m as being nL then you either decrease your error by L/(n+1) or increase it by (1-L)/(n+1), depending whether your current error is less than or greater than L/n.
So there's no particular reason there why the scaled error should have a trend in either direction - for an arbitrary irrational, I'd expect it to wander around (0,1) chaotically, with the minimum decreasing over time through pure chance.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: power of 3 close to power of 2
« Reply #4 on: Jul 13th, 2022, 2:09pm » |
Quote Modify
|
I also got something like this.
I did not find any reason why the difference (as a ratio) MUST converge to zero. If the irrational number would have any sequence of digits for sure, then e.g. lots of zeros after each other would make a rational number suddenly a very good approximation. Even if not all decimal sequences occur there might still be rational numbers that are suddenly give a "very good" approximation. Still I do not see that this chance exists as we (or at least I) know so little about the value (digits, actually in any base) of log2(3).
Going back to the first part of the question. Any idea on the absolute value (not the ratio)? Would there be a number occur infinite times, that would immediately mean a convergence to 1. Even if the difference has some limits as a function of 2^n but less than linear, it would also make the ratio close to 1.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: power of 3 close to power of 2
« Reply #5 on: Sep 29th, 2022, 7:09am » |
Quote Modify
|
I think I have a proof for the ratio of 3^n/2^m (<1) can get larger than any 1-e.
Let's take 3^n, what is between 2^m and 2^(m+1). If 3^n/2^m > 3/2 then I use 3^n/2^(m+1) (>3/4) and call it less than the "closest" (by ratio) power of 2. If 3^n/2^m<3/2 than I call it more than the closest power of 2.
Starting with the special case 3^1 = 3, it is 3/2 and 3/4 for the two neighboring power of twos.
Now I call 3/4 the best lower number so-far and 3/2 the best upper number so-far (aL and aH).
In the next step I take aL*aH (with other words the power of 3 that is a sum of the lower and upper powers in the previous step and the same for the power of 2). In the initial case it is 3/4*3/2 = 9/8.
This aNext > aL and aNext < aH (simply because aH was multiplied with a number <1 and aL was multiplied with a number >1).
If aNext > 1 then it becomes aH, otherwise becomes aL. I can continue this iteration infinite times. In every step aH-aL decreases and converges to either a non zero number or to zero.
What we want to prove is that aL converges to 1. I use an indirect proof, assuming that aL converges to 1 - l where l > 0. aH either converges to 1 or to 1 + h. First I exclude the possibility that aH converges to 1 + h and then I exclude the possibility that aH converges to 1 (and aL to 1 - l).
Let in one step aL = 1 - l - e and aH = 1 + h + f (e<<l and f<<h).
aN = 1 - l - e + h - hl - he + f - fl + fe, but
aN < 1 + h, because
1 - l - e + h - hl - he + f - fl + fe < 1 + h
-l -e -hl - he + f -fl +fe < 0
f(1 - l + e) - e(1+h) < l(1+h), where all elements of the left side << than the elements on the right side.
So, aH cannot converge to 1 + h, it can only converge to 1.
Let in one step aL = 1 - l -e and aH = 1 + f.
aN = 1 - l - e + f - fl -fe. It is clearly < 1, i.e. aN becomes aL and aH does not change.
If in every step aH (= 1 + f > 1) does not change then after many (n) steps
aN = (1 - l - e) * (1 + f) ^ n, but (1 + f)^n can grow above any number including
(1 - l) / (1 - l - e), in which case aN > 1 -l what is a contradiction.
So, aL converges to 1, i.e. the power of 3 can get arbitrarily close (in terms of a ratio) to the next (larger) power of 2.
It raises to me one more question: Is this sequence of aL the best achievable or there can be other 3^n with lower n, where it is still a better ratio.
And still I have no idea about the absolute difference achievable.
P.S. What happened to the superscript. I can only write 3^n and not the proper superscript version.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: power of 3 close to power of 2
« Reply #6 on: Nov 13th, 2023, 10:10am » |
Quote Modify
|
If I remember well, I proved few month ago that indeed this aL is the best sequence, but that was never validated by anyone.
Nonetheless, I am more interested in the smallest absolute difference (i.e. not ratio) between 3^n and 2^m, where 2^m > 3^n.
I came up with a related question to prove:
2^m - 3^n > 2^(m-n) if 2^m > 3^n > 3.
With other words, if we write 3^n in base 2 then the first (i.e. highest value) n bits have at least one 0 among them.
Yet with other words, we proved earlier that 3^n/2^m > 1-e can be solved for any e, but even that solution is not that close, i.e.
3^n/2^m < 1-2^-n
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print