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:
• Prev by Date: matrix of vectors - super slow
• Next by Date: RE: Product
• Previous by thread: Re: Re: Re: Re: Re: Timing
• Next by thread: Re: Timing