Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!rex!ukma!usenet.ins.cwru.edu!agate!apple!ntg!slandrum
From: slandrum@ntg.uucp (Stephen Landrum)
Newsgroups: comp.compression
Subject: Re: You can't get something for nothing.
Keywords: Pi, PI, transcendental
Message-ID: <60@goblin.ntg.uucp>
Date: 12 Apr 91 19:05:06 GMT
References: <4931@pink1.UUCP> <1991Apr10.193417.28193@agate.berkeley.edu> <1991Apr11.044640.20930@colorado.edu>
Reply-To: slandrum@ntg.UUCP (Stephen Landrum)
Organization: New Technologies Group, Inc.  Palo Alto CA
Lines: 18

In article <1991Apr11.044640.20930@colorado.edu> weverka@spot.Colorado.EDU (Robert T. Weverka) writes:
>In article <1991Apr10.193417.28193@agate.berkeley.edu> greg@math.berkeley.edu writes:
>A sloppy proof to that effect (but simple)
>suppose we want to compress a ten digit number   (decimal)
>the chance of matching the first digit to a digit in the pi sequence is 0.1
>the chance of matching the first two digits to two digits in the pi seq. is 0.01
>the chance of matching all ten is 10^-10.
>  so the description of where the ten digit sequence occurs in the sequence
>of pi digits is a number of size 10^10 and to store this we need 10 digits.
>  --->  no compression   QED  BFD .

Actually the problem is worse.  There is ~1/e probability that the 10 digit
sequence you are looking for does NOT occur in the first 10^10 digits.  You may
need more than 10 digits to store the location of your number in PI.
-- 
Stephen H. Landrum                                        VOICE: (415) 813-8909
                    UUCP: ...apple!ntg!slandrum
 USNAIL: New Technologies Group Inc. 2468 Embarcardero Way, Palo Alto CA 94303