[math-fun] Digit scanning question
OEIS A036903(n) gives the number of digits of pi you must scan before seeing every possible n-digit substring. Over all infinite strings of digits, what is the expected number of digits you must scan before seeing every n-digit substring?
See https://en.wikipedia.org/wiki/Coupon_collector's_problem WFL On 10/19/15, David Wilson <davidwwilson@comcast.net> wrote:
OEIS A036903(n) gives the number of digits of pi you must scan before seeing every possible n-digit substring.
Over all infinite strings of digits, what is the expected number of digits you must scan before seeing every n-digit substring?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Some quick computation suggests it's proportional to log(n). On Mon, 19 Oct 2015 at 22:59 David Wilson <davidwwilson@comcast.net> wrote:
OEIS A036903(n) gives the number of digits of pi you must scan before seeing every possible n-digit substring.
Over all infinite strings of digits, what is the expected number of digits you must scan before seeing every n-digit substring?
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
This seems like it should be about 10^n H_{10^n} but I don't think it is exact. Intuition suggests it is slightly more than this (in almost all cases, when there are only two numbers still to be found, you cannot find them consecutively in this case, where in the coupon collectors problem you can. (Consider missing numbers 23 and 45.) On the other hand, in some of the cases, you are much more likely to find the last two numbers consecutively (consider missing numbers 23 and 34.) These two effects might cancel exactly but I haven't figured out the right viewpoint to establish this. -tom On Tue, Oct 20, 2015 at 1:16 AM, Christian Lawson-Perfect < christianperfect@gmail.com> wrote:
Some quick computation suggests it's proportional to log(n).
On Mon, 19 Oct 2015 at 22:59 David Wilson <davidwwilson@comcast.net> wrote:
OEIS A036903(n) gives the number of digits of pi you must scan before seeing every possible n-digit substring.
Over all infinite strings of digits, what is the expected number of digits you must scan before seeing every n-digit substring?
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
participants (4)
-
Christian Lawson-Perfect -
David Wilson -
Fred Lunnon -
Tom Rokicki