Re: Re: Timing

*To*: mathgroup at smc.vnet.net*Subject*: [mg88037] Re: [mg87971] Re: Timing*From*: Carl Woll <carlw at wolfram.com>*Date*: Tue, 22 Apr 2008 06:29:59 -0400 (EDT)*References*: <480A0EE6.3090109@csl.pl> <200804211038.GAA28042@smc.vnet.net>

Artur wrote: >Who know how change bellow procedure to received reasonable timing? > >Part: >Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - 1) - >1))/(4 Sqrt[2])]/(2^n - 1) >is every time integer > > >>Timing[Do[ If[IntegerQ[Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - >>2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])]/(2^n - 1)], >> Print[n]], {n, 1, 17}]] >> >> >> >I will be greatfull for any help! (Mayby some N[] or Floor[N[]] or >Int[N[]] will be quickest > >Best wishes >Artur > > You should review Fibonacci numbers and difference equations. Anyway, one can prove that ((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2]) is an integer. Then notice: In[166]:= 3 - 2 Sqrt[2] // N Out[166]= 0.171573 As n gets larger, this term disappears. Therefore, all you need to do is: f[n_] := Round[(3 + 2 Sqrt[2])^(2^(n-1)-1)/(4 Sqrt[2])] Of course, the number of digits doubles every time, so on my computer things become very slow at f[23] (which is an integer with ~3.2 million digits). So, you might want to experiment with recurrence relations (a la Fibonacci). This might allow you to incorporate the 2^n-1 denominator and keep things from blowing quite so quickly. For example, if g[n_] := ((3 + 2 Sqrt[2])^n - (3 - 2 Sqrt[2])^n)/(4 Sqrt[2]) then (from the quadratic satisfied by 3 +/- 2 Sqrt[2]): g[n+2] == 6 g[n+1] - g[n] g[0]==0 g[1]==1 From this one can see that: {g[n+1], g[n]} == {{6, -1}, {1, 0}} . {g[n], g[n-1]} or MatrixPower[{{6, -1}, {1,0}}, n] == {{g[n+1], -g[n]}, {g[n], g[n-1]}} etc. Carl Woll Wolfram Research

**References**:**Re: Timing***From:*Artur <grafix@csl.pl>