[math-fun] working on a recipe/formula
i'm not sure i fully understood scott's post, but it is probably similar to something i'm working on here. i'm trying to find a general "formula" for T(m, n) . perhaps i should say *bound* on T(m, n) , but my intent is to get it exact in as many cases as possible. i will always have m <= n , and here i will focus on the range n >= 3m/2 . this is very much "in progress" as we speak, so to speak. firstly, there is the trivial case, when m divides 2n . i call this "case I", which splits into case I A if m divides n , and case I B if m divides 2n but not n . we have the exact values T(m, n) = 1/n and 1/(2n) in these cases, respectively. case II is if m does not divide 2n and 2n >= 3m . divide 2n by m to get 2n = mq + r , where 0 < r < m , and now compare r(q + 1) to (m - r)q . there are three possibilities: case II A: r(q + 1) > (m - r)q . here we have the easy bound T(m, n) <= 1/n - 1/(qm) . case II B: r(q + 1) < (m - r)q . here we have the easy bound T(m, n) <= 1/((q+1)m) . case II C: r(q + 1) = (m - r)q . here we have the exact value T(m, n) = 1/((q+1)m) , which also equals 1/n - 1/(qm) . (in case II C, we have (m, n) = ((2k+1)j, k(k+1)j) for some k >= 3 . i had previously identified the family T(2k+1, k(k+1)) = 1/((k+1)(2k+1)) in an earlier message, and this is just a "multiple" of that.) when can the bounds in II A and II B be attained? here's a guess. in case II A, divide r(q + 1) - (m - r)q by r to get r(q + 1) - (m - r)q = rs + t where 0 <= t < r . it seems plausible to believe that if s >= 2 , then equality can be attained. (i was initially skeptical of this, thinking there might be some behavior like that in the case m < n < 3m/2 , but i have not encountered such.) case II A.1 is when s >= 2 , so there's no improvement in the bound. case II A.2 is when s = 1 and r - t divides r + t (equivalently, divides 2t ). in this case, T(m, n) = 1/n - 1/(qm) can be achieved. case II A.3 is when s = 1 and r - t does not divide r + t . so divide r + t by r - t to get r + t = (r - t)u + v , where 0 < v < r - t . then we have the improved bound T(m, n) <= ((u+2)/m - (u+1)/n)/((q-1)(u+2)+2) . case II A.4 is when s = 0 . in this case, the bound can be improved to T(m, n) <= (1/m - 1/(2n))/q . it is unlikely that this bound can always be attained. here's the corresponding refinement in case II B: divide (m - r)q - r(q + 1) by m - r to get (m - r)q - r(q + 1) = (m - r)s + t where 0 <= t < m - r . as in case II A, it is reasonable to believe that the bound 1/((q+1)m) can be attained if s >= 2 . so we have the cases, similar to those in II A: case II B.1: s >= 2 . in this case there's no improvement in the bound. case II B.2: s = 1 and m - r - t divides m - r + t (equivalently, divides 2t ). in this case, T(m, n) = 1/((q+1)m) can be achieved. case II B.3: s = 1 and m - r - t does not divide m - r + t . so divide m - r + t by m - r - t to get m - r + t = (m - r - t)u + v , where 0 < v < m - r - t . we then have the improvement T(m, n) <= 1/n - ((u+2)/m - (u+1)/n)/((q-2)(u+2)+2) . case II B.4: s = 0 . here the bound can be improved to T(m, n) <= 1/n - (1/m - 1/(2n))/(q - 1) . it is likely that cases II A.3, A.4, B.3 and B.4 all need further refinement in subcases where the bound can be improved. i speculate that these subcases will be similar to the splitting of cases II A and B , and there will be further splittings into sub-sub-...-subcases, probably with arbitrarily deep splitting. some examples: (m, n) = (13, 23) , which is one of the complex examples we've already seen. here we have q = 3 and r = 7 . then r(q + 1) > (m - r)q , so we have case II A. next, s = 1 and t = 3 , and since r - t does not divide r + t , we have case II A.3. now u = 2 and v = 2 , so our improved bound is T(13, 23) <= (4/13 - 3/23)/10 = 53/2990 , which is the exact value, as i previously showed. (m, n) = (25, 41) . again we have q = 3 and r = 7 , but this time r(q + 1) < (m - r)q , so we're in case II B. next, s = 1 and t = 8 , and since m - r - t does not divide m - r + t , we're in case II B.3. now u = 2 and v = 6 , so the improved bound is T(m, n) <= 1/41 - (4/25 - 3/41)/6 = 61/6150 . indeed, this bound can be attained via 4 * [3 * 61 + 63] + 3 * [2 * 61 + 2 * 62] + 6 * [68 + 2 * 89] + 6 * [75 + 82 + 89] + 4 * [71 + 87 + 88] + 2 * [2 * 79 + 88] <---> 18 * [61 + 89] + 6 * [62 + 88] + 4 * [63 + 87] + 6 * [68 + 82] + 4 * [71 + 79] + 3 * [2 * 75] where i've scaled the parts by 6150 for those who don't like fractions. the first case where the above is not sharp is (m, n) = (20, 33) , where the bound from the "formula" is 41/3300 , but the exact value is 49/3960 . among the long list of values i previously sent, the only other pair (in case II) where the formula is not sharp is (21, 37) . i also have some refinements of case III ( n < (3/2)m ) beyond what i previously sent, that work for all but 1 of the values on that long list. but it'll have to wait for another message ... mike
participants (1)
-
Michael Reid