Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: Re: Timing

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
>
  • Prev by Date: RE: Re: Player Pro and Packages
  • Next by Date: Re: Re: Wolfram User Interface Research?
  • Previous by thread: Re: Re: Timing
  • Next by thread: Re: Re: Re: Re: Timing