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

[David Wilson]

A059097 includes n such that C(2n, n) has no odd square divisor.

I assume your program is taking so long because you are actually computing
c(2n, n).  Here is a much better method.

The exponent e of prime p in n! can be computed as follows (in pseudo-C):

    int e(int p, int n) {
        int s = 0;
        while (n > 0) {
            n /= p;   // That is, n = floor(n/p)
            s += n;
        }
        return s;
    }

And the exponent of p in C(2n, n) is then f(p, n) = e(p, 2*n) - 2*e(p, n).

We can then use the following function to check if n is in A059097:

    bool isGood(int n) {
        for (int p = 3; p <= n; p += 2) {
            if (!isPrime(p)) continue;
            if (f(p, n) >= 2) return false;
        }
        return true;
    }

For large n, A059097 is eliminated very quickly, much more quickly
than by computing C(2n, n).

I am fairly convinced that A059097 is finite.  Indeed, I contend that all but
a finite number of c(2n, n) are divisible by 9 or 25.  This would be a special
case of a conjecture I have made about b-regular sets.

I wrote a Perl program to check A059097, and in the time it has taken me
to write this message, it has confirmed that A059097 is complete up to
7,700,000.  Note that Perl is not particularly efficient at number crunching.

----- Original Message ----- 
From: "Alonso Del Arte" <alonso.delarte at gmail.com>
To: <seqfan at ext.jussieu.fr>
Sent: Monday, November 21, 2005 3:31 PM
Subject: a(27) in A059097: A new lower higher bound


> Accepting Naohiro Nomoto's statement as true that after 786 there are
> no more terms less than 157430 in A059097, I've checked up to 160250
> and found no more terms either. I've been checking in chunks of a
> hundred each, my algorithm takes about 505 seconds for each chunk, 495
> seconds if I don't do anything else on the computer.
> 
> Can anyone confirm or dispute my finding? Has anyone else tried to
> extend this further? Anyone close to a proof that the sequence is
> finite?
> 
> Alonso
>