Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #6122 > unrolled thread
| Started by | David Turner <DTurner@faulkner.edu> |
|---|---|
| First post | 2011-11-02 11:28 +0000 |
| Last post | 2011-11-04 11:04 +0000 |
| Articles | 5 — 5 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
Bernoulli Numbers David Turner <DTurner@faulkner.edu> - 2011-11-02 11:28 +0000
Re: Bernoulli Numbers "Dr. Wolfgang Hintze" <weh@snafu.de> - 2011-11-03 08:46 +0000
Re: Bernoulli Numbers Simon <simonjtyler@gmail.com> - 2011-11-03 08:51 +0000
Re: Bernoulli Numbers DrMajorBob <btreat1@austin.rr.com> - 2011-11-04 11:02 +0000
Re: Bernoulli Numbers "Alexander Elkins" <alexander_elkins@hotmail.com> - 2011-11-04 11:04 +0000
| From | David Turner <DTurner@faulkner.edu> |
|---|---|
| Date | 2011-11-02 11:28 +0000 |
| Subject | Bernoulli Numbers |
| Message-ID | <j8r9gv$3jd$1@smc.vnet.net> |
Hello,
I wish to compute several Bernoulli numbers, say B0 through B20. The Bernoulli numbers are defined recursively by
B0 = 1, and Solve[Sum[Binomial[n,k]*Bk,{k,0,n-1}]==0,Bn-1] for n > 1
I am trying to compute these numbers in some type of loop, and display them in a table. Any help is greatly appreciated.
Thanks,
David
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. This message contains confidential information and is intended only for the individual named. If you are not the named addressee you should not dissem inate, distribute or copy this e-mail. Please notify the sender immediately by e-mail if you have received this e-mail by mistake and delete this e-mail from your system. If you are not the intended recipient you are notified that disclosing, copying, distributing or taking any action in reliance on the contents of this information is strictly prohibited.
[toc] | [next] | [standalone]
| From | "Dr. Wolfgang Hintze" <weh@snafu.de> |
|---|---|
| Date | 2011-11-03 08:46 +0000 |
| Message-ID | <j8tkdi$esm$1@smc.vnet.net> |
| In reply to | #6122 |
Why not solve by hand for b[n] (and preferrably use lower case symbols
for your own ones), i.e.
b[n_] := -Sum[Binomial[n + 1, k]*b[k], {k, 0, n - 1}]/(n + 1)
and then calculate the values recursively in a table
b[0] = 1;
Table[{n, b[n]}, {n, 0, 16}]
{{0, 1}, {1, -(1/2)}, {2, 1/6}, {3, 0}, {4, -(1/30)},
{5, 0}, {6, 1/42}, {7, 0}, {8, -(1/30)}, {9, 0},
{10, 5/66}, {11, 0}, {12, -(691/2730)}, {13, 0},
{14, 7/6}, {15, 0}, {16, -(3617/510)}}
Regards,
Wolfgang
"David Turner" <DTurner@faulkner.edu> schrieb im Newsbeitrag
news:j8r9gv$3jd$1@smc.vnet.net...
> Hello,
>
> I wish to compute several Bernoulli numbers, say B0 through B20. The
> Bernoulli numbers are defined recursively by
>
> B0 = 1, and Solve[Sum[Binomial[n,k]*Bk,{k,0,n-1}]==0,Bn-1] for n > 1
>
> I am trying to compute these numbers in some type of loop, and
> display them in a table. Any help is greatly appreciated.
>
> Thanks,
>
> David
>
> _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
> _ _ _
>
> This email and any files transmitted with it are confidential and
> intended solely for the use of the individual or entity to whom they
> are addressed. This message contains confidential information and is
> intended only for the individual named. If you are not the named
> addressee you should not dissem inate, distribute or copy this
> e-mail. Please notify the sender immediately by e-mail if you have
> received this e-mail by mistake and delete this e-mail from your
> system. If you are not the intended recipient you are notified that
> disclosing, copying, distributing or taking any action in reliance on
> the contents of this information is strictly prohibited.
[toc] | [prev] | [next] | [standalone]
| From | Simon <simonjtyler@gmail.com> |
|---|---|
| Date | 2011-11-03 08:51 +0000 |
| Message-ID | <j8tknd$f0o$1@smc.vnet.net> |
| In reply to | #6122 |
Bernoulli number generation is already built into Mathematica, so generating them yourself is probably not worthwhile. The formula in your post, which is related to "umbral calculus" and is thus very cool, is not very efficient. To make it tolerably fast, you should combine it with memoization(1) and use
Clear[B]
B[0] = 1;
B[(n_Integer)?Positive] := B[n] = (-(1/(1 + n)))*Sum[Binomial[n + 1, k]*B[k],{k, 0, n - 1}]
Then the first twenty can be generated with
Table[B[i], {i, 1, 20}]
(* Returns: {-(1/2), 1/6, 0, -(1/30),... } *)
Which can be compared to the built in function for the first 1000 values:
And @@ Table[B[i] == BernoulliB[i], {i, 1, 1000}]
(* Returns: True *)
The Wikipedia article(2) discusses algorithms for computing Bernoulli numbers. I think that Mathematica probably uses some hybrid calculational scheme.
There was a nice Wolfram blog post a while back about this(3).
A newer algorithm that beat the Mathematica record uses the Chinese Remainder Theorem and is implemented in some CAS is described at http://arxiv.org/abs/0807.1347 There was some discussion of this at the time over at (4).
(1)http://reference.wolfram.com/mathematica/tutorial/FunctionsThatRememberValuesTheyHaveFound.html
(2)http://en.wikipedia.org/wiki/Bernoulli_number
(3)http://blog.wolfram.com/2008/04/29/today-we-broke-the-bernoulli-record-from-the-analytical-engine-to-mathematica/
(4)https://groups.google.com/forum/#!topic/sage-devel/6GHGlW6hpa8
[toc] | [prev] | [next] | [standalone]
| From | DrMajorBob <btreat1@austin.rr.com> |
|---|---|
| Date | 2011-11-04 11:02 +0000 |
| Message-ID | <j90gno$si6$1@smc.vnet.net> |
| In reply to | #6122 |
Much faster is:
Clear[b]
b[0] = 1;
b[n_] := b[n] = -Sum[Binomial[n + 1, k]*b[k], {k, 0, n - 1}]/(n + 1)
Array[b, 17, 0] // Timing
{0.000679, {1, -(1/2), 1/6, 0, -(1/30), 0, 1/42, 0, -(1/30), 0, 5/66,
0, -(691/2730), 0, 7/6, 0, -(3617/510)}}
whereas before, the timing was:
Clear[b]
b[0] = 1;
b[n_] := -Sum[Binomial[n + 1, k]*b[k], {k, 0, n - 1}]/(n + 1)
Array[b, 17, 0] // Timing
{0.717417, {1, -(1/2), 1/6, 0, -(1/30), 0, 1/42, 0, -(1/30), 0, 5/66,
0, -(691/2730), 0, 7/6, 0, -(3617/510)}}
Bobby
On Thu, 03 Nov 2011 03:44:09 -0500, Dr. Wolfgang Hintze <weh@snafu.de>
wrote:
> Why not solve by hand for b[n] (and preferrably use lower case symbols
> for your own ones), i.e.
>
> b[n_] := -Sum[Binomial[n + 1, k]*b[k], {k, 0, n - 1}]/(n + 1)
>
> and then calculate the values recursively in a table
> b[0] = 1;
>
> Table[{n, b[n]}, {n, 0, 16}]
>
> {{0, 1}, {1, -(1/2)}, {2, 1/6}, {3, 0}, {4, -(1/30)},
> {5, 0}, {6, 1/42}, {7, 0}, {8, -(1/30)}, {9, 0},
> {10, 5/66}, {11, 0}, {12, -(691/2730)}, {13, 0},
> {14, 7/6}, {15, 0}, {16, -(3617/510)}}
>
> Regards,
> Wolfgang
>
> "David Turner" <DTurner@faulkner.edu> schrieb im Newsbeitrag
> news:j8r9gv$3jd$1@smc.vnet.net...
>> Hello,
>>
>> I wish to compute several Bernoulli numbers, say B0 through B20. The
>> Bernoulli numbers are defined recursively by
>>
>> B0 = 1, and Solve[Sum[Binomial[n,k]*Bk,{k,0,n-1}]==0,Bn-1] for n > 1
>>
>> I am trying to compute these numbers in some type of loop, and
>> display them in a table. Any help is greatly appreciated.
>>
>> Thanks,
>>
>> David
>>
>> _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
>> _ _ _
>>
>> This email and any files transmitted with it are confidential and
>> intended solely for the use of the individual or entity to whom they
>> are addressed. This message contains confidential information and is
>> intended only for the individual named. If you are not the named
>> addressee you should not dissem inate, distribute or copy this
>> e-mail. Please notify the sender immediately by e-mail if you have
>> received this e-mail by mistake and delete this e-mail from your
>> system. If you are not the intended recipient you are notified that
>> disclosing, copying, distributing or taking any action in reliance on
>> the contents of this information is strictly prohibited.
>
>
--
DrMajorBob@yahoo.com
[toc] | [prev] | [next] | [standalone]
| From | "Alexander Elkins" <alexander_elkins@hotmail.com> |
|---|---|
| Date | 2011-11-04 11:04 +0000 |
| Message-ID | <j90grj$sko$1@smc.vnet.net> |
| In reply to | #6122 |
Mathematica provides for the computation of Bernoulli numbers:
In[1]:= expect=Table[BernoulliB[k], {k, 0, 20}]
Out[1]= {1, -(1/2), 1/6, 0, -(1/30), 0, 1/42, 0, -(1/30), 0, 5/66,
0, -(691/2730), 0, 7/6, 0, -(3617/510), 0, 43867/798, 0, -(174611/330)}
For one way to display them in a table use:
Grid[Table[{Subscript[B, k], BernoulliB[k]}, {k, 0, 20}],
Alignment -> {{Left, Center}}]
We can check the recursive definition you gave:
In[2]:= Sum[Binomial[n, k]*BernoulliB[k], {k, 0, n - 1}] == 0
Out[2]= True
Mathematica's result is incorrect, since this is true if and only if n > 1,
as is shown here when n = 1:
In[3]:= With[{n = 1}, Sum[Binomial[n, k]*BernoulliB[k], {k, 0, n - 1}] == 0]
Out[3]= False
The simplest way to do what you ask is to use Nest to build the list of
Bernoulli numbers using Solve on the recursive definition every time:
In[4]:= expect == Nest[With[{B = #, n = Length[#] + 1}, Join[B, b /.
Solve[Sum[Binomial[n, k]*Part[Append[B, b], k + 1], {k, 0, n - 1}] == 0,
b]]] &, {1}, 20]
Out[4]= True
However, with a little effort it is possible solve for BernoulliB[n - 1]
this way:
In[5]:= Solve[Sum[Binomial[n, k]*BernoulliB[k], {k, 0, n - 1}] ==
Sum[Binomial[n, k]*BernoulliB[k], {k, 0, n - 2}] +
Sum[Binomial[n, k]*BernoulliB[k], {k, n - 1, n - 1}], BernoulliB[n - 1]]
Out[5]= {{BernoulliB[-1 + n] -> -(Sum[BernoulliB[k] Binomial[n, k],
{k, 0, -2 + n}]/n)}}
Now, still using Nest to build the list of Bernoulli numbers, we have:
In[6]:= expect == Nest[With[{B = #, n = Length[#] + 1}, Append[B,
Sum[Binomial[n, k]*B[[k + 1]], {k, 0, n - 2}]/-n]] &, {1}, 20]
Out[6]= True
It is also possible to use Dot instead of Sum giving in an even simpler
expression:
In[7]:= expect == Nest[With[{B = #, n = Length[#] + 1}, Append[B,
Binomial[n, Range[0, n - 2]].B/-n]] &, {1}, 20]
Out[7]= True
Note that since Binomial[n, k] == n!/k!/(n-k)! then Binomial[n, k]/-n can
also be written as -(n-1)!/k!/(n-k)!
Enjoy!
"David Turner" <DTurner@faulkner.edu> wrote in message
news:j8r9gv$3jd$1@smc.vnet.net...
> Hello,
>
> I wish to compute several Bernoulli numbers, say B0 through B20. The
Bernoulli numbers are defined recursively by
>
> B0 = 1, and Solve[Sum[Binomial[n,k]*Bk,{k,0,n-1}]==0,Bn-1] for n > 1
>
> I am trying to compute these numbers in some type of loop, and display
them in a table. Any help is greatly appreciated.
>
> Thanks,
>
> David
>
> _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_
>
> This email and any files transmitted with it are confidential and intended
solely for the use of the individual or entity to whom they are addressed.
This message contains confidential information and is intended only for the
individual named. If you are not the named addressee you should not dissem
inate, distribute or copy this e-mail. Please notify the sender immediately
by e-mail if you have received this e-mail by mistake and delete this e-mail
from your system. If you are not the intended recipient you are notified
that disclosing, copying, distributing or taking any action in reliance on
the contents of this information is strictly prohibited.
[toc] | [prev] | [standalone]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web