a(27) in A059097: A new lower higher bound
Alonso Del Arte
alonso.delarte at gmail.com
Tue Nov 22 17:40:39 CET 2005
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