login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #49 Mar 22 2023 21:59:02

%S 0,1,5,89,24305,1664474849,7382162541380960705,

%T 139566915517602820239076685726696149889,

%U 48426946216426731755940416722216940042029155625849753533402166195474237122305

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

%C 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

%C 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

%D Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.15 Optimal Stopping Constants, p. 362.

%H Richard Blecksmith, John Brillhart, and Irving Gerst, <a href="https://doi.org/10.1090/S0025-5718-1990-0995206-9">On the mod 2 reciprocation of infinite modular-part products and the parity of certain partition functions</a>, Mathematics of Computation 54.189 (1990): 345-376. The sequence appears in Prop. 21. - _N. J. A. Sloane_, Nov 28 2019

%H Ji Chen, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?t=318151">Inspired by IMO Shortlist 2001 algebra problem 3</a>

%H Tom Davis, <a href="https://aimath.org/~circle/theteacherscircle.org/circle/materials/AIM_MTC_2012_workshop/iterated.pdf">Iterated Functions</a>. See page 17.

%H Ross Millikan, <a href="https://math.stackexchange.com/q/3802381">Strategy to maximize the expected sum of 3 numbers each drawn from ~U(0, 1)</a>, answer on MathStackExchange.

%H Brian Skinner, <a href="https://gravityandlevity.wordpress.com/2011/08/04/when-is-a-shot-too-good-to-pass-up-the-shooters-sequence/">When is a shot too good to pass up? - The shooter's sequence</a>.

%H Wikipedia, <a href="https://de.wikipedia.org/wiki/Mandelbrot-Menge#Verhalten_der_Zahlenfolge">Mandelbrot-Menge</a>. See table for c=+0,25.

%F a(n) + A076628(n+1) = 2^(2^n-1). - Shai Covo (green355(AT)netvision.net.il), Mar 17 2010

%F a(n+1) = a(n)^2 + 4^(2^n-1), a(0) = 0. - _Henry Bottomley_, Aug 21 2018

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

%p f:=proc(n) option remember; if n = 1 then 1/2; else (f(n-1)^2+1)/2; fi; end;

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

%o (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 */

%o (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 */

%Y Denominators are (essentially) A058891.

%K nonn,frac

%O 0,3

%A _N. J. A. Sloane_, Dec 15 2009, following an email suggestion from Ji Chen