HAKMEM -- SERIES -- DRAFT, NOT YET PROOFED

Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

SERIES

Previous Up Next

ITEM 116 (Schroeppel & Gosper):

 inf
 ====
 \       N! N!    4    2 pi
  >      ------ = - + --------- .
 /       (2 N)!   3   9 SQRT(3)
 ====
 N=0

PROBLEM: Evaluate in closed form

 inf
 ====
 \      N! N! N!
  >     -------- , which =
 /       (3 N)!
 ====
 N=0

  1
 /
 [
 I  (P + Q arccos (R)) dT , where
 ]
 /
  0

               2      3
     2 (8 + 7 T  - 7 T )
 P = -------------------  and
             2    3 2
       (4 - T  + T )

                    2        2    3
            4 (T - T ) (5 + T  - T )
 Q = ------------------------------------------  and
           2    3 2            2    3
     (4 - T  + T )  SQRT((4 - T  + T ) (1 - T))

          2    3
         T  - T
 R = 1 - ------- .
            2

ITEM 117 (Henry Cohen):

                        2      3      4
                       X      X      X
 gamma = - ln X + X - ---- + ---- - ---- ... + ERROR
                      2 2!   3 3!   4 4!

Where ERROR is of the order of (e^-X)/X.

ITEM 118 (Schroeppel):

Differentiate

   -Y
Y E   = X  to get Y + Y X Y' - X Y' = 0.

Substitute for Y a power series in X with coefficients to be determined. One observes the curious identity:

     N
    ====
    \      J - 1        N - J                   N      0
     >    J      (N - J)      BINOMIAL(N, J) = N     (0  = 1)
    /
    ====
    J=1

and thus

        ====    N - 1  N
        \      N      X
 Y(X) =  >     ---------
        /         N!
        ====
        N=1

ITEM 119 (Schroeppel):

PROBLEM: Can someone square some series for pi to give the series

   2                    ====
 pi    1    1           \       1
 --  = -- + -- + ... =   >      --  ?
  6     2    2          /        2
       1    2           ====    N

ITEM 120 (Euler):

The series accelerating transformation

(Abramowitz & Stegun, se. 3.6.27)

                          ====        K       K
                          \       (-1)  (delta  A0)
A0 - A1 + A2 - ...   =     >      -----------------
                          /              K+1
                          ====          2

                       K
                      ====
              K       \                      K-m
(where  (DELTA  A0) =  >  BINOMIAL(K, m) (-1)    Am   = Kth forward difference on A0)
                      /
                      ====
                      m=0

when applied to

 pi      1   1
 -- = 1 - - + - - ...
 4        3   5

gives

      ====     N-1   2
 pi   \       2    N!
 -- =  >     ----------
 4    /      (2 N + 1)!
      ====
      N=0

Applied to the formula for gamma in Amer. Math. Monthly (vol. 76, #3, Mar69 p273) =

  ====         T
  \       (- 1)  [LOG2(T)]
   >      ----------------     ([ ] means integer part of)
  /              T
  ====
  T=0

we get

  inf             K-1
  ====            ====
  \      -(K+1)   \              1
   >    2          >    ------------------
  /               /               I
  ====            ====  BINOMIAL(2 + J, J)
  K=1             J=0

(Gosper) which converges fast enough for a few hundred digits.

The array of reciprocals of the terms follows, with powers of 2 factored out to the left from all member of each row.

4                1
8              1   3
16           1   5   6
32         1   9  15  10
64       1  17  45  35  15
128    1  33 153 165  70  21
256  1  65 561 969 495 126  28

The next to left diagonal is 2^(N+1); the perpendicular one 3rd from the right is 1, *9/1= 9, *10/2= 45, *11/3= 165, *12/4= 495.

ITEM 121 (Gosper):

Consider the triangular array: 1 1 1 1 4 1 1 11 11 1 1 26 66 26 1 1 57 302 302 57 1 This bears an interesting relationship to Pascal's triangle. The 302 in the 4th southeast diagonal and the 3rd southwest one = 4*26 + 3*66. Note that rows then sum to factorials rather than powers of 2. If the nth row of the triangle is dotted with any n consecutive elements of (either) n+1st diagonal of Pascal's triangle, we get the nth Bernoulli polynomial: for n = 5, 1(6,i) + 26(6,i+1) + 66(6,i+2) + 26(6,i+3) + 1(6,i+4) = sum of 5th powers of 1 thru i+5, where (j,i) = BINOMIAL (j+i j).

ITEM 122 (Schroeppel, Gosper):

The "parity number" =

     inf
     ====
  1  \     PARITY(N)
  -   >    ---------
  2  /         N
     ====     2
     N=0

where the parity of N is the sum the bits of N mod 2. The parity number's value is .4124540336401075977..., or, for hexadecimal freaks, .6996966996696996... . It can be written (base 2) in stages by taking the previous stage, complementing, and appending to the previous stage:

.0
.01
.0110
.01101001
.0110100110010110
.01101001100101101001... radix 2

i.e.,

stage 0 = 0
                              N
                            -2
                       1 - 2   - stage N
stage N+1 = stage N +  ----------------- .
                              N
                             2
                            2

NUM 0 = 0, DEN 0 = 2

NUM N+1 = ((NUM N)+1) * ((DEN N)-1)

                       N+1
                 2    2
DEN N+1 = (DEN N)  = 2

then

                                    N            N
NUM N+1                           -2           -2
------- = stage N+1 = (stage N + 2   ) * (1 - 2   ) .
DEN N+1

Or, faster, by substituting in the string at any stage:

the string itself for zeros, and
the complement of the string for ones.

It is claimed (perhaps proven by Thue?) that the parity number is transcendental.

Its regular continued fraction begins: 0 2 2 2 1 4 3 5 2 1 4 2 1 5 44 1 4 1 2 4 1 1 1 5 14 1 50 15 5 1 1 1 4 2 1 4 1 43 1 4 1 2 1 3 16 1 2 1 2 1 50 1 2 424 1 2 5 2 1 1 1 5 5 2 22 5 1 1 1 1274 3 5 2 1 1 1 4 1 1 15 154 7 2 1 2 2 1 2 1 1 50 1 4 1 2 867374 1 1 1 5 5 1 1 6 1 2 7 2 1650 23 3 1 1 1 2 5 3 84 1 1 1 1284 ... and seems to continue with sporadic large terms in suspicious patterns. A non-regular fraction is

1/(3 -1/(2 -1/(4 -3/(16 -15/(256 -255/(65536 -65535/

            N     N
           2     2
      (...2   -(2  -1)/(... .

This fraction converges much more rapidly than the regular one, its Nth approximant being

1 + NUM N
--------- ,
1 + DEN N

which is, in fact, an approximant of the regular fraction, roughly the 2^N'th.

In addition, 4*(parity number) =

    1   3   15   255   65535
2 - - * - * -- * --- * ----- * ...
    2   4   16   256   65536

This gives still another non-regular fraction per the product conversion item in the CONTINUED FRACTION section.

For another property of the parity number, see the spacefilling curve item in the TOPOLOGY section.

ITEM 123 (Schroeppel, Gosper, Salamin):

Consider the image of the circle |z| = 1 under the function

                n
        ===    2
        \     z
 f(z) =  >    --- .
        /      n
        ===   2

This is physically analogous to a series of clock hands placed end to end. The first hand rotates around the center (0,0) at some rate. the next hand is half as long and rotates around the end of the first hand at twice this rate. The third hand rotates around the end of the second at four times this rate; etc. It would seem that the end of the "last" hand (really there are infinitely many) would sweep through space very fast, tracing out an (infinitely) long curve in the time the first hand rotates once. The hands shrink, however, because of the 2^n in the denominator. Thus it is unclear whether the curve's arc length is really infinite.

Also, it is a visually interesting curve, as are

        ===   n!                ===   FIB(n)
        \    z                  \    z
 f(z) =  >   ---   and   f(z) =  >   ------- .
        /    n!                 /    FIB(n)
        ===                      ===

Gosper has programmed the one mentioned first, which makes an intriguing display pattern. see following illustrations. If you write a program to display this, be sure to allow easy changing of:

z and z* on alternate terms (alternate hands rotate in opposite directions),
negation of alternate terms (alternate hands initially point in opposite directions), and
how many terms are used in the computation, since these cause fascinating variations in the resulting curve.

Figure 6(a). Image of circles |z| = 1/2, 3/4, 7/8, 1 under the function

                      inf
                      ===    n!
                      \     z
               f(z) =  >    --- .
                      /     n!
                      ===
                      n=1

Figure 6(b). Image of circles |z| = 1/8, 2/8, ..., 8/8 under the function

                      inf     n
                      ===    2
                      \     z
               f(z) =  >    --- .
                      /      n
                      ===   2
                      n=0

Both [original] plots by Salamin on the RLE PDP-1.

ITEM 124 (Schroeppel):

Consider

   ====         ====                    ====
   \     1      \      1      1         \        1       1
    >    --  =   >    (-- - ------)  +   >    (----- - -----)  =
   /      2     /       2    2   1      /          1       1
   ====  N      ====   N    N  - -      ====   N - -   N + -
                                 4                 2       2

               ====
               \           1
           2 -  >    ------------- .
               /      2     2
               ====  N  (4 N  - 1)

Take the last sum and re-apply this transformation. This may be a winner for computing the original sum. For example, the next iteration gives

               ====
        31     \                      1
        -- - 9  >      --------------------------------
        18     /        2     2           4      2
               ====    N  (4 N  - 1) (25 N  + 5 N  + 9)

where the denominator also =

    2                         2                2
   N  (2 N - 1) (2 N + 1) (5 N  - 5 N + 3) (5 N  + 5 N + 3)

ITEM 125 (Polya):

CONJECTURE: If a function has a power series with integer coefficients and radius of convergence 1, then either the function is rational or the unit circle is a natural boundary.

Reference: Polya, Mathematics and Plausible Reasoning, volume 2, page 46.

Previous Up Next