Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #6122 > unrolled thread

Bernoulli Numbers

Started byDavid Turner <DTurner@faulkner.edu>
First post2011-11-02 11:28 +0000
Last post2011-11-04 11:04 +0000
Articles 5 — 5 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  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

#6122 — Bernoulli Numbers

FromDavid Turner <DTurner@faulkner.edu>
Date2011-11-02 11:28 +0000
SubjectBernoulli 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]


#6133

From"Dr. Wolfgang Hintze" <weh@snafu.de>
Date2011-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]


#6143

FromSimon <simonjtyler@gmail.com>
Date2011-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]


#6163

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-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]


#6167

From"Alexander Elkins" <alexander_elkins@hotmail.com>
Date2011-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