Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Re: Re: Timing


Many thanks for Andrzej Kozlowski for this procedure!
I was execute these on my computer and received follwing Timing
Table[f[n], {n, 2, 20}] // Timing = 0.071
Table[f[n], {n, 2, 21}] // Timing = 0.089
Table[f[n], {n, 2, 22}] // Timing = 525.756
but increasing limit of n to 23 was catastrophe on my computer (probably 
RAM memory is limit)

Could help me sombody with big memory size computer check these 
procedure for n=23 (next true should occured for n=31)
Or sombody can explained this catastrophe in relation hardware-software 
relation or estimated how increased time if increased n (is this time 
polynomial time or not)

Best wishes
Artur

 



Andrzej Kozlowski pisze:
> It is easy to prove that expr is an integer. Let A=(3 + 2 Sqrt[2]) and  
> B=3 -2 Sqrt[2]. Then A and B are the roots of
> x^2 - (A + B) x + A B == 0 // Expand
> = x^2 - 6 x + 1 == 0
>
> with A+B = 6 and A*B=1.
>
> Note also that A-B=4Sqrt[2].
>
> expr is
>
> (A^m-B^m)/(4*Sqrt[2])= (A-B)*(A^(m-1) + A^(m-2) B +  
> A^(m-3)B^2+ ...A*B^(m-2)+B^(m-1))/(4 Sqrt[2]) = A^(m-1) + A^(m-2) B +  
> A^(m-3)B^2+ ...A*B^(m-2)+B^(m-1) = (A^(m-1)+B^(m-1)) + (A^(m-2)*B+  
> A*B^(m-2))+...= (A^(m-1)+B^(m-1) + (A^(m-3)+B^(m-3) + ....) + 1
> Here m is 2^(n-1)-1.The 1 is present because
>
>   A*B // Simplify
>   1
>
> so the product of the same powers o A and B is 1.
> So expr clearly an integer since any sum of power A^k+B^k can be  
> expresses as polynomial with integer coefficients in the symmetric  
> functions of A and B.
>
> So this does not require any use of Mathematica. The question when  
> this is divisible by 2^n-1 is far from clear. One could try to use  
> something like this:
>
> f[n_] := Module[
>       {prec = Log[10,
>             ((2*Sqrt[2] + 3)^
>                    (2^(n - 1) - 1) -
>                  (3 - 2*Sqrt[2])^
>                    (2^(n - 1) - 1))/
>               ((4*Sqrt[2])*(2^n -
>                     1))], p},
>       p = N[((2*Sqrt[2] + 3)^
>                   (2^(n - 1) - 1) -
>                 (3 - 2*Sqrt[2])^
>                   (2^(n - 1) - 1))/
>              ((4*Sqrt[2])*(2^n -
>                    1)), prec +
>              $MachinePrecision];
>        p == Round[p]]
>
> Table[f[n], {n, 2, 20}] // Timing
>   {11.4016, {False, True, False, True, False, True, False, False,  
> False, False,
>    False, True, False, False, False, True, False, True, False}}
>
> This is at least vastly faster than the OP's version.
>
> Andrzej Kozlowski
>
>
>
>
> On 22 Apr 2008, at 03:40, W_Craig Carter wrote:
>
>   
>> Dear Artur,
>> The previous method should work (in a very weak interpretation of
>> work) if you replace the expr with;
>>
>> expr = Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 -
>>        2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])]
>>
>> Note:
>>
>> FullSimplify[Together[expr], Element[n, Integers]]
>>
>> is considerably simpler
>>
>> ((3 + 2*Sqrt[2])^2^(-1 + n)*(-4 + 3*Sqrt[2]) -
>>  (3 - 2*Sqrt[2])^2^(-1 + n)*(4 + 3*Sqrt[2]))/8
>>
>> I can't immediately see that this result should be integer, but I am
>> getting integers for the first 10
>>
>> t = Table[nexpr /. n -> i, {i, 1, 10}] // Expand
>> Map[IntegerQ, t]
>>
>>
>> In general, Do is slow compared to Table, but it is the size of the
>> expression that is the limiting factor here.
>>
>> On Mon, Apr 21, 2008 at 9:09 AM, Artur <grafix at csl.pl> wrote:
>>     
>>> Dear Craig,
>>> My problem is find such numbers n that expression
>>>
>>>
>>> ((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - 1) - 1))/ 
>>> (4
>>> Sqrt[2])
>>> is divisable by (2^n - 1)
>>>
>>> or another words (2^n - 1) is divisor of ((3 + 2 Sqrt[2])^(2^(n -  
>>> 1) - 1) -
>>> (3 - 2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])
>>>
>>> My procedure 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}]
>>>
>>> is extremaly slow (probably Expand function do that as aslowly but  
>>> without
>>> Expand we don't have integers. I don't have idea how improove them.
>>> Best wishes
>>> Artur
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> W_Craig Carter pisze:
>>>
>>>
>>>
>>>       
>>>> Hello Artur,
>>>> I am not sure I understand your question:
>>>>
>>>> Are you asking for
>>>> Member[expr,Integers] && Element[n,Integers]
>>>> for 1 <= n <= 17 ?
>>>>
>>>> If so, this may be a hint, although it does not exactly check the  
>>>> above:
>>>>
>>>> Map[Element[Rationalize[#, .00000001], Integers] & ,
>>>> Table[expr /. n -> i, {i, 1, 30}]]
>>>>
>>>> and it is reasonably fast.  This approximate method gets worse for
>>>> large n; so I don't trust the result except for n=1,3,5
>>>>
>>>> Note, that
>>>> Map[Element[Rationalize[Expand[#], .00000001], Integers] & ,
>>>> Table[expr /. n -> i, {i, 1, 10}]]
>>>>
>>>> Gives a different result and is much slower, thus emphasizing the
>>>> result for large n.
>>>>
>>>> I am curious to see the better solutions....
>>>>
>>>> On Mon, Apr 21, 2008 at 6:38 AM, Artur <grafix at csl.pl> 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
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>           
>>>>
>>>>
>>>>
>>>>         
>>
>> -- 
>> W. Craig Carter
>>
>>     
>
>
>
> __________ NOD32 Informacje 2701 (20071204) __________
>
> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> http://www.nod32.com lub http://www.nod32.pl 
>
>
>
>   


  • Prev by Date: Re: Print[Plot] vs Print[text,Plot]?
  • Next by Date: Re: installing Playe rPro killed using Mathematica itself:
  • Previous by thread: Re: Re: Re: Re: Timing
  • Next by thread: Re: Re: Re: Re: Re: Timing