2015F MATH 3600-001 08.28 Newton's Method continued

2277 days ago by calkin

Continuing our investigations into the approximations using Newton's method of $\sqrt{2}$.

Starting with $x_0=2$, $x_1=3/2$, and 

\[ x_{n+1} = \frac{x_n}{2} + \frac{1}{x_n} \]

we can write 

\[ x_n = \frac{a_n}{b_n}\]

in which $a_n, b_n$ are integers with no common factors.  Then 

\[ \frac{a_{n+1}}{b_{n+1}} = \frac{a_n}{2b_n} + \frac{b_n}{a_n} = \frac{a_n^2 + 2 b_n^2}{2a_nb_n} \]

Now, for $n\geq 1$, we have $a_n$ is odd  and $b_n$ is even, so $a_n^2+ 2b_n^2$ is odd.  Furthermore, any odd prime divisor of $2a_nb_n$ must {\em fail} to divide $a_n^2 + 2b_n^2$, since $a_n$ and $b_n$ have no common factors.

Hence 

\[ a_{n+1} = a_n^2 + 2b_n^2 \mbox{ and } b_{n+1} = 2a_nb_n .\]

Proving that $an^2-2b_n^2 =1$.

We'll prove this by induction.  Suppose that $a_n^2 - 2b_n^2=1$.  Then 

\[ a_{n+1}^2 - 2 b_{n+1}^2 = (a_n^2 + 2 b_n^2)^2 -2 (2a_nb_n)^2\]  

\[ = (a_n^4 + 4 a_n^2b_n^2 + 4 b_n^4) - 2(4 a_n^2 b_n^2) \]

\[= a_n^4 - 4 a_n^2b_n^2 + 4 b_n^4 = (a_n^2-2b_n^2)^2 = 1^2 = 1 \]

How big is $x_n^2 - 2$?

\[ x_n^2-2 = \frac{a_n^2}{b_n^2} - 2 = \frac{a_n^2 -2b_n^2 }{b_n^2} = \frac{1}{b_n^2}.\]

Declare some variables, $C, \alpha$ so that we can compute with them:

var('C,alpha') 
       
(C, alpha)
(C, alpha)
c_0=C 
       
c_1 = alpha*c_0^2 print c_1 
       
C^2*alpha
C^2*alpha
c_2= alpha*c_1^2 print c_2 
       
C^4*alpha^3
C^4*alpha^3
c_3= alpha*c_2^2 print c_3 
       
C^8*alpha^7
C^8*alpha^7
c_4= alpha*c_3^2 print c_4 
       
C^16*alpha^15
C^16*alpha^15

It seems clear now that 

\[  c_n = \alpha^{2^n-1} C^{2^n} =\frac{1}{\alpha} (\alpha C)^{2^n} \]

and so $c_n$ grows like a constant raised to the $2^n$, that is, we see doubly exponential growth.

 

Let us compute the first $N$ values of $b_n$ and compare then to $2^{2^n}$. 

N = 20 a_list=[2,3] b_list=[1,2] for i in range(1,N): a=a_list[i] b=b_list[i] a_list.append(a^2 + 2*b^2) #b_list.append(2*a*b) #b_list = b_list + [2*a*b] b_list += [2*a*b] 
       
#print b_list 
       
for j in range(N): print (b_list[j]/2^(2^j)).n() 
       
0.500000000000000
0.500000000000000
0.750000000000000
1.59375000000000
7.18432617187500
145.987972162664
60280.8192007541
1.02778738945663e10
2.98780027580414e20
2.52492289017950e41
1.80318893015127e83
9.19660341077192e166
2.39221335575648e334
1.61861967434589e669
7.41028008749474e1338
1.55315300138903e2678
6.82297019320294e5356
1.31671548048849e10714
4.90375627185688e21428
6.80146937169076e42857
0.500000000000000
0.500000000000000
0.750000000000000
1.59375000000000
7.18432617187500
145.987972162664
60280.8192007541
1.02778738945663e10
2.98780027580414e20
2.52492289017950e41
1.80318893015127e83
9.19660341077192e166
2.39221335575648e334
1.61861967434589e669
7.41028008749474e1338
1.55315300138903e2678
6.82297019320294e5356
1.31671548048849e10714
4.90375627185688e21428
6.80146937169076e42857

So we see growth faster than $2^{2^n}$.  How about $3^{2^n}$?

for j in range(N): print (b_list[j]/3^(2^j)).n() 
       
0.333333333333333
0.222222222222222
0.148148148148148
0.0621856424325560
0.0109376972057872
0.000338373844937171
3.23846021517246e-7
2.96634817945213e-13
2.48879568287369e-25
1.75195716287626e-49
8.68144382777081e-98
2.13171387801630e-194
1.28529500172576e-387
4.67251420977504e-774
6.17513213603020e-1547
1.07854309736489e-3092
3.29018259709369e-6184
3.06185764589982e-12367
2.65164257879798e-24733
1.98872604612724e-49465
0.333333333333333
0.222222222222222
0.148148148148148
0.0621856424325560
0.0109376972057872
0.000338373844937171
3.23846021517246e-7
2.96634817945213e-13
2.48879568287369e-25
1.75195716287626e-49
8.68144382777081e-98
2.13171387801630e-194
1.28529500172576e-387
4.67251420977504e-774
6.17513213603020e-1547
1.07854309736489e-3092
3.29018259709369e-6184
3.06185764589982e-12367
2.65164257879798e-24733
1.98872604612724e-49465

How about $2^{3^n}$.  This must be way way too big, since $2^{3^n}>>3^{2^n}$.

for j in range(N): print (b_list[j]/2^(3^j)).n() 
       
0.500000000000000
0.250000000000000
0.0234375000000000
3.03983688354492e-6
1.94731551084784e-19
4.43596377515735e-62
3.93760392338330e-196
1.55289543267323e-610
3.02850923009723e-1878
2.27091691589689e-5730
9.78459445535814e-17385
8.17366231080919e-52544
5.19680580756707e-158413
1.58888442824797e-476804
6.42617614428489e-1433547
8.51371853408596e-4306910
7.93945516308470e-12933270
1.03549447525549e-38824892
5.94161819634105e-116524847
7.50839308497723e-349674881
0.500000000000000
0.250000000000000
0.0234375000000000
3.03983688354492e-6
1.94731551084784e-19
4.43596377515735e-62
3.93760392338330e-196
1.55289543267323e-610
3.02850923009723e-1878
2.27091691589689e-5730
9.78459445535814e-17385
8.17366231080919e-52544
5.19680580756707e-158413
1.58888442824797e-476804
6.42617614428489e-1433547
8.51371853408596e-4306910
7.93945516308470e-12933270
1.03549447525549e-38824892
5.94161819634105e-116524847
7.50839308497723e-349674881

That's too fast.  How about $2.5$?

for j in range(N): print (b_list[j]/(2.5)^(2^j)).n() 
       
0.400000000000000
0.320000000000000
0.307200000000000
0.267386880000000
0.202220804191027
0.115663587836314
0.0378388834815584
0.00404968850879462
0.0000463861398436698
6.08585301921702e-9
1.04758172193916e-16
3.10399360701785e-32
2.72512626628759e-63
2.10047855989981e-125
1.24790492694620e-249
4.40461539368482e-498
5.48732872671095e-995
8.51661371552975e-1989
2.05153482074764e-3976
1.19042702820006e-7951
0.400000000000000
0.320000000000000
0.307200000000000
0.267386880000000
0.202220804191027
0.115663587836314
0.0378388834815584
0.00404968850879462
0.0000463861398436698
6.08585301921702e-9
1.04758172193916e-16
3.10399360701785e-32
2.72512626628759e-63
2.10047855989981e-125
1.24790492694620e-249
4.40461539368482e-498
5.48732872671095e-995
8.51661371552975e-1989
2.05153482074764e-3976
1.19042702820006e-7951
for j in range(N): print j,(b_list[j]/(2.4)^(2^j)).n() 
       
0 0.416666666666667
1 0.347222222222222
2 0.361689814814815
3 0.370655312732196
4 0.388585064775781
5 0.427087836192402
6 0.515916477331552
7 0.752841914867670
8 1.60307032505207
9 7.26858951274738
10 149.432574854300
11 63159.0447771283
12 1.12827794706353e10
13 3.60061919840097e20
14 3.66690263955293e41
15 3.80315260034620e83
16 4.09102842352865e167
17 4.73380089327806e335
18 6.33818582805765e671
19 1.13625270354726e1344
0 0.416666666666667
1 0.347222222222222
2 0.361689814814815
3 0.370655312732196
4 0.388585064775781
5 0.427087836192402
6 0.515916477331552
7 0.752841914867670
8 1.60307032505207
9 7.26858951274738
10 149.432574854300
11 63159.0447771283
12 1.12827794706353e10
13 3.60061919840097e20
14 3.66690263955293e41
15 3.80315260034620e83
16 4.09102842352865e167
17 4.73380089327806e335
18 6.33818582805765e671
19 1.13625270354726e1344
for j in range(N): print j,(b_list[j]/(2.41)^(2^j)).n() 
       
0 0.414937759336100
1 0.344346688245726
2 0.355723925117397
3 0.358528614219295
4 0.363574395502365
5 0.373879432589366
6 0.395374033547751
7 0.442141499877873
8 0.552926689760261
9 0.864729153738900
10 2.11497479368317
11 12.6518893522959
12 452.747190216834
13 579771.043647113
14 9.50731832857319e11
15 2.55658987314895e24
16 1.84870289845612e49
17 9.66672219159049e98
18 2.64303837597438e198
19 1.97584071960139e397
0 0.414937759336100
1 0.344346688245726
2 0.355723925117397
3 0.358528614219295
4 0.363574395502365
5 0.373879432589366
6 0.395374033547751
7 0.442141499877873
8 0.552926689760261
9 0.864729153738900
10 2.11497479368317
11 12.6518893522959
12 452.747190216834
13 579771.043647113
14 9.50731832857319e11
15 2.55658987314895e24
16 1.84870289845612e49
17 9.66672219159049e98
18 2.64303837597438e198
19 1.97584071960139e397

Is it possible that the growth rate is like $(1+\sqrt{2})^{2^n}$?

for j in range(N): print (b_list[j]/(1+ sqrt(2))^(2^j)).n() 
       
0.414213562373095
0.343145750507620
0.353247018274313
0.353553125105796
0.353553390593075
0.353553390593274
0.353553390593275
0.353553390593276
0.353553390593279
0.353553390593283
0.353553390593293
0.353553390593311
0.353553390593349
0.353553390593424
0.353553390593575
0.353553390593875
0.353553390594477
0.353553390595680
0.353553390598087
0.353553390602900
0.414213562373095
0.343145750507620
0.353247018274313
0.353553125105796
0.353553390593075
0.353553390593274
0.353553390593275
0.353553390593276
0.353553390593279
0.353553390593283
0.353553390593293
0.353553390593311
0.353553390593349
0.353553390593424
0.353553390593575
0.353553390593875
0.353553390594477
0.353553390595680
0.353553390598087
0.353553390602900

Wow!  Our guess that this might be the case seems to have worked out rather nicely.  Can we identify the constant that we're seeing here? 

Look closely: it's  0.3535....  If we double that, we get 0.707.... 

(Aside: many people believe that the Boeing 707 was named that because its wings were at 45 degrees to the fuselage, and sin(45)=0.707: this is a lovely story, but unfortunately neither true, nor accurate: see http://www.boeing.com/news/frontiers/archive/2004/february/i_history.html.)

Anyway, is it possible that our constant is in fact $\frac{\sqrt{2}}{4}$?

for j in range(len(b_list)): print (4/sqrt(2)*b_list[j]/(1+ sqrt(2))^(2^j)).n() 
       
1.17157287525381
0.970562748477141
0.999133448222780
0.999999249088018
0.999999999999437
1.00000000000000
1.00000000000000
1.00000000000001
1.00000000000001
1.00000000000003
1.00000000000005
1.00000000000011
1.00000000000021
1.00000000000043
1.00000000000085
1.00000000000170
1.00000000000340
1.00000000000681
1.00000000001361
1.00000000002723
1.00000000005445
1.17157287525381
0.970562748477141
0.999133448222780
0.999999249088018
0.999999999999437
1.00000000000000
1.00000000000000
1.00000000000001
1.00000000000001
1.00000000000003
1.00000000000005
1.00000000000011
1.00000000000021
1.00000000000043
1.00000000000085
1.00000000000170
1.00000000000340
1.00000000000681
1.00000000001361
1.00000000002723
1.00000000005445

It appears that it is extremely close, but perhaps not close enough.   But before we give up, let's check our computation to more digits of accuracy.

for j in range(len(b_list)): print (4/sqrt(2)*b_list[j]/(1+ sqrt(2))^(2^j)).n(digits=20) 
       
1.1715728752538099024
0.97056274847714058562
0.99913344822277991109
0.99999924908801739671
0.99999999999943613120
1.0000000000000000000
1.0000000000000000000
1.0000000000000000000
1.0000000000000000001
1.0000000000000000001
1.0000000000000000003
1.0000000000000000005
1.0000000000000000011
1.0000000000000000021
1.0000000000000000043
1.0000000000000000086
1.0000000000000000171
1.0000000000000000343
1.0000000000000000685
1.0000000000000001371
1.0000000000000002742
1.1715728752538099024
0.97056274847714058562
0.99913344822277991109
0.99999924908801739671
0.99999999999943613120
1.0000000000000000000
1.0000000000000000000
1.0000000000000000000
1.0000000000000000001
1.0000000000000000001
1.0000000000000000003
1.0000000000000000005
1.0000000000000000011
1.0000000000000000021
1.0000000000000000043
1.0000000000000000086
1.0000000000000000171
1.0000000000000000343
1.0000000000000000685
1.0000000000000001371
1.0000000000000002742
for j in range(len(b_list)): print (4/sqrt(2)*b_list[j]/(1+ sqrt(2))^(2^j)).n(digits=40) 
       
1.171572875253809902396622551580603842861
0.9705627484771405856202646905163769428361
0.9991334482227799110889994775568160564261
0.9999992490880173967053971005657291157484
0.9999999999994361311943827893836498013520
0.9999999999999999999999996820519700518202
0.9999999999999999999999999999999999999997
0.9999999999999999999999999999999999999993
0.9999999999999999999999999999999999999986
0.9999999999999999999999999999999999999972
0.9999999999999999999999999999999999999945
0.9999999999999999999999999999999999999890
0.9999999999999999999999999999999999999780
0.9999999999999999999999999999999999999560
0.9999999999999999999999999999999999999120
0.9999999999999999999999999999999999998240
0.9999999999999999999999999999999999996479
0.9999999999999999999999999999999999992958
0.9999999999999999999999999999999999985917
0.9999999999999999999999999999999999971833
0.9999999999999999999999999999999999943666
1.171572875253809902396622551580603842861
0.9705627484771405856202646905163769428361
0.9991334482227799110889994775568160564261
0.9999992490880173967053971005657291157484
0.9999999999994361311943827893836498013520
0.9999999999999999999999996820519700518202
0.9999999999999999999999999999999999999997
0.9999999999999999999999999999999999999993
0.9999999999999999999999999999999999999986
0.9999999999999999999999999999999999999972
0.9999999999999999999999999999999999999945
0.9999999999999999999999999999999999999890
0.9999999999999999999999999999999999999780
0.9999999999999999999999999999999999999560
0.9999999999999999999999999999999999999120
0.9999999999999999999999999999999999998240
0.9999999999999999999999999999999999996479
0.9999999999999999999999999999999999992958
0.9999999999999999999999999999999999985917
0.9999999999999999999999999999999999971833
0.9999999999999999999999999999999999943666
for j in range(len(b_list)): print (4/sqrt(2)*b_list[j]/(1+ sqrt(2))^(2^j)).n(digits=100) 
       
1.1715728752538099023966225515806038428606562492461038536466405240185350\
43075785922299224931344716855
0.9705627484771405856202646905163769428360625045233768781201568558887897\
415452844662046504119316988728
0.9991334482227799110889994775568160564261251537948138560853331002188512\
125396718509581140056777616759
0.9999992490880173967053971005657291157484274792151899224743976525542992\
707813160056635625521369739720
0.9999999999994361311943827893836498013520555774324180699954736960990892\
694631662455405565381562002759
0.9999999999999999999999996820519700518203492696511088065333782421633110\
830259389092803986427787165458
0.9999999999999999999999999999999999999999999999998989090502520714559257\
096690662772472767865886323418
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999898
1.0000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000
1.0000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000
1.0000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999998
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999997
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999994
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999988
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999976
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999953
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999905
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999811
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999621
1.171572875253809902396622551580603842860656249246103853646640524018535043075785922299224931344716855
0.9705627484771405856202646905163769428360625045233768781201568558887897415452844662046504119316988728
0.9991334482227799110889994775568160564261251537948138560853331002188512125396718509581140056777616759
0.9999992490880173967053971005657291157484274792151899224743976525542992707813160056635625521369739720
0.9999999999994361311943827893836498013520555774324180699954736960990892694631662455405565381562002759
0.9999999999999999999999996820519700518203492696511088065333782421633110830259389092803986427787165458
0.9999999999999999999999999999999999999999999999998989090502520714559257096690662772472767865886323418
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999898
1.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999994
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999988
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999976
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999953
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999905
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999811
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999621
for j in range(len(b_list)): print (4/sqrt(2)*b_list[j]/(1+ sqrt(2))^(2^j)).n(digits=400) 
       
1.1715728752538099023966225515806038428606562492461038536466405240185350\
430757859222992249313447168545299723075381754059501503278882985255747117\
570058001283371735546681449888144884000989976944358788570597808800567880\
594509308062759705429651627182216027808953415390313825713570983204747927\
440094971840206254932069073363823407187587694832952098905084994244800765\
40328849559324936285977291250793183002306
0.9705627484771405856202646905163769428360625045233768781201568558887897\
415452844662046504119316988728201661547709475642990980326702088465517294\
579651992299769586719911300671130695994060138333847268576413147196592716\
432944151623441767422090236906703833146279507658117045718574100771512435\
359430168958762470407585559817059556874473831002287406569490034531195407\
580269026440503822841362524952409019861659
0.9991334482227799110889994775568160564261251537948138560853331002188512\
125396718509581140056777616758856492622122171861693331107871007827588015\
708167738192165948476984222818443663798044703350807131598047004684152358\
720101155197020092351068054827930326973503260375979554431519426231422802\
220625744597923993857909033780024933732110254077771823362661174060643857\
729146898977129976606325848381906675296414
0.9999992490880173967053971005657291157484274792151899224743976525542992\
707813160056635625521369739720392485928986328394104098483143033036570127\
225569873759504542439793132483988022943587666831429864146243405511821962\
996733097361186573132535271431597327422762473880405813973417871061913762\
602109266004288912027024982148773526855233205748684160510994865983011819\
435521419607993003700029032720303292062192
0.9999999999994361311943827893836498013520555774324180699954736960990892\
694631662455405565381562002759006434099331025945407380341097262950408072\
558863764832230666671632781625986296906146750790101650390527770473630231\
420019255216052621076459258203291476705141170748149796206743345424449905\
339067635604191157547077271788542490033360403178130739016957700602107755\
971791838794929380463280085978285311087539
0.9999999999999999999999996820519700518203492696511088065333782421633110\
830259389092803986427787165457744191654490492242814511603370181240502637\
521667158426366384263686494376501081170663080218990413199641063223553484\
874575362359300639723061856457880271224545876948333644862134417080037028\
071263257317417505708601831666880332373619331068450406192645972392263261\
691235640843897927641430795189673128394755
0.9999999999999999999999999999999999999999999999998989090502520714559257\
096690662772472767865886323418060251152101518194345814448148253938700785\
455909052864779282161868547042309841563198936289719380134346293838231945\
861690204174743461304983969584335871039533346946207984017234276187983120\
404402000776738673522309763137717671974315366182280687097963291874062851\
195865366012594641310456709414013109119159
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999897806198790617858312862208476841675460421526\
724999632674643205036801194299021763296551586299022124736662563656440026\
961552223951906221372380230848390344967847028853597870992194364154284507\
760472291541825862824116196932591908073314695599997391595055353948760154\
994275737850096593285568155589114689426482
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999998955642699437728511\
510079128951309720659837506903863622112073258059532757945857673724509557\
853789393681124044336525546663960421101640522825028648222691628280052787\
377602731477204655122272319118457554408595
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999890931752
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999939
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999878
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999755
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999511
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999021
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999998043
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999996085
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999992170
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999984341
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999968682
0.9999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999937363
1.171572875253809902396622551580603842860656249246103853646640524018535043075785922299224931344716854529972307538175405950150327888298525574711757005800128337173554668144988814488400098997694435878857059780880056788059450930806275970542965162718221602780895341539031382571357098320474792744009497184020625493206907336382340718758769483295209890508499424480076540328849559324936285977291250793183002306
0.9705627484771405856202646905163769428360625045233768781201568558887897415452844662046504119316988728201661547709475642990980326702088465517294579651992299769586719911300671130695994060138333847268576413147196592716432944151623441767422090236906703833146279507658117045718574100771512435359430168958762470407585559817059556874473831002287406569490034531195407580269026440503822841362524952409019861659
0.9991334482227799110889994775568160564261251537948138560853331002188512125396718509581140056777616758856492622122171861693331107871007827588015708167738192165948476984222818443663798044703350807131598047004684152358720101155197020092351068054827930326973503260375979554431519426231422802220625744597923993857909033780024933732110254077771823362661174060643857729146898977129976606325848381906675296414
0.9999992490880173967053971005657291157484274792151899224743976525542992707813160056635625521369739720392485928986328394104098483143033036570127225569873759504542439793132483988022943587666831429864146243405511821962996733097361186573132535271431597327422762473880405813973417871061913762602109266004288912027024982148773526855233205748684160510994865983011819435521419607993003700029032720303292062192
0.9999999999994361311943827893836498013520555774324180699954736960990892694631662455405565381562002759006434099331025945407380341097262950408072558863764832230666671632781625986296906146750790101650390527770473630231420019255216052621076459258203291476705141170748149796206743345424449905339067635604191157547077271788542490033360403178130739016957700602107755971791838794929380463280085978285311087539
0.9999999999999999999999996820519700518203492696511088065333782421633110830259389092803986427787165457744191654490492242814511603370181240502637521667158426366384263686494376501081170663080218990413199641063223553484874575362359300639723061856457880271224545876948333644862134417080037028071263257317417505708601831666880332373619331068450406192645972392263261691235640843897927641430795189673128394755
0.9999999999999999999999999999999999999999999999998989090502520714559257096690662772472767865886323418060251152101518194345814448148253938700785455909052864779282161868547042309841563198936289719380134346293838231945861690204174743461304983969584335871039533346946207984017234276187983120404402000776738673522309763137717671974315366182280687097963291874062851195865366012594641310456709414013109119159
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999897806198790617858312862208476841675460421526724999632674643205036801194299021763296551586299022124736662563656440026961552223951906221372380230848390344967847028853597870992194364154284507760472291541825862824116196932591908073314695599997391595055353948760154994275737850096593285568155589114689426482
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998955642699437728511510079128951309720659837506903863622112073258059532757945857673724509557853789393681124044336525546663960421101640522825028648222691628280052787377602731477204655122272319118457554408595
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999890931752
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999939
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999878
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999755
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999511
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999021
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998043
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996085
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999992170
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999984341
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999968682
0.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999937363
(log(b_list[-1])/log(10.)).n() 
       
401368.945483842
401368.945483842

Observe that this means that $b_n$ has on the order of four hundred thousand digits.

print b_list[5] 
       
627013566048
627013566048
print floor(sqrt(2)/4*(1+sqrt(2))^(2^5)) 
       
627013566048
627013566048
for i in range(10): print b_list[i], floor(sqrt(2)/4*(1+sqrt(2))^(2^i)) 
       
1 0
2 2
12 12
408 408
470832 470832
627013566048 627013566048
1111984844349868137938112 1111984844349868137938112
3497379255757941172020851852070562919437964212608
3497379255757941172020851852070562919437964212608
345963636159190997653185453890148615173898600719883426481871047662465656\
94525469768325292176831232
345963636159190997653185453890148615173898600719883426481871047662465656\
94525469768325292176831232
338536811494422613116048908841276441318459719760043042408042448921745564\
033552086544609184704239228339511303049317527075732707720494361061891707\
3241080260452775055121081948254768847591544963982848
338536811494422613116048908841276441318459719760043042408042448921745564\
033552086544609184704239228339511303049317527075732707720494361061891707\
3241080260452775055121081948254768847591544963982848
1 0
2 2
12 12
408 408
470832 470832
627013566048 627013566048
1111984844349868137938112 1111984844349868137938112
3497379255757941172020851852070562919437964212608 3497379255757941172020851852070562919437964212608
34596363615919099765318545389014861517389860071988342648187104766246565694525469768325292176831232 34596363615919099765318545389014861517389860071988342648187104766246565694525469768325292176831232
3385368114944226131160489088412764413184597197600430424080424489217455640335520865446091847042392283395113030493175270757327077204943610618917073241080260452775055121081948254768847591544963982848 3385368114944226131160489088412764413184597197600430424080424489217455640335520865446091847042392283395113030493175270757327077204943610618917073241080260452775055121081948254768847591544963982848

So, it appears that we have an exact formula for $b_n$!

\[ b_n =\left\lfloor \frac{\sqrt{2}}{4} (1+\sqrt{2})^{2^n}\right\rfloor. \]

 

If we now consult the online encyclopedia of integer sequences, we find that even more is known:

 

\[ b_n =\frac{\sqrt{2}}{4}\left(  (1+\sqrt{2})^{2^n}- (1-\sqrt{2})^{2^n}\right). \]

 

Furthermore, $a_n$ has a similar formula: 

\[ a_n =\frac{1}{2}\left(  (1+\sqrt{2})^{2^n} + (1-\sqrt{2})^{2^n}\right). \]

 

To understand why these formulae are true, we need to change our focus.  Let us consider continued fractions.