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

[Alonso Del Arte]

Yes, I was actually having it calculate the binomial. I haven't
benchmarked (2n)! / (n!)^2, but I figure it wouldn't be too much
faster.

David, I tried implementing your algorithm in Mathematica but I got
stuck at f(p, n). For both f(2, 786) and f(3, 786) it gave me 0s,
where I expected 4 and 1. I'm running late to a meeting, so it's
possible I have made some small mistake I'm not seeing right now. I
tested e(p, n) with e(7, 15) and it said 2 like I expected, so I think
I've implemented that one correctly, but I will double-check it later
today and let you know how it goes.

Al

On 11/21/05, David Wilson <davidwwilson at comcast.net> wrote:
> 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
> >
>