a(27) in A059097: A new lower higher bound

[Jack Brennen]

Some statistics on this sequence which I just collected...

For n ranging from 0 to 2^31-1, these are the (smallest) values of p
for which p^2 divides C(2*n,n), along with the number of times that
value of p is the "witness" which eliminates n from the sequence:

p ==  3, 2141454336 times
p ==  5,    5955962 times
p ==  7,      71761 times
p == 11,       1309 times
p == 13,        188 times (largest is 492832062)
p == 17,         28 times (largest is 64491311)
p == 19,         16 times (largest is 2007775)
p == 23,         17 times (largest is 49784905)
p == 29,          2 times (n == 750 or 751)
p == 31,          1 time  (n == 731)
p == 43,          1 time  (n == 3250)

No value of p,   27 times (largest is 786)


Given that p > 13 is only needed 65 times while eliminating
2147483621 candidates, and that all of those 65 times occur
in (roughly) the first 3% of the range, I'd say that any
attempt to extend the search bound further should probably
just try to find C(2*n,n) not divisible by 9, 25, 49, 121, or 169.
Very few candidates, if any, should fall through that test.
If they do, fall out to a slower general purpose test.
(In addition, those five squared primes are also the ones
which can fit in a single byte, which may offer some advantages
in implementation...)

  Jack