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

Author

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

Keywords

• nonn
• frac

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

Examples

			0/1, 1/2, 5/8, 89/128, 24305/32768, 1664474849/2147483648, 7382162541380960705/9223372036854775808, ...
		

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
• 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.

Crossrefs

Denominators are (essentially) A058891.

Programs

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 *)

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 */

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