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
>> 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
>>>
>>
>
More information about the SeqFan
mailing list