wu :: forums « wu :: forums - power of 3 close to power of 2 » Welcome, Guest. Please Login or Register. Aug 12th, 2022, 8:17am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums riddles hard (Moderators: towr, Eigenray, Icarus, william wu, ThudnBlunder, SMQ, Grimbal) power of 3 close to power of 2 « No topic | Next topic » Author Topic: power of 3 close to power of 2  (Read 31 times)
jollytall
Senior Riddler Gender: Posts: 577 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: 2849 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: 577 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: 2849 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: 577 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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « No topic | Next topic »
{"ft_lang_label":"__label__en","ft_lang_prob":0.9175657,"math_prob":0.9410311,"size":5936,"snap":"2022-27-2022-33","text_gpt3_token_len":1810,"char_repetition_ratio":0.12306136,"word_repetition_ratio":0.29190993,"special_character_ratio":0.3217655,"punctuation_ratio":0.11210097,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9689017,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-12T15:17:01Z\",\"WARC-Record-ID\":\"<urn:uuid:5be5e8c9-fdaf-4841-9916-1255cedef49b>\",\"Content-Length\":\"42015\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:fa2343f5-b807-46f1-bf08-1287e48c00be>\",\"WARC-Concurrent-To\":\"<urn:uuid:e68288d1-d669-4f64-ae25-7b74e744f19e>\",\"WARC-IP-Address\":\"169.229.226.23\",\"WARC-Target-URI\":\"https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1657566486;start=4\",\"WARC-Payload-Digest\":\"sha1:IJTPQUQU4ZDR3VTFH54O7C44AWWVVMJA\",\"WARC-Block-Digest\":\"sha1:I44CZHQQOVCKBA3FEP32ZZU37L73TBYK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882571719.48_warc_CC-MAIN-20220812140019-20220812170019-00656.warc.gz\"}"}