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>
- Re: Timing