The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A277828 Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails. 0
 1, 2, 5, 11, 23, 45, 90, 179, 357, 712, 1422, 2842, 5681, 11360, 22716, 45430, 90856, 181709, 363413, 726822, 1453640, 2907276, 5814546, 11629086, 23258166, 46516327, 93032647 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS There are a family of sequences that represent the number of sequences of tosses of a fair coin to n tosses where there are no runs of m or more consecutive heads or consecutive tails. Some are given in this Encyclopedia. Their general form is given as part of the formula below. As n increases, the proportion of sequences of tosses that meet this condition decreases. When that proportion becomes a half or less of the total number of sequences of tosses, there is an even or better chance that a run of m consecutive heads or m consecutive tails occurs. There is actually a family of sequences of which the above sequence is an instance: those in which, for successive values of m, r*g(n) <= 2^n for r > 1. a(n) - ceiling((log 2)*2^n + (1-log 2)*n + (log 2)/2-2) equals 0 or (almost never) 1 for all n. Obtained using Weisstein's exact formula for Fibonacci k-step number seeing that the function g(N) described in the Formula section is 2*A092921(n-1,N+1). - Andrey Zabolotskiy, Nov 01 2016 REFERENCES Marcus du Sautoy, The Number Mysteries, Fourth Estate, 2011, pages 126 - 127. LINKS Eric Weisstein's World of Mathematics, Coin Tossing FORMULA For successive integers m, where g(n) is the number of sequences of tosses of a fair coin with runs of fewer than m consecutive heads or tails out of all possible sequences of tosses to n tosses, g(n) = 2^n where n <= m-1, and thereafter g(n) = g(n-1) + g(n-2) + ... + g(n-m+1) and a(m) = the least value of n for which 2g(n) <= 2^n. MAPLE a:= proc(n) option remember; local l, j; Digits:= 50;       if n<3 then n else l:= 0\$n;         for j from 0 while l[n]<1/2 do l:= seq(           (`if`(i=1, 1.0, l[i-1])+l[n-1])/2, i=1..n)         od; j       fi     end: seq(a(n), n=1..16);  # Alois P. Heinz, Nov 01 2016 MATHEMATICA a[n_] := a[n] = Module[{l, j}, If[n < 3, n, l = Table[0, {n}]; For[j = 0, l[[n]] < 1/2, j++, l = Table[(If[i == 1, 1, l[[i - 1]]] + l[[n - 1]])/2, {i, n}]]; j]]; Array[a, 16] (* Jean-François Alcover, May 31 2019, after Alois P. Heinz *) PROG (Python) def a(m):     if m == 1:         return 1     g = [2**i for i in range(1, m)]     sg, lim, n = sum(g), 2**(m-1), m     while True:         g.append(sg)         sg <<= 1         sg -= g.pop(0)         if g[-1] <= lim:             return n         lim <<= 1         n += 1 print([a(i) for i in range(1, 15)]) # Andrey Zabolotskiy, Nov 01 2016 (PARI) step(v)=my(n=#v); concat([sum(i=1, n-1, v[i])], concat(vector(n-2, i, v[i]), 2*v[n]+v[n-1])) a(n)=if(n<3, return(n)); my(v=vector(n), flips=1, needed=1/2); v=1; while(v[n]#v, i=1); M*=2; m++) \\ Charles R Greathouse IV, Nov 02 2016 CROSSREFS Cf. A135491, A135492, A135493. Sequence in context: A171985 A005986 A333396 * A147878 A179902 A140992 Adjacent sequences:  A277825 A277826 A277827 * A277829 A277830 A277831 KEYWORD nonn,more AUTHOR Tim Miles, Nov 01 2016 EXTENSIONS a(11)-a(22) from Andrey Zabolotskiy, Nov 01 2016 a(23)-a(27) from Alois P. Heinz, Nov 02 2016 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 1 16:59 EDT 2021. Contains 346400 sequences. (Running on oeis4.)