Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2008

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

Search the Archive

Re: Re: Re: Re: Timing

I wrote:

> 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.

I meant:

So expr clearly an integer since any sum of power A^k+B^k can be
expressed as polynomial with integer coefficients in the elementary  
symmetric
functions of A and B.

Andrzej Kozlowski



On 22 Apr 2008, at 19:26, Andrzej Kozlowski wrote:

> 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: Wolfram User Interface Research?
  • Next by Date: Re: Print[Plot] vs Print[text,Plot]?
  • Previous by thread: Re: Re: Re: Timing
  • Next by thread: Re: Re: Re: Re: Timing