OFFSET
0,3
COMMENTS
Suppose that U_1,U_2,... is a sequence of independent uniform(0,1) random variables, and define random variables X_1,X_2,... as follows: X_1 = U_1, and, for n>=1, X_{n+1} = X_n or U_{n+1} according as U_{n+1} < E(X_n) or U_{n+1} > E(X_n), respectively, where E() denotes expectation. Then, the sequence E(X_n) is identical to the sequence f(n). Sketch of proof. E(X_1)=1/2; for n>=1, by the law of total expectation, we have E(X_{n+1}) = E(X_n)*E(X_n) + (1-E(X_n))*(1+E(X_n))/2. Hence E(X_{n+1}) = (E(X_n)^2 + 1)/2. - Shai Covo (green355(AT)netvision.net.il), Mar 08 2010
a(n) is the numerator of x_n where x_0 = 0 and x_{m+1} = (x_m)^2 + 1/4. - Michael Somos, May 12 2019
REFERENCES
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.15 Optimal Stopping Constants, p. 362.
LINKS
Richard Blecksmith, John Brillhart, and Irving Gerst, On the mod 2 reciprocation of infinite modular-part products and the parity of certain partition functions, Mathematics of Computation 54.189 (1990): 345-376. The sequence appears in Prop. 21. - N. J. A. Sloane, Nov 28 2019
Tom Davis, Iterated Functions. See page 17.
Ross Millikan, Strategy to maximize the expected sum of 3 numbers each drawn from ~U(0, 1), answer on MathStackExchange.
Brian Skinner, When is a shot too good to pass up? - The shooter's sequence.
Wikipedia, Mandelbrot-Menge. See table for c=+0,25.
FORMULA
a(n) + A076628(n+1) = 2^(2^n-1). - Shai Covo (green355(AT)netvision.net.il), Mar 17 2010
a(n+1) = a(n)^2 + 4^(2^n-1), a(0) = 0. - Henry Bottomley, Aug 21 2018
EXAMPLE
0/1, 1/2, 5/8, 89/128, 24305/32768, 1664474849/2147483648, 7382162541380960705/9223372036854775808, ...
MAPLE
f:=proc(n) option remember; if n = 1 then 1/2; else (f(n-1)^2+1)/2; fi; end;
MATHEMATICA
a[1]=0; a[n_] := a[n]=(a[n - 1]^2 + 1)/2; Numerator[Table[a[n], {n, 10}]] (* José María Grau Ribas, May 19 2013 *)
PROG
(PARI) {a(n) = if( n<2, n>0, a(n-1)^2 + 4*(a(n-1) - a(n-2)^2)^2)}; /* Michael Somos, Aug 16 2011 */
(PARI) {a(n) = my(x=0); if( n<1, 0, for(k=1, n, x = x^2 + 1/4); numerator(x))}; /* Michael Somos, May 12 2019 */
CROSSREFS
KEYWORD
nonn,frac
AUTHOR
N. J. A. Sloane, Dec 15 2009, following an email suggestion from Ji Chen
STATUS
approved