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

[Jack Brennen]

Alonso Del Arte wrote:
> 
> It probably would take an hour to go up 10^7, but in any case we
> should be able to give Neil a very nice, large lower bound once he
> returns from vacation.
> 

Like I stated earlier, I tested up to 2^31-1 (2147483647) using a
C implementation I threw together.  I ran up against the 32-bit
limitation of "unsigned" integers on the x86 -- once n reaches 2^31,
we can't represent 2*n as an unsigned integer any longer.

If I recall correctly, up to 2^31-1, the largest prime that was
ever needed to eliminate a number from the sequence was 43...
When n == 3250, C(2*n,n) is divisible by 43^2, but by no smaller
odd prime square.  (And n==3250 was the only time that the test
had to go as far as 43^2.)

Thus, I think any program used to extend the sequence probably
should be optimized to work with just the first few odd prime
squares -- as a quick guess, I'd probably just focus on finding
C(2*n,n) which are not divisible by any odd prime square up to
23^2.  If anything falls out of this, it could revert to a
slower complete test.

David's idea of just iterating the C(2*n,n) which are not
divisible by 9 is a good idea.  My program didn't do this;
it would generally take no more than a fraction of a
microsecond to eliminate each candidate which has C(2*n,n)
divisible by 9, so for the range I tested, it wasn't
crucial.  But as the bound is pushed higher and higher,
and as n with C(2*n,n) not divisible by 9 get more and
more sparse, it makes sense to implement a more complex
first step which takes longer to generate each candidate,
but which can skip millions of non-candidates in a single
iteration.

If I get some time, maybe I'll try to implement something.
But although it's not really difficult to push the bound
higher, I can't imagine dedicating a lot of CPU power to
it -- you can't prove the conjecture (that the sequence
is finite and complete) by throwing more CPU time at it,
and I'm convinced that you won't find a counterexample
either.