## Tuesday, October 18, 2016

### [umqmxbar] Numbers whose factorial is just less than a power of 2

3 5 22 28 48 63 64 90 536 548 557 2689 6627 35053 49692 55139 2418263 9519742 18582322 19015320 43430008 43578373 45601897 103481702 455189228 760006976 1855572486

Pari/gp:
s=0; m=0; for(i=1, 10^100, s+=log(i)/log(2); q=s; f=q-floor(q); if(f>m, m=f; printf(" %d",i))); print("")

64 was artificially inserted into the sequence; it is the same as 63.  64! = 0.9966 * 2^296 = 0.9966 * 256^37.

If one only has a uniform random bit generator, permutations of this many items can be generated easily, with high probability (low probability of rejection with rejection sampling).  In fact, looking at the high order bits when they come out are enough to (usually) quickly know to reject.

Going the other direction: 3 6 7 11 15 20 24 62 65. Stopping at 81 because it's hard to imagine someone with a good random permutation generator larger than shuffling a deck of 81 Set cards.

How can the above record sequences be computed (extended) quickly?  There seem to be many algorithmic tricks possible.