 |
|
List Archives >
Maple User Group List Archive >
Archive by date >
This Month By Date >
This Month By Topic
[MUG] binomial coefficients
| [MUG] binomial coefficients |
|
Author: Maple User Group
Posted: Thu, 30 Jan 2003 16:45:48 -0500
|
>> From: Maple User Group "maple_gr"
>>From "maple_gr" Tue Jan 14 11:02:08 2003
Received: from smtp01.mrf.mail.rcn.net (smtp01.mrf.mail.rcn.net [207.172.4.60])
by scg.math.uwaterloo.ca (8.11.6/8.11.6) with ESMTP id h0EG25d27526
for "maple-list" Tue, 14 Jan 2003 11:02:08 -0500 (EST)
Received: from 66-44-21-21.s275.apx3.lnh.md.dialup.rcn.com ([66.44.21.21] helo=yourze8cxvr8tt)
by smtp01.mrf.mail.rcn.net with smtp (Exim 3.35 #4)
id 18YTVt-0000gG-00
for "maple-list" Tue, 14 Jan 2003 11:02:05 -0500
Message-ID: <002701c2bbe6$475525f0$15152c42@yourze8cxvr8tt>
From: "Dan. & Linda Willard" "willardd"
To: "maple-list"
References: "200301141351.h0EDpib29050"
Subject: Re: [MUG] recognising binomial coefficients
Date: Tue, 14 Jan 2003 11:02:02 -0500
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2800.1106
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106
X-Spam-Status: No, hits=1.1 required=5.0
tests=QUOTED_EMAIL_TEXT,RCVD_IN_OSIRUSOFT_COM,REFERENCES,
SPAM_PHRASE_00_01,USER_AGENT_OE,X_OSIRU_DUL,X_OSIRU_DUL_FH
version=2.43
X-Spam-Level: *
Status: R
Have you tried factoring?
----- Original Message -----
From: "Brendan McKay" "bdm"
To: "maple-list"
Sent: Friday, January 10, 2003 6:37 PM
Subject: [MUG] recognising binomial coefficients
>
> >> From: Brendan McKay "bdm"
>
> The following problem has no important application that I know of.
> It just occurred to me as something that would interest a few
> people in this group.
>
> Say that a binomial coefficient binomial(n,k) is "non-trivial" if
> n and k are integers such that 2 <= k <= n-2. The problem is to
> determine if (and how) a given number is a non-trivial binomial
> coefficient.
>
> For example, if we are given
> 11159690566590580740354583612991667619792058478202676400
> we would like to quickly recognise that it equals binomial(187,92).
>
> I suspect that considering the theory of binomial coefficients
> modulo a prime might be productive.
>
> Brendan.
>
>>From "maple_gr" Tue Jan 14 14:24:14 2003
Received: from maynard.rephil.org (rephil.org [65.165.40.37])
by scg.math.uwaterloo.ca (8.11.6/8.11.6) with ESMTP id h0EJODd20516
for "maple-list" Tue, 14 Jan 2003 14:24:14 -0500 (EST)
Received: by maynard.rephil.org (Postfix, from userid 1000)
id B61D873D23; Tue, 14 Jan 2003 13:01:21 -0600 (CST)
References: "200301141351.h0EDpib29050"
In-Reply-To: "200301141351.h0EDpib29050"
From: "Phil Mendelsohn" "phil"
To: "maple-list"
Subject: Re: recognising binomial coefficients
Date: Tue, 14 Jan 2003 13:01:21 -0600
Mime-Version: 1.0
Content-Type: text/plain; format=flowed; charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Message-Id: "20030114190121.B61D873D23"
X-Spam-Status: No, hits=-1.3 required=5.0
tests=IN_REP_TO,QUOTED_EMAIL_TEXT,REFERENCES,SPAM_PHRASE_00_01
version=2.43
X-Spam-Level:
Status: R
Brendan McKay writes:
>
> For example, if we are given
> 11159690566590580740354583612991667619792058478202676400
> we would like to quickly recognise that it equals binomial(187,92).
>
> I suspect that considering the theory of binomial coefficients
> modulo a prime might be productive.
Here's a wrinkle, though:
binomial coefficients are not unique -- i.e., there's often lots of ways to
get them. This poses a lot of trouble algorithmically, at least.
Cheers,
Phil Mendelsohn
--
"To misattribute a quote is unforgivable." -- Anonymous
>>From "maple_gr" Tue Jan 14 15:42:05 2003
Received: from brain.math.fau.edu (brain.math.fau.edu [131.91.80.111])
by scg.math.uwaterloo.ca (8.11.6/8.11.6) with ESMTP id h0EKg4d26249
for "maple-list" Tue, 14 Jan 2003 15:42:05 -0500 (EST)
Received: from localhost (localhost.localdomain [127.0.0.1])
by brain.math.fau.edu (Postfix) with ESMTP
id F3CF92F03F; Tue, 14 Jan 2003 15:42:43 -0500 (EST)
Received: by brain.math.fau.edu (Postfix, from userid 527)
id 714A72F040; Tue, 14 Jan 2003 15:42:41 -0500 (EST)
From: "Aaron Meyerowitz" "meyerowi"
Subject: Re: [MUG] recognising binomial coefficients
To: "maple-list"
Cc: "bdm"
X-Originating-IP: 131.91.81.218
X-Mailer: Webmin 0.960
Message-Id: "20030114204241.714A72F040"
Date: Tue, 14 Jan 2003 15:42:41 -0500 (EST)
X-Virus-Scanned: by AMaViS perl-11
X-Spam-Status: No, hits=0.0 required=5.0
tests=QUOTED_EMAIL_TEXT,SPAM_PHRASE_00_01
version=2.43
X-Spam-Level:
Status: R
Brendan McKay "bdm" wrote ..
>
> >> From: Brendan McKay "bdm"
>
> The following problem has no important application that I know of.
> It just occurred to me as something that would interest a few
> people in this group.
>
> Say that a binomial coefficient binomial(n,k) is "non-trivial" if
> n and k are integers such that 2 <= k <= n-2. The problem is to
> determine if (and how) a given number is a non-trivial binomial
> coefficient.
>
> For example, if we are given
> 11159690566590580740354583612991667619792058478202676400
> we would like to quickly recognise that it equals binomial(187,92).
>
> I suspect that considering the theory of binomial coefficients
> modulo a prime might be productive.
>
The prime factorization of the given number ends:
(53)(59)(61)(97)(101) ...(179)(181) where ... is all the primes between 101 and 179. That seems promising for a binomial coefficient binomial(n,k) with 181<=n<191 (since 191 is the next prime) and 89<=n-k<97 (since 89 is the largest ommitted prime)
now looking mod a prime close to n/3 or n/4 should be revealing. Indeed, mod 43 or 67 determines it uniquely in that range.
It seems like a search for solutions with "small" k (like k<sqrt(n)) coupled with something like this should almost always work.
>>From "maple_gr" Tue Jan 14 16:59:03 2003
Received: from mcphail.usc.edu (mcphail.usc.edu [128.125.253.51])
by scg.math.uwaterloo.ca (8.11.6/8.11.6) with SMTP id h0ELx0d00806
for "maple-list" Tue, 14 Jan 2003 16:59:03 -0500 (EST)
Received: from math.usc.edu(128.125.11.1) by mcphail.usc.edu via csmap
id 28944; Tue, 14 Jan 2003 13:56:44 -0800 (PST)
Received: from math.usc.edu (imperator.usc.edu [128.125.188.226])
by math.usc.edu (8.9.3.1/8.9.3/usc) with ESMTP
id NAA09332 for "maple-list" Tue, 14 Jan 2003 13:58:54 -0800 (PST)
Date: Tue, 14 Jan 2003 13:58:54 -0800
Subject: Re: [MUG] recognising binomial coefficients
Content-Type: text/plain; charset=US-ASCII; format=flowed
Mime-Version: 1.0 (Apple Message framework v551)
From: Ronald Bruck "bruck"
To: "maple-list"
Content-Transfer-Encoding: 7bit
In-Reply-To: "200301141351.h0EDpib29050"
Message-Id: "5F8A8D88-280B-11D7-B42E-0003930C779A"
X-Mailer: Apple Mail (2.551)
X-Spam-Status: No, hits=-4.2 required=5.0
tests=EMAIL_ATTRIBUTION,IN_REP_TO,QUOTED_EMAIL_TEXT,
SPAM_PHRASE_02_03,USER_AGENT_APPLEMAIL
version=2.43
X-Spam-Level:
Status: R
On Friday, January 10, 2003, at 03:37 PM, Brendan McKay wrote:
>
>>> From: Brendan McKay "bdm"
>
> The following problem has no important application that I know of.
> It just occurred to me as something that would interest a few
> people in this group.
>
> Say that a binomial coefficient binomial(n,k) is "non-trivial" if
> n and k are integers such that 2 <= k <= n-2. The problem is to
> determine if (and how) a given number is a non-trivial binomial
> coefficient.
>
> For example, if we are given
> 11159690566590580740354583612991667619792058478202676400
> we would like to quickly recognise that it equals binomial(187,92).
>
> I suspect that considering the theory of binomial coefficients
> modulo a prime might be productive.
I think you will essentially have to factor the integer, or at least
find the biggest prime factor of the integer. Your example factors as
2^4 * 3 * 5^2 * 7 * 11^2 * 13 * 17 * 31 * 37 * 53 * 59 * 61 * 97 *
101 * 103 * 107
*109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167
* 173 * 179 * 181
and since the next prime after 181 is 191, this means the n must be
between 181 and 190, inclusive. Not a big range, and once you know n
you can find k with a few trials.
Conversely, if you CAN write the integer as a binomial coefficient, you
will have reduced the range (and if k is large, quite substantially
reduced the range) that n can lie in. So this is essentially a
factorization problem.
Note that the number of times a prime p divides a binomial coefficient
is N(n,p) - N(k,p) - N(k,n-k), where N(n,p) = sum of floor(n/p^i), i =
1 to infinity (really a finite sum). Assuming k <= n/2 (which we can
surely arrange) this means that all primes p between k and n must
appear in the factorization. The longest such list is
{97,101,103,107,...,181} for your example, so I would start at k = 97
and work down.
--Ron Bruck
>>From "maple_gr" Wed Jan 15 17:31:28 2003
Received: from viol.math.ubc.ca (viol.math.ubc.ca [137.82.36.61])
by scg.math.uwaterloo.ca (8.11.6/8.11.6) with ESMTP id h0FMVPW09728
for "maple-list" Wed, 15 Jan 2003 17:31:28 -0500 (EST)
Received: from germain.math.ubc.ca (IDENT: [137.82.36.62])
by viol.math.ubc.ca (8.12.3/8.12.3) with ESMTP id h0FMVMRK016080;
Wed, 15 Jan 2003 14:31:22 -0800 (PST)
Received: from localhost (israel@localhost)
by germain.math.ubc.ca (8.12.3/8.12.3) with ESMTP id h0FMVLJ5023351;
Wed, 15 Jan 2003 14:31:21 -0800 (PST)
X-Authentication-Warning: germain.math.ubc.ca: israel owned process doing -bs
Date: Wed, 15 Jan 2003 14:31:21 -0800 (PST)
From: Robert Israel "israel"
To: "maple-list"
cc: "bdm"
Subject: Re: [MUG] recognising binomial coefficients
In-Reply-To: "200301141351.h0EDpib29050"
Message-ID: "Pine.GSO.4.44.0301151235210.22612-100000"
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Spam-Status: No, hits=-3.2 required=5.0
tests=EMAIL_ATTRIBUTION,IN_REP_TO,QUOTED_EMAIL_TEXT,
SPAM_PHRASE_02_03,USER_AGENT_PINE,X_AUTH_WARNING
version=2.43
X-Spam-Level:
Status: R
Given a number like that, you might first try to factor it, using
the "easy" option (because if it is binomial(n,k) with n not very
large, its prime factors should all be fairly small). In your example,
if your number is B, we get
> ifactor(B,easy);
4 2 2
(2) (3) (5) (7) (11) (13) (17) (31) (37) (53) (59)
(61) (97) (101) (103) (107) (109) (113) (127) (131)
(137) (139) (149) (151) (157) (163) (167) (173)
(179) (181)
The largest prime factor is 181.
If B = binomial(n,k) with (wlog) k <= n/2, any prime between n-k+1 and
n inclusive will divide B. Assuming there are such primes, the most
n could be is 190 (because 191 is the next prime after 181).
So there aren't too many possibilities for n. For any given n,
we could use Stirling's approximation to determine k approximately
and then quickly refine this to find which k will make the magnitude
of binomial(n,k) close to that of B. In this case we must have
n >= 187, else binomial(n,floor(n/2)) is too small. And checking
n=187, we find indeed that k=92 works.
So here's my proposed code. It will return the pair [n,k] if successful,
an error if it can't factor B, or FAIL if it can factor B and determines
there is no possible [n,k] (or no prime between n-k and n).
binomialfinder:= proc(B)
local F,p,q,Q,Q1,n,t,k,B0;
F:= ifactors(B,easy)[2];
if hastype(F,name) then error "couldn't easily factor %1",B fi;
p:= F[-1,1];
q:= nextprime(p)-1;
for n from p to q do
Q:= ln(B) + 1/2*ln(2*Pi*n*t*(1-t)) + n*(t*ln(t)+(1-t)*ln(1-t)):
Q1:= evalf(subs(t=1/2,Q));
if Q1 > 0.01 then next # B too big
elif Q1 > -0.01 then k:= floor(n/2)
else k:= round(n*fsolve(Q=0,t=0..1/2))
fi;
B0:= binomial(n,k);
if B0 >= B then
while B0 > B do
k:= k - 1;
B0:= B0*(k+1)/(n-k);
od
else
while B0 < B do
k:= k + 1;
if k > n/2 then B0:= infinity
else B0:= B0*(k+1)/(n-k);
fi
od
fi;
if B0 = B then return [n,k] fi;
od;
FAIL
end;
Robert Israel "israel"
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
On Sat, 11 Jan 2003, Brendan McKay wrote:
> The following problem has no important application that I know of.
> It just occurred to me as something that would interest a few
> people in this group.
>
> Say that a binomial coefficient binomial(n,k) is "non-trivial" if
> n and k are integers such that 2 <= k <= n-2. The problem is to
> determine if (and how) a given number is a non-trivial binomial
> coefficient.
>
> For example, if we are given
> 11159690566590580740354583612991667619792058478202676400
> we would like to quickly recognise that it equals binomial(187,92).
>
> I suspect that considering the theory of binomial coefficients
> modulo a prime might be productive.
>
> Brendan.
>
|
Previous by date: [MUG] Guaranteed multiple-precision results, Vincent Lefevre
Next by date: [MUG] Automata and Maple, Vesa-Matti Sarenius
Previous thread: [MUG] Problem with SWP Implementation of Maple, Jim Moser
Next thread: [MUG] Automata and Maple, Vesa-Matti Sarenius
|
|
|
(NAG)
