Return to Revisions

First, I'd like to revisit Will Sawin's upper bound, but I make no promises about off-by-one errors (which I think I made in comments elsewhere on this page). The product of any sequence of $x$ consecutive integers has $p$-valuation at least $\lfloor \frac{x}{p-1}\rfloor - \lfloor \log_p(x+1) \rfloor$. The $p$-valuation of $\binom{n}{a}$ is the number of carries when adding $a$ to $n-a$ in base $p$, so this is bounded above by $\lfloor \log_p n \rfloor$. In other words, the product of the $x = b-(n-a)$ integers from $n-a+1$ to $b$ must satisfy $\lfloor \frac{x}{p-1}\rfloor - \lfloor \log_p(x+1) \rfloor \leq \lfloor \log_p n \rfloor$. Pushing some terms around yields the bound $$x \leq (p-1)\lfloor log_p(n) \rfloor +(p-1) \lfloor log_p log_p n \rfloor + 2p - 2.$$ If we only worry about making $\frac{n!}{a!b!}$ into a 2-adic integer instead of an ordinary integer, then this bound is sharp, since the case $n=2^k, a=2^k-1, b = 2^y-1$ saturates it when $k = 2^y-y-1$.

When $n$ is large, $(p-1) \lfloor \log_p(n) \rfloor > \lfloor \log_2(n) \rfloor$ for odd $p$, so this suggests that it is good to check 2-valuations when eliminating candidate triples. By request, here is some computer code.

I couldn't find a fast function in SAGE for computing the valuation of a factorial, so I made a Cython file "val.spyx" with the code:

def val(int a, int p):
    cdef int i,r
    i=0
    r=p
    while(a >= r):
        i = i + (a/r)
        r = r*p
    return i

In SAGE, I compiled it with

load ".../val.spyx"

where "..." indicates the directory holding the file (available with the "pwd" UNIX command). Then I wrote three functions (I imagine there are more elegant ways to write these):

def innerloop(a,b,c):
    r=0
    p=2
    while(r==0 and p <= min(b,c)):
        if val(a,p) < val(b,p) + val(c,p):
            r=1
        p=next_prime(p)
    return r

def testvirtue(m,k):
    r=0
    for i in range((m+k+1)/2,m):
        if innerloop(m,i,m-i+k)==0:
            print m,i,m-i+k
            r=1
    return r

def testrange(m,n,k):
    for i in range(m,n):
        if testvirtue(i,k):
            k=k+1
            testvirtue(i,k)
    return k

Anyway, starting with k=3 and running up to 80000 took about 2 hours on my laptop:

10 7 6
36 23 17
36 29 11
56 47 14
100 59 47
162 107 62
162 110 59
256 142 122
256 202 62
256 239 25
256 241 23
261 223 47
261 239 31
416 239 187
1056 620 447
2080 1214 878
2080 1853 239 
3201 1775 1439
4384 2735 1663
32778 18458 14335
32808 18617 14207
32808 23615 9209
65536 34963 30590
65536 39314 26239
65536 39319 26234
65536 39323 26230
65536 39346 26207
65536 39347 26206
65536 52447 13106
65536 39347 26207
19

As you can see from the last entries, the optimal value of $a+b-n$ jumps by 2 to 18 at 65536. I checked a few larger powers of two beyond 80000 - here are the maximal values of $a+b-n$:

4 1
8 1
16 3
32 3
64 4
128 5
256 8
512 8
1024 9
2048 8
4096 11
8192 14
16384 14
32768 14
65536 18
131072 17
262144 20
524288 20
1048576 21
2097152 12
4194304 20
8388608 20
16777216 21

I couldn't find a really good pattern here, although powers of 4 tend to yield better values than odd powers of 2. $2^{21}$ is very strange.