A167424 Define a sequence of fractions by f(1) = 1/2, f(n+1) = (f(n)^2 + 1)/2; sequence gives numerators.

0, 1, 5, 89, 24305, 1664474849, 7382162541380960705, 139566915517602820239076685726696149889, 48426946216426731755940416722216940042029155625849753533402166195474237122305

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

Table of n, a(n) for n=0..8.

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

Ji Chen, Inspired by IMO Shortlist 2001 algebra problem 3

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

Denominators are (essentially) A058891.

Sequence in context: A258181 A355082 A067258 * A174591 A065197 A300348

Adjacent sequences: A167421 A167422 A167423 * A167425 A167426 A167427

Keyword

nonn,frac

Author

N. J. A. Sloane, Dec 15 2009, following an email suggestion from Ji Chen

Status

approved