![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoy...barring any errors in the program, anyway. And some of its output was a bit suspicious. Regardless, I'm pretty certain of it by this point, and failing all else I can always check it all by hand, which would be a bunch of case checking, but not nearly as much as it would have been previously. I really doubt any mistakes it may have made are ones that would affect the final result.
So, here we go: Let f be the function Josh and I have been working on; let k∈N. Then if k is not of either of the following forms:
A.) 2m3n for m≤10
B.) 2a(2b3n+1)3m for a+b≤2
Then the following holds:
1.) If ⌈3log3k+(5-6log32)⌉≡0 (mod 3), then f(k) is at least this quantity.
2.) If ⌈3log3k+3(1-log32)⌉≡0 or 1 (mod 3), then f(k) is at least this quantity.
3.) f(k)≥3log3k+1.
(Note that 1, which gives the largest bound, is only a tiny improvement over 3, with a difference of only about 0.21 - and of course this whole exercise is such a tiny improvement on the standard bound in the first place! - but it can matter. For instance, say we want to prove f(2183n)=36+3n; the last inequality isn't going to cut it. Note that as far as 2a3b goes, these bounds are only good enough for a≤18, not 19; 19 was a mistake.)
EDIT 9/12: There was a typo in the lists below; Instead of "4*3^n+1" I wrote "4*3^n+4".
Furthermore, not all the exceptions listed above necessarily are exceptions; the completely reduced lists of numbers for which 1, 2, and 3 fail (where the condition is in fact met, obviously) are:
1.) 16*3^m, 128*3^m, 1024*3^m, (4*3^n+4)*3^m for n≥1, (4*3^n+2)*3^m for n≥1, (4*3^n+1)*3^m.
2.) 2*3^m, 8*3^m, 16*3^m, 64*3^m, 128*3^m, 512*3^m, 1024*3^m, (2*3^n+2)*3^m for n≥1, 40*3^m, (2*3^n+1)*3^m for n≥1, 14*3^m, 38*3^m, 5*3^m, 13*3^m.
3.) 2^n*3^m for n≤9 (except when k=1), (3^n+1)*3^m, 20*3^m, 40*3^m, 7*3^m, 19*3^m, 14*3^m, 38*3^m, 5*3^m, 13*3^m.
And that's all, folks!
...OK, OK, at some point I'm going to have to start writing up a proof. But really! There it is!
Yaaaaaay!
-Harry
So, here we go: Let f be the function Josh and I have been working on; let k∈N. Then if k is not of either of the following forms:
A.) 2m3n for m≤10
B.) 2a(2b3n+1)3m for a+b≤2
Then the following holds:
1.) If ⌈3log3k+(5-6log32)⌉≡0 (mod 3), then f(k) is at least this quantity.
2.) If ⌈3log3k+3(1-log32)⌉≡0 or 1 (mod 3), then f(k) is at least this quantity.
3.) f(k)≥3log3k+1.
(Note that 1, which gives the largest bound, is only a tiny improvement over 3, with a difference of only about 0.21 - and of course this whole exercise is such a tiny improvement on the standard bound in the first place! - but it can matter. For instance, say we want to prove f(2183n)=36+3n; the last inequality isn't going to cut it. Note that as far as 2a3b goes, these bounds are only good enough for a≤18, not 19; 19 was a mistake.)
EDIT 9/12: There was a typo in the lists below; Instead of "4*3^n+1" I wrote "4*3^n+4".
Furthermore, not all the exceptions listed above necessarily are exceptions; the completely reduced lists of numbers for which 1, 2, and 3 fail (where the condition is in fact met, obviously) are:
1.) 16*3^m, 128*3^m, 1024*3^m, (4*3^n+4)*3^m for n≥1, (4*3^n+2)*3^m for n≥1, (4*3^n+1)*3^m.
2.) 2*3^m, 8*3^m, 16*3^m, 64*3^m, 128*3^m, 512*3^m, 1024*3^m, (2*3^n+2)*3^m for n≥1, 40*3^m, (2*3^n+1)*3^m for n≥1, 14*3^m, 38*3^m, 5*3^m, 13*3^m.
3.) 2^n*3^m for n≤9 (except when k=1), (3^n+1)*3^m, 20*3^m, 40*3^m, 7*3^m, 19*3^m, 14*3^m, 38*3^m, 5*3^m, 13*3^m.
And that's all, folks!
...OK, OK, at some point I'm going to have to start writing up a proof. But really! There it is!
Yaaaaaay!
-Harry
no subject
Date: 2009-09-10 11:17 pm (UTC)Overall, this result as stated here looks at least prettier than what I was expecting this to end up looking like.
no subject
Date: 2009-09-11 12:18 am (UTC)I suppose this allows you to start with the old base case for your proof of f(k)-3log_3(k) being unbounded? Hell, that's really all statement 3 is - one case of that, done in detail. Sometime you need to show me that again - do you suppose the list of exceptions you'd get from your method would be just as good as the one I got this way, or would it include more extraneous stuff? Did you ever try to compute that out explicitly, for 1 or 2 or anything?
(To avoid confusion with strict and nonstrict inequalities, I should probably note that, if we leave off the ceiling signs, equality never holds for any of those three, except statement 3 when k=1. This is easy to check - just check which values of k will cause those to be integers, and then check none of them work.)
no subject
Date: 2009-09-11 01:01 am (UTC)no subject
Date: 2009-09-11 02:10 am (UTC)