       Re: Re: Re: Timing

```It is easy to prove that expr is an integer. Let A=(3 + 2 Sqrt) and
B=3 -2 Sqrt. 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.

expr is

(A^m-B^m)/(4*Sqrt)= (A-B)*(A^(m-1) + A^(m-2) B +
A^(m-3)B^2+ ...A*B^(m-2)+B^(m-1))/(4 Sqrt) = 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 + 3)^
(2^(n - 1) - 1) -
(3 - 2*Sqrt)^
(2^(n - 1) - 1))/
((4*Sqrt)*(2^n -
1))], p},
p = N[((2*Sqrt + 3)^
(2^(n - 1) - 1) -
(3 - 2*Sqrt)^
(2^(n - 1) - 1))/
((4*Sqrt)*(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^(n - 1) - 1) - (3 -
>        2 Sqrt)^(2^(n - 1) - 1))/(4 Sqrt)]
>
> Note:
>
> FullSimplify[Together[expr], Element[n, Integers]]
>
> is considerably simpler
>
> ((3 + 2*Sqrt)^2^(-1 + n)*(-4 + 3*Sqrt) -
>  (3 - 2*Sqrt)^2^(-1 + n)*(4 + 3*Sqrt))/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^(n - 1) - 1) - (3 - 2 Sqrt)^(2^(n - 1) - 1))/
>> (4
>> Sqrt)
>> is divisable by (2^n - 1)
>>
>> or another words (2^n - 1) is divisor of ((3 + 2 Sqrt)^(2^(n -
>> 1) - 1) -
>> (3 - 2 Sqrt)^(2^(n - 1) - 1))/(4 Sqrt)
>>
>> My procedure Do[ If[IntegerQ[Expand[((3 + 2 Sqrt)^(2^(n - 1) -
>> 1) - (3 -
>> 2 Sqrt)^(2^(n - 1) - 1))/(4 Sqrt)]/(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:
>>>
>>> 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^(n - 1) - 1) - (3 - 2 Sqrt)^(2^(n -
>>>> 1) -
>>>> 1))/(4 Sqrt)]/(2^n - 1)
>>>> is every time integer
>>>>> Timing[Do[ If[IntegerQ[Expand[((3 + 2 Sqrt)^(2^(n - 1) - 1) -
>>>>> (3 -
>>>>> 2 Sqrt)^(2^(n - 1) - 1))/(4 Sqrt)]/(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