NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/math/18848

Internet Message Format | 1993-01-28 | 5.5 KB

Path: sparky!uunet!europa.eng.gtefsd.com!emory!gatech!paladin.american.edu!howland.reston.ans.net!spool.mu.edu!samsung!balrog!web.ctron.com!wilson
From: [e-mail] (David Wilson)
Newsgroups: sci.math
Subject: Re: A strange recurrence and RESULT ABOUT PI
Message-ID: <[e-mail]>
Date: 28 Jan 93 19:15:10 GMT
Sender: [e-mail]
Reply-To: [e-mail] (David Wilson)
Organization: Cabletron Systems INc.
Lines: 180
Nntp-Posting-Host: web
Originator: wilson@web


    In <[e-mail]>, [e-mail]
    (Simon Plouffe [melancon]) writes:


>    Let a(1)=1/2 and iterate the following recurrence :
>
>                                              a(n)
>                              a(n + 1) = 2 ---------
>                                                   2
>                                           1 - a(n)
> This gives the numbers
>
>                                       336  354144
>                      1/2, 4/3, -24/7, ---, ------, ....
>                                       527  164833
>
> Now define this sign function to be,
>
> sign(x) = 0 if x <= 0
>           1 if x >  0
>
>    If you take the sum
>
>                              infinity
>                               -----
>                                \      sign(a(i))
>                        v =      )     ----------
>                                /           i
>                               -----       2
>                               i = 1
>
> This real number appears to be
>
>                                   arctan(1/2)
>                         v =   1 - -----------
>                                        Pi
>
> The questions are :
>
> 0)  Is this known ?

    I can't tell you if it is written down, but I can tell you that it
    is not especially deep.

> 1)  Can we explain this fact?

    We can prove it, as follows:

            ---<>---

    Lemma 1:  a(n) = tan(2^(n-1) atan(a(1)))

    Proof:  Induction on positive integer n, using the formula for
    tan(2x).

            ---<>---

    Lemma 2:  Redefine sign(x) to

        sign(x) =       1       if x >= 0
                        0       if x < 0

    does not affect the value of v.  (The redefined sign(x) simplifies
    later arguments).

    Proof:  The redefined sign(x) disagrees with the old sign(x) only at
    x = 0.  Thus v would be disturbed only if a(n) = 0 for some positive
    integer n.  But this never happens (exercise).

            ---<>---

    Lemma 3:  Let n be a positive integer and r a nonnegative real.  Let
    d(n, r) be the nth digit after the point in the zero-extended binary
    expansion of r.  Then

        d(n, r) =       0       if floor(2^n r) is an even integer
                        1       if floor(2^n r) is an odd integer.

    Proof:  Exercise.

            ---<>---

    Theorem:

             inf
             ---  sign(a(i))
             >    ----------  =  1 - atan(a(1))/pi
             ---     2^i
            n = 1

    Proof: We have

          sign(a(n)) = 1

    <==>  a(n) >= 0

    <==>  tan(2^(n-1) atan(a(1))) >= 0

    <==>  2^(n-1) atan(a(1))  in  [ pi k, pi k + pi/2 )
        for some integer k

    <==>  2^n atan(a(1))/pi  in  [ 2k, 2k + 1 )
        for some integer k

    <==>  floor(2^n atan(a(1))/pi) = 2k
        for some integer k

    <==>  floor(2^n atan(a(1))/pi) is an even integer

    <==>  d(n, atan(a(1))/pi) = 0

    so that

    sign(a(n)) =     1    if d(n, atan(a(1))/pi) = 0
                0    if d(n, atan(a(1))/pi) = 1

           = 1 - d(n, atan(a(1))/pi).

    But then

     inf                 inf
     ---  sign(a(i))     ---  1 - d(n, atan(a(1))/pi)
     >    ----------  =  >    ----------------------
     ---     2^i         ---          2^i
    n = 1               n = 1

              = 1 - atan(a(1))/pi.

    Letting a(1) = 1/2 solves the problem as posed.

> 2)  Are the distribution of binary digits of v random ?

    Normally, I leave sick questions like these to Bob Silverman.

> 3)  Can we find another formula that will give the decimal digits of 1/Pi ?

    Suppose we wish to generate the binary digits of

    v = k/pi

    where 0 < k < pi is rational, using the above recursion for a(n).
    We must then have

         1 - atan(a(1))/pi = k/pi

    ==>  atan(a(1)) = pi - k

    ==>  a(1) = tan(pi - k) = -tan(k)

    Since k is a positive rational, tan(k) is irrational (deep number
    theory) and so a(1) is irrational.  Rational a(1) is presumably
    an important prerequisite for this algorithm.  In my estimation,
    bases other than binary will suffer from the same limitation.

    Generating the decimal digits of atan(1/2)/pi, however, is probably
    possible.  You would have to modify the recursion for a(n) to

    a(n+1) = tan(atan(10 a(n)))

    with the right side expanded to a rational function of a(n).
    the sign(x) function would have to be modified to return a digit
    between 0 and 9, selected according to the signs of p(x), where
    p is one of nine polynomials satisfied by tan(2*pi*k/10) for
    integer 1 <= k <= 9.  Good luck.

> 4)  Can the formula be used to calculate v efficiently ?

    Probably not.  If floating point numbers are used for a(n), rounding
    errors quickly undermine the accuracy.  If integer pairs are used
    as a rational description of a(n), their bit-length approximately
    doubles each time n is incremented, which means that only a few
    (many fewer than 100) digits could be calculated in a lifetime
    on existing hardware.

--
David W. Wilson ([e-mail])

Disclaimer: "Truth is just truth...You can't have opinions about truth."
- Peter Schikele, introduction to P.D.Q. Bach's oratorio "The Seasonings."