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

Richard Guy rkg at cpsc.ucalgary.ca
Tue Nov 22 22:25:34 CET 2005

```In OEIS A059097 only a fairly small bound
is given.  Now that good programs have been
written, could people post the latest record,
so that Neil can update OEIS and I can update
UPINT.   Thanks in anticipation,   R.

On Tue, 22 Nov 2005, Alonso Del Arte wrote:

> 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
>>
>> 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
>>>
>>
>

```